二刷整合 - ToB企服应用市场:ToB评测及商务社交产业平台

class Solution {
public int search(int[] nums, int target) {
// 方法一：暴力解法
// for(int i = 0; i < nums.length; i++){
// if(nums[i] == target){//找到目标值
// return i;
// }
// }
// return -1;
// 方法二：二分查找（元素有序且无重复元素），使用迭代，执行速度快，但是内存消耗大
// return binarySearch(nums, target, 0, nums.length-1);
// 方法三：二分查找，统一使用左闭右闭区间
// 上来先处理边界条件
if(target < nums[0] || target > nums[nums.length - 1]){
return -1;
}
int left = 0;
int right = nums.length - 1;//右闭区间
int mid = (left + right) >> 1;
while(left <= right){//因为取得数组区间左右都是闭的，所以取等号的时候也能满足条件，还不需要退出循环
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;//往左区间缩
}else{
left = mid +1;
}
mid = (left + right) >> 1;
}
return -1;
}
// public int binarySearch(int[] nums, int target, int start, int end){
// int mid = (start+end)/2;
// int find = -1;
// if(start > end){//没有找到
// return -1;
// }
// if(target == nums[mid]){
// return mid;
// }else if(target < nums[mid]){
// find = binarySearch(nums, target, start, mid-1);
// }else{
// find = binarySearch(nums, target, mid+1, end);
// }
// return find;
// }
}

复制代码

class Solution {
public int searchInsert(int[] nums, int target) {
// 有序数组，考虑用二分查找
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left]){
return left;
}
if(target > nums[right]){
return right + 1;
}
while(left <= right){
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return left;//找不到，返回需要插入的位置
}
}

复制代码

class Solution {
public int[] searchRange(int[] nums, int target) {
// 非递减说明是升序的，但可以有重复元素
int[] arr = {-1, -1};
if(nums.length == 0){
return arr;
}
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left] || target > nums[right]){
return arr;//边界值
}
int leftPoint;//目标数组的开始位置
int rightPoint;//目标数组的结束位置
while(left <= right){
if(target == nums[mid]){
leftPoint = mid;
rightPoint = mid;
while(leftPoint >= 0 && target == nums[leftPoint]){
arr[0] = leftPoint;
leftPoint--;//向左寻找重复元素
}
while(rightPoint <= (nums.length - 1) && target == nums[rightPoint]){
arr[1] = rightPoint;
rightPoint++;//向右寻找重复元素
}
return arr;//返回找到的目标值的位置
}else if(target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return arr;//没有找到
}
}

复制代码

class Solution {
public int mySqrt(int x) {
// 使用二分查找
int left = 0;
int right = x;
int mid = (left + right) / 2;
while(left <= right){
if((long)mid * mid < x){
left = mid + 1;
}else if((long)mid * mid > x){
right = mid - 1;
}else{
return mid;
}
mid = (left + right) / 2;
}
return right;
}
}

复制代码

class Solution {
public boolean isPerfectSquare(int num) {
int left = 0, right = num;
while(left <= right){
int mid = (left + right) >> 1;
if((long) mid * mid == num){
return true;
}else if((long) mid * mid < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
}

复制代码

class Solution {
public int removeElement(int[] nums, int val) {
// 原地移除，所有元素
// 数组内元素可以乱序
// 方法一：暴力解法，不推荐，时间复杂度O(n^2)
// int right = nums.length;//目标数组长度，右指针
// for(int i = 0; i < right; i++){
// if(val == nums[i]){
// right--;//找到目标数值，目标数长度减一，右指针左移
// for(int j = i; j < right; j++){
// nums[j] = nums[j + 1];//数组整体左移一位（数组元素不能删除，只能覆盖）
// }
// i--;//左指针左移
// }
// }
// return right;
// 方法二：快慢指针，时间复杂度O(n)
// int solwPoint = 0;
// for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
// if(nums[fastPoint] != val){
// nums[solwPoint] = nums[fastPoint];
// solwPoint++;
// }
// }
// return solwPoint;
// 方法三：注意元素的顺序可以改变，使用相向指针，时间复杂度O(n)
int rightPoint = nums.length - 1;
int leftPoint = 0;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
while(leftPoint <= rightPoint){
if(nums[leftPoint] == val){
nums[leftPoint] = nums[rightPoint--];
}
leftPoint++;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
}
return leftPoint;
}
}

复制代码

class Solution {
public int removeDuplicates(int[] nums) {
// 相对顺序一致，所以不能使用相向指针。
// 考虑使用快慢指针
if(nums.length == 1){
return 1;
}
int slowPoint = 0;
for(int fastPoint = 1; fastPoint < nums.length; fastPoint++){
if(nums[slowPoint] != nums[fastPoint]){
nums[++slowPoint] = nums[fastPoint];
}
}
return slowPoint + 1;
}
}

复制代码

class Solution {
public void moveZeroes(int[] nums) {
// 要保持相对顺序，不能用相向指针
int slowPoint = 0;
for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
if(nums[fastPoint] != 0){
nums[slowPoint++] = nums[fastPoint];//所有非零元素移到左边
}
}
for(; slowPoint < nums.length; slowPoint++){
nums[slowPoint] = 0;//把数组末尾置零
}
}
}

复制代码

class Solution {
public boolean backspaceCompare(String s, String t) {
// 从前往后的话不确定下一位是不是"#"，当前位需不需要消除，所以采用从后往前的方式
int countS = 0;//记录s中"#"的数量
int countT = 0;//记录t中"#"的数量
int rightS = s.length() - 1;
int rightT = t.length() - 1;
while(true){
while(rightS >= 0){
if(s.charAt(rightS) == '#'){
countS++;
}else{
if(countS > 0){
countS--;
}else{
break;
}
}
rightS--;
}
while(rightT >= 0){
if(t.charAt(rightT) == '#'){
countT++;
}else{
if(countT > 0){
countT--;
}else{
break;
}
}
rightT--;
}
if(rightT < 0 || rightS < 0){
break;
}
if(s.charAt(rightS) != t.charAt(rightT)){
return false;
}
rightS--;
rightT--;
}
if(rightS == -1 && rightT == -1){
return true;
}
return false;
}
}

复制代码

class Solution {
public int[] sortedSquares(int[] nums) {
// 用相向的双指针
int[] arr = new int[nums.length];
int index = arr.length - 1;
int leftPoint = 0;
int rightPoint = nums.length - 1;
while(leftPoint <= rightPoint){
if(Math.pow(nums[leftPoint], 2) > Math.pow(nums[rightPoint], 2)){
arr[index--] = (int)Math.pow(nums[leftPoint], 2);
leftPoint++;
}else{
arr[index--] = (int)Math.pow(nums[rightPoint], 2);
rightPoint--;
}
}
return arr;
}
}

复制代码

class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 注意是连续子数组
// 使用滑动窗口，实际上还是双指针
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for(int right = 0; right < nums.length; right++){//for循环固定的是终止位置
sum += nums[right];
while(sum >= target){
result = Math.min(result, right - left + 1);//记录最小的子数组
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}

复制代码

class Solution {
public int totalFruit(int[] fruits) {
// 此题也可以使用滑动窗口
int maxNumber = 0;
int left = 0;
Map<Integer, Integer> map = new HashMap<>();//用哈希表记录被使用的篮子数量，以及每个篮子中的水果数量
for(int right = 0; right < fruits.length; right++){
map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);//往篮子里面放水果
while(map.size() > 2){//放进去的水果不符合水果类型
map.put(fruits[left], map.get(fruits[left]) - 1);
if(map.get(fruits[left]) == 0){
map.remove(fruits[left]);
}
left++;
}
maxNumber = Math.max(maxNumber, right - left + 1);
}
return maxNumber;
}
}

复制代码

class Solution {
public int[][] generateMatrix(int n) {
// 方法一：直接按序输出
int[][] arr = new int[n][n];
int top = 0;
int buttom = n - 1;
int left = 0;
int right = n - 1;;
int index = 1;
while(left <= right && top <= buttom && index <= n*n){
for(int i = left; i <= right; i++){
arr[top][i] = index++;
}
top++;
for(int i = top; i <= buttom; i++){
arr[i][right] = index++;
}
right--;
for(int i = right; i >= left; i--){
arr[buttom][i] = index++;
}
buttom--;
for(int i = buttom; i >= top; i--){
arr[i][left] = index++;
}
left++;
}
return arr;
}
}

复制代码

class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
List<Integer> list = new ArrayList<Integer>();
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
list.add(matrix[top][i]);
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
list.add(matrix[i][right]);
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
list.add(matrix[buttom][i]);
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
list.add(matrix[i][left]);
}
left++;
}
return list;
}
}

复制代码

class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0){
return new int[0];
}
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
int[] arr = new int[matrix.length*matrix[0].length];
int index = 0;
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
arr[index++] = matrix[top][i];
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
arr[index++] = matrix[i][right];
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
arr[index++] = matrix[buttom][i];
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
arr[index++] = matrix[i][left];
}
left++;
}
return arr;
}
}

复制代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 方法一：设置虚节点方式，推荐方式
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur = head;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
return dummy.next;
// 方法二：时间复杂度O(n)，空间复杂度O(1)
if(head == null){//空链表的情况
return head;
}
while(head != null && head.val == val){//头结点为val的情况
head = head.next;
}
ListNode temp = head;
while(temp != null && temp.next != null){
while(temp != null && temp.next != null && temp.next.val == val){
if(temp.next.next != null){
temp.next = temp.next.next;
}else{//最后一个节点为val的情况
temp.next = null;
}
}
temp = temp.next;
}
return head;
}
}

复制代码

class MyLinkedList {
int size;
ListNode head;
ListNode tail;
// 初始化链表,构建虚拟的头结点和尾节点
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
public int get(int index) {
ListNode cur = head;
if(index > size - 1 || index < 0){
return -1;
}
while(index >= 0){
cur = cur.next;
index--;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if(index > size){
return;
}
if(index < 0 ){
index = 0;
}
size++;
ListNode temp = new ListNode(val);
ListNode cur = head;
while(index > 0){
cur = cur.next;
index--;
}
temp.next = cur.next;
cur.next = temp;
temp.prev = cur;
}
public void deleteAtIndex(int index) {
ListNode cur = head;
if(index > size - 1 || index < 0){
return;
}
while(index > 0){
cur = cur.next;
index--;
}
cur.next = cur.next.next;
size--;
}
}
class ListNode {
int val;
ListNode next;
ListNode prev;
public ListNode(int val) {
this.val = val;
}
}

复制代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 方法一：在头结点不断插入
// if(head == null){
// return head;//空节点不需要反转
// }
// ListNode temp = head.next;//临时节点前移一位
// head.next = null;//代反转链表的头结点拆出来
// ListNode newHead = head;//待反转链表的头结点赋给新的链表
// while(temp != null){
// head = temp;//找出待反转链表的新头结点
// temp = temp.next;//临时节点前移一位
// head.next = null;//待反转链表的新头拆出来
// head.next = newHead;//待反转链表的心头指向新的链表
// newHead = head;//得到新的链表的新头
// }
// return newHead;
// 方法二：压栈，利用栈的先入后出
// if(head == null){
// return head;
// }
// Stack<ListNode> stack = new Stack<>();
// ListNode temp = head;
// while(head != null){
// temp = head.next;
// head.next = null;
// stack.push(head);
// head = temp;
// }
// ListNode newHead = new ListNode();
// temp = newHead;
// while(!stack.isEmpty()){
// temp.next = stack.pop();
// temp = temp.next;
// }
// return newHead.next;
// 方法三：递归
return reverse(null, head);
// 方法四：从后往前递归
// if(head == null){
// return null;
// }
// if(head.next == null){
// return head;
// }
// ListNode newHead = reverseList(head.next);
// head.next.next = head;
// head.next = null;
// return newHead;
}
public ListNode reverse(ListNode pre, ListNode cur){
if(cur == null){
return pre;
}
ListNode temp = cur.next;
cur.next = pre;
return reverse(cur,temp);
}
}

复制代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 方法一：从前往后进行迭代
// if(head == null){
// return null;
// }
// if(head.next == null){
// return head;
// }
// ListNode temp = head.next;//依次记录偶数节点的位置
// head.next = head.next.next;//交换相邻的节点
// temp.next = head;
// temp.next.next = swapPairs(temp.next.next);//迭代交换下一个相邻的节点
// return temp;
// 方法二：双指针
if(head == null){
return null;
}
if(head.next == null){
return head;
}
ListNode temp = head.next;
ListNode pre = head.next;//记录新的头结点
while(temp != null){
head.next = head.next.next;//交换相邻的节点
temp.next = head;
if(head.next == null || head.next.next == null){
break;
}else{
head = head.next;//指向下一个相邻节点的奇数节点
temp.next.next = temp.next.next.next;//上一个相邻节点的偶数节点指向下一个节点的偶数节点
temp = head.next;//下一个相邻节点的偶数节点
}
}
return pre;
}
}

复制代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 方法一：快慢指针，返回头结点说明head的头结点不能动，所以把链表的地址赋给另外一个对象
// 添加虚拟头结点，方便操作。比如需要删除的是头结点的时候不需要单独考虑这种特殊情况
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode cur = dummyHead;
ListNode temp = dummyHead;
for(int i = 0; i < n; i++){
temp = temp.next;
}
while(temp.next != null){
cur = cur.next;
temp = temp.next;
}
cur.next = cur.next.next;
return dummyHead.next;
}
}

复制代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode dummyHeadA = headA;
int countA = 0;
int countB = 0;
ListNode dummyHeadB = headB;
while(dummyHeadA.next != null){
dummyHeadA = dummyHeadA.next;
countA++;
}
while(dummyHeadB.next != null){
dummyHeadB = dummyHeadB.next;
countB++;
}
if(dummyHeadA != dummyHeadB){
return null;//尾节点不相交则说明不相交
}
dummyHeadA = headA;
dummyHeadB = headB;
int index = (countA - countB) > 0 ? (countA - countB) : -(countA - countB);//两个链表的长度差
for(int i = 0; i < index; i++){//让较长的链表先移动index位
if((countA - countB) > 0){
dummyHeadA = dummyHeadA.next;
}else{
dummyHeadB = dummyHeadB.next;
}
}
while(dummyHeadA != dummyHeadB){//两个链表逐次向前移动，找出相交的第一个节点
dummyHeadA = dummyHeadA.next;
dummyHeadB = dummyHeadB.next;
}
return dummyHeadA;
}
}

复制代码

/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
int count = 0;
while(fast != null && fast.next != null){//判断是否有环
fast = fast.next.next;
slow = slow.next;
count++;
if(fast == slow){
// 找环的入口
while(head != slow){
head = head.next;
slow = slow.next;
}
return head;
}
}
return null;
}
}

复制代码