快去刷题
0%

代码随想录

发表于 更新于
本文字数： 11k 阅读时长 ≈ 10 分钟

摘要：刷题recording

数组

二分查找

704、二分查找（easy）

最基本的二分查找思想，左闭右闭，<=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <=right){
            int mid = (left + right)/2;
            if(nums[mid]>target){
                right = mid-1;
            } 
            else if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

35、搜索插入位置（easy）

相同代码下java的内存消耗竟然是cpp的4倍…

主要思想还是二分查找，找不到则把目标值按顺序插入，即返回L/R+1。

image-20220310194657218 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid]>target){
                right = mid-1;
            }
            else if(nums[mid]< target){
                left = mid + 1;
            }
            else{
                return mid;
            }
        }
        return left;
    }
}

34、在排序数组中查找元素的第一个和最后一个位置（medium）

集合也可以（保存两个下标到集合中，然后打印输出）（为啥我想的把数组变为集合，然后取第一次和最后一次出现的位置，打印输出是错误的？答：好像是集合类调不了）

二分查找

第二次做还做吐了…qaq

找左边界：二分查找思想，相等的时候保存，继续往左查找，即right=mid-1；

找右边界：二分查找思想，相等的时候保存，继续往右查找，即left=mid+1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] arr = new int[]{-1,-1};
        int left =0,right = nums.length-1;
        while(left <= right){ //找左边界，顺序插入
            int mid = (left + right)/2;
            if(nums[mid]>target){
                right = mid -1;
            }else if(nums[mid] < target){
                left = mid +1;
            }else{
                arr[0] = mid;
                right = mid -1;
            }
        }
        left =0;right = nums.length-1;
        while(left <= right){ //找右边界
            int mid = (left + right)/2;
            if(nums[mid]>target){
                right = mid -1;
            }else if(nums[mid] < target){        
                left = mid +1;
            }else{
                 arr[1] = mid;
                 left = mid +1;
            }
        }
        return arr;
    }
}

69、x的平方根（easy）

中心思想：二分查找，考虑int*int变量长度，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//在比较过程中赋值
class Solution {
    public int mySqrt(int x) {
        int left = 0;int index =0; int right = x;
        while(left <= right){
            //int mid = (left+right)/2;报错：运行时间超出限制
            int mid = left + (right-left)/2;
            //long num = mid*mid; 结果错误
            if((long)mid*mid<=x){ 
                index = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return index;
    }
}

这个方法更加熟悉，与上面的解法相似，正常进行二分法，然后对返回结果进行考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//考虑的是最后左右指针在哪
class Solution {
    public int mySqrt(int x) {
        int left = 0;int index =0; int right = x;
        while(left <= right){
            int mid = left + (right-left)/2;
            if((long)mid*mid<x){ 
                left = mid+1;
            }else if((long)mid*mid>x){
                right = mid-1;
            }else{
                return mid;
            }
        }
        return right;
    }
}

367、有效的完全平方数（easy）

easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isPerfectSquare(int num) {
        int left =1,right = num;
        while(left<=right){
            int mid = left +(right -left)/2;
            if((long)mid*mid<num){
                left = mid+1;
            }else if((long)mid*mid>num){
                right = mid-1;
            }else{
                return true;
            }
        }
        return false;
    }
}

双指针法

27、移除元素（easy）

1、暴力破解法

2、双指针法：快指针遍历数组，慢指针保存合适的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeElement(int[] nums, int val) {
        int fast=0;
        int slow=0;
        //int index = 0;
        while(fast<nums.length){
            if(nums[fast]!=val){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

26、删除有序数组中的重复项（easy）

双指针法：数组的一个值肯定会在数组里，于是从第二个数开始比较，快慢指针有点颠倒的意思，慢指针依旧用来保存数组，但是是从1开始，而快指针用来比较当前的值与之前一个值是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length ==0){
            return 0;
        }
        int fast = 0;
        int slow =1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]!=nums[fast]){
                nums[slow] = nums[i];
                slow++;
            }fast++;
        }
        return slow;
    }
}

！283、移动零（easy）

1、补0

2、双指针法：左右指针，有点搞脑子，以后再做做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

！844、比较含退格的字符串（easy)

1、重构字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String str) {
        StringBuffer ret = new StringBuffer();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            char ch = str.charAt(i);
            if (ch != '#') {
                ret.append(ch);
            } else {
                if (ret.length() > 0) {
                    ret.deleteCharAt(ret.length() - 1);
                }
            }
        }
        return ret.toString();
    }
}

2、双指针法

两个字符串各一个指针，从后往前，一次遍历过程：指到“#”则指针加一，否则在>0的基础上减一，若<0则break，最终会各自得到一个值，然后比较两个值是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

977、有序数组的平方（easy）

双指针法：左右指针，分别比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left =0,right = nums.length-1;
        int[] nums2 = new int[nums.length];
        int index =nums.length-1;
        while(left<=right){
            if(nums[left]*nums[left] <= nums[right]*nums[right]){
                nums2[index--] =  nums[right]*nums[right];
                //index--;
                right--;
            }else{
                nums2[index--] = nums[left]*nums[left];
                //index--;
                left++;
            }
        }
        return nums2;
    }
}

滑动窗口

！209、长度最小的子数组（m）

1、暴力破解法

2、滑动窗口:while（右指针小于右边界），当sum>=目标值的时候在while里一直减左指针下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

！！！904、水果成篮（m）

！！！76、最小覆盖字串（hard）

螺旋矩阵

59、螺旋矩阵（m）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[][] generateMatrix(int n) {
        int top = 0,bottom = n-1,left = 0,right = n-1;//0,2
        int[][] target = new int[n][n];
        int temp =1;
        while(temp <=(n*n)){
            for(int i=left;i<=right;i++){
                target[top][i] = temp;
                temp++;
            }top++;
            for(int i=top;i<=bottom;i++){
                System.out.println(i);
                target[i][right] =temp;
                temp++;
            }right--;
            for(int i=right;i>=left;i--){
                target[bottom][i] = temp;
                temp++;
            }bottom--;
            for(int i=bottom;i>=top;i--){
                target[i][left] = temp;
                temp++;
            }left++;
        }
        return target;
    }
}

！54、螺旋矩阵（m）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.add(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

链表

迭代

203、移除链表元素（easy）

添加虚拟头节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        ListNode pre = newhead;
        ListNode cur = head;
        while(cur!=null){
            if(cur.val == val){
                //ListNode temp = cur;
                pre.next = cur.next;
                cur = cur.next;

            }else{
                pre = pre.next;
                cur = cur.next;
            }
        }
        return newhead.next;
    }
}

！206、反转链表（easy）

前一个节点，后一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

！24、两两交换链表中的节点（m）

与上题类似，一般都会设置一个虚拟头节点，然后将对下的一个或两个节点进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}

19、删除链表的倒数第N个结点（m）

①利用长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        ListNode pp =newhead;
        ListNode temp = head;
        int length = 0;
        while(temp!=null){
            length++;
            temp = temp.next;
        }
        int move = length - n;
        while(move>0){
            move--;
            pp = pp.next;
        }
        pp.next = pp.next.next;
        return newhead.next;
    }
}

②双指针：右指针先移动n位（n，即倒数第n个），然后左右一起移动，直到右指针为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

02.07链表相交（easy）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
    
}

142、环形链表II（m）

①哈希表：用一个集合存所有的结点，然后比较是否已经包含contains。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        if(head == null || head.next == null){
            return null;
        }
        ArrayList list = new ArrayList();
        ListNode temp = newhead;
        while(temp!= null){
            if(list.contains(temp)){
                return temp;
            }else{
                list.add(temp);
            }
            temp = temp.next;
        }
        return null;
    }
}

②快慢指针

递归