数组篇

两数之和，二分查找，移除元素，长度最小子数组，螺旋矩阵

数组

1.两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target)
                    return new int[] { i, j };
            }
        }
        return new int[0];
    }
}
//常规两层for循环，注意同一个元素不能再匹配一次，所以，内层循环从J=i+1开始
//区别常规的，判断冒泡排序的算法，内层是n-i-1,因为每次已经将前i个元素排号了，所以内层循环要减去
//时间复杂度是O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//使用map集合简化时间复杂度
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                int j = map.get(target - nums[i]);
                return new int[] { i, j };
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}
//注意put放入元素的顺序，不能先放入元素，再查找，这样会查到到自己本身，会重复，
//先查找，再放入元素能完美的避开这一点

二分查找

704.二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
//二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

//这就涉及到区间的问题哦，使用while(left<=right)，说明区间是[left.right],所以right开始要赋值为nums.length-1，当(mid>target)时候，因为相等的时候已经判断过了，所以不需要再判断了，所以right=mid-1,

//当使用while(left<right)时候 ，说明区间是[left,right),所以开始right要赋值为nums.length，因为取不到，当(mid > right)的时候，因为又开区间，相等的时候没没判断过。所欲right=mid

//总之区间的问题，只要熟悉一种写法就够了

35.搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
}
//标准的二分查找，注意理解题目要求返回的东西，被顺序插入的地方，不一定是返回mid的位置，因为mid有可能找到 ，也有可能没有无法找到

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

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
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        int left = -1;
        int right = -1;
        for (int i = 0; i < len; i++) {
            if (nums[i] == target) {
                left = i;
                break;
            }
        }
        for (int i = len-1; i >= 0; i--) {
            if (nums[i] == target) {
                right = i;
                break;
            }
        }
        return new int[] { left, right };
    }
}
//常规暴力思路，两次for循环分别找第一个位置和最后一个位置，复杂度0(n)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1;
        int end = -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                first = mid;
                right = mid - 1;// 相等后继续从左区间找到首次位置
            }
        }

        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                end = mid;
                left = mid + 1;// 相等后继续从右区间找到最后位置
            }
        }
        return new int[] { first, end };
    }
}
//因为有重复的元素，所以二分法在相等后还需要调整区间，确保找到首次末次的，时间复杂度O(log(n))

69. x的平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if ((long) mid * mid > x) {
                right = mid - 1;
            } else if ((long) mid * mid < x) {
                ans = mid;			//因为平方根向下取整，所以要在小于的时候，记录ans的值
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return ans;
    }
}
//(long)mid*mid，乘法注意强转为long类型的，防止溢出报错

367.有效的完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = num;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if ((long) mid * mid > num) {
                right = mid - 1;
            } else if ((long) mid * mid < num) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
//熟能生巧，没啥说的，一遍过

移除元素

27.移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}
//通用解法，遍历，对于不是目标元素的，在原有基础上覆盖，时间O(n)，空间O(1)
//这就是双指针，快指针指向全部元素，判断符合条件的赋值给慢指针，最后返回慢指针的个数即可

26.删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 1;
        for (int fast = 1; fast < nums.length ; fast++) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}
//双指针，注意边界的取值问题，fast从1开始，确保能取值到数组末端，且能够跟前一位比较，而不发生数组溢出的问题，slow从1开始，因为第一个元素必定不重复，送0开始会漏掉第一个元素。

283.移动0

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
class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                swap(nums, fast, slow);
                slow++;
            }
        }
    }

    public void swap(int nums[], int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}
//交换的解法
//1.交换过程一定要把要交换的数据放入，传入的数据不能只是swap(int a,int b)，不然无法交换
//2.判断交换的条件，开始想着必须nums[slow]==0并且nums[fast]!=0，看起来对，但是这样条件苛刻会导致slow无法执行++的操作，进而一直指向某一位不动，无法继续，所以nums[fast]不为0交换即可实现

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}
//不用交换，直接覆盖，再把之后的赋值为0就行

844.比较含退格的字符串

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Solution {
    public boolean backspaceCompare(String s, String t) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder t1 = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != '#') {
                s1.append(c);
            } else if (s1.length() != 0) {
                s1.deleteCharAt(s1.length() - 1);
            }
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (c != '#') {
                t1.append(c);
            } else if (t1.length() != 0) {
                t1.deleteCharAt(t1.length() - 1);
            }
        }
        return s1.toString().equals(t1.toString());
    }
}
//StringBuilder工具类的方法还是不熟悉，detete(int start,int end),deleteCharAt(int index),还有就是比较的时候，转化为字符串调用String类中的equals()方法比较。这其实就是栈的数据结构，进栈，出栈


class Solution {
    public boolean backspaceCompare(String s, String t) {
        //使用栈方式，如果字符为#，则出栈顶元素，如果是普通字符，则压栈
        Stack<Character> stacks=new Stack();
        Stack<Character> stackt=new Stack();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)!='#'){
                stacks.push(s.charAt(i));
            }else{
                if(!stacks.isEmpty()){
                    stacks.pop();
                }
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if(t.charAt(i)!='#'){
                stackt.push(t.charAt(i));
            }else{
                if(!stackt.isEmpty()){
                    stackt.pop();
                }
            }
        }
        return stacks.equals(stackt);
    }
}
//栈数据结构的方法：Stack<Character> s = new Stack()
//				s.push()压栈
//              s.pop()出栈



class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        int countS = 0;// 记录s中#的个数
        int countT = 0;// 记录t中#的个数

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                char c = s.charAt(i);
                if (c == '#') {
                    countS++;
                    i--;
                } else if (c != '#' && countS != 0) {
                    countS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                char c = t.charAt(j);
                if (c == '#') {
                    countT++;
                    j--;
                } else if (c != '#' && countT != 0) {
                    countT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else if (i < 0 && j < 0) {
                return true;
            } else {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}
/*   双指针。
准备两个指针i,j，指向两个字符串的末尾，从后往前扫描，准备两个变量countS,countT,记录扫描到的#的个数
	1.若当前字符是#，count++,继续扫描j--
	2.若当前不是#，并且当前的s的count！=0，说明字符后面有退格，字符被抵消，count--，i--;
	3,若当前不是#，并且当前的s的count==0，说明当前字符没有退格，跳出S的循环，等待t找出没有退格的字符，在进行比较。
	
当i,j都>=0，没有越界的时候，比较，不相等返回false
	当都小于0 时候，退格空字符串也是空串，说明两个都是空串，返回true
	其他情况，返回false

*/

977.有序数组的平方

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
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }
}
//平方再排序，时间复杂度O(n*log(n))

class Solution {
    public int[] sortedSquares(int[] nums) {
        int len = nums.length;
        int ans[] = new int[len];
        int i = 0;
        int j = len - 1;
        int k = len - 1;
        while (i <= j) {
            if (nums[i] * nums[i] >= nums[j] * nums[j]) {
                ans[k--] = nums[i] * nums[i];
                i++;
            } else {
                ans[k--] = nums[j] * nums[j];
                j--;
            }
        }
        return ans;
    }
}
//双指针，因为本来数组就有序，所以定义首尾指针，判断平方后的大小放入新数组即可

长度最小的子数组

209.长度最小的子数组

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
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int l = nums.length;
        int substring = 0;
        for (int i = 0; i < l; i++) {
            int sum = 0;
            for (int j = i; j < l; j++) {
                sum += nums[j];
                if (sum >= target) {
                    substring = j - i + 1;
                    ans = Math.min(ans, substring);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
//暴力解法，java中int类型的最大值的表示方式，Integer.MAX_VALUE,Integer.MIN_VALUE
//需要先把ans设置为最大值，要不然调用Math.min()的时候，一直就是0了。然后最后判断ans是否被赋值了再返回答案

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int l = nums.length;
        int substring = 0;
        int i = 0; //滑动窗口起始位置
        int sum = 0;
        for (int j = 0; j < l; j++) {
            sum += nums[j];
            while (sum >= target) {
                substring = j - i + 1;
                ans = Math.min(ans, substring);
                sum -= nums[i];//窗口滑动，从sum中减去左边的值
                i++;
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
// i记录左边窗口的位置，当sum>target的时候，记录当前的substring，再减去左边窗口的位置，其他流程不变，核心代码为： sum-=nums[i++];

904.水果成篮

（找最多包含两种元素的最长字串，并且返回其长度。）

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 int totalFruit(int[] fruits) {
        int len = fruits.length;
        if (len <= 2)
            return len;
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int ans = 0;
        for (int right = 0; right < len; right++) {
            int a = fruits[right];// 快指针遍历的值
            map.put(a, map.getOrDefault(a, 0) + 1);
            // 将a的值与a元素的个数加入
            while (map.size() > 2) {
                int b = fruits[left];// 慢指针遍历的值
                map.put(b, map.get(b) - 1);// 将慢指针遍历的个数-1
                if (map.get(b) == 0) {
                    map.remove(b);
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
//双指针+HashMap
/*使用双指针形成窗口，使用HashMap存储窗口 中的元素和元素的个数，记录此时临时窗口的长度为：     right-left+1，当hash表长度＞2时候，即出现第三个元素，我们将left++，左边元素的个数+1
滑动窗口，滑动的是数组fruits的窗口，与right与left有关，而与HashMap的a,b无关
窗口不断滑动，右边次数+1，左边次数-1，左边为0时候，remove即可，不停的记录窗口的长度，返回最大值即可

map中的函数，getOrDefault(key,default),因为开始存入都没有数值，会出现null的情况，所以需要设置默认值，其他没什么了，这题，花了俩小时，还是看答案+花示例图才理解原因，对双指针+map组合的解法，又了解了许多

76.覆盖最小字串

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
45
46
47
48
class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer> window = new HashMap();  // 用来记录窗口中的字符和数量
        Map<Character,Integer> need = new HashMap();  // 需要凑齐的字符和数量
        // 构建need字符集
        for (int i = 0; i < t.length(); i++) {
            char needChar = t.charAt(i);
            need.put(needChar,need.getOrDefault(needChar,0)+1);
        }

        int left = 0,right = 0,valid = 0;
        // valid是用来记录窗口中满足need要求的字符和数量的数目，比如need中要求字符a数量为2，如果window中的a字符的数量等于了2，valid就＋1，反之-1
        int len = Integer.MAX_VALUE;  // 记录最小字串的长度
        int start = 0;  // 记录最小字串的起始位置
        while(right < s.length()){
            char addChar = s.charAt(right);  // 即将要加入window的字符
            window.put(addChar,window.getOrDefault(addChar,0) + 1);  
            right++;
            // 如果加入的字符是need中要求的字符，并且数量已经达到了need要求的数量，则valid+1
            // 这里和下面都有个坑，window.get(addChar)和need.get(addChar)返回的都是对象，最好用.equals()方法比较大小
            if(need.containsKey(addChar) && window.get(addChar).equals(need.get(addChar))){
                valid++;
            }
			// 当window中记录的字符和数量满足了need中要求的字符和数量，考虑缩窗口
            while(valid == need.size()){
                // 先判断当前的最小覆盖字串是否比之前的最小覆盖字串短
                if(right - left < len){  // 注意，这里上面已经对right实施了++操作，所以这里的长度不是right - left + 1
                    len = right - left ;
                    start = left;  // 如果最短，则记录下该最小覆盖字串的起始位置
                }
                char removeChar = s.charAt(left);
                // 开始缩减窗口，left右移，如果要从window删除的字符正好是need中需要的并且，数目也等于need中需要的数目，则删减后，该该字符要求的数量
                // 显然不满足need要求的数量，所以valid要-1；
                if(need.containsKey(removeChar) && window.get(removeChar).equals(need.get(removeChar))){
                    valid--;
                }
                window.put(removeChar,window.get(removeChar) - 1);
                left++;
            }

        }
        // 如果最小覆盖字串的长度相对于定义时没变，则t不包含s中所有的字符，返回"",如果长度改变过，说明存在这样的最小覆盖字串，直接输出。
        return len == Integer.MAX_VALUE?"":s.substring(start,start+len);
    }
}

//两个HashMap+滑动窗口，如何判断当前窗口包含t的所有字符呢？使用一个哈希表t记录t中所有的字符和个数，使用一个哈希表记录窗口中的所有字符以及个数，如果动态表中的t包含哈希表中的所有字符，并且对应个数不小于t中的个数，那么当前窗口是可行的
//代码我是写不出来了，copy一份吧，不浪费时间了

螺旋矩阵

59.螺旋矩阵II

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
class Solution {
    public int[][] generateMatrix(int n) {
        int ans[][] = new int[n][n];
        int loop = 0;// 循环次数
        int i, j;
        int count = 1;
        int start = 0;// 记录起始位置,控制遍历长度
        //int site = 1;// 控制每条边的遍历长度，每次遍历收缩1位
        while ((loop++) < n / 2) {
            for (j = start; j < n - start - 1; j++) {
                ans[start][j] = count++;
            }
            for (i = start; i < n - start - 1; i++) {
                ans[i][j] = count++;
            }
            for (; j > start; j--) {
                ans[i][j] = count++;
            }
            for (; i > start; i--) {
                ans[i][j] = count++;
            }
            start++;
            // site++;
        }
        if (n % 2 == 1) {
            ans[start][start] = count;
        }
        return ans;
    }
}

/*loop控制循环次数,
site控制每条边的遍历长度,初始为1，每次遍历[ , )，左闭右开区间的数据，写入
最后奇数写入中间的即可，或者不用site，用start-1控制也行，一样
i,j分别表示横纵坐标，所以开始先从j开始，

54.螺旋矩阵

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
//针对不是不是正方形的矩阵，即m不等于n，上述算法要改进，我开始按照上面的做，寻找m,n的最小值的一半作为循环条件，进入循环，但是最后的结果不对，只有最外圈的成功，内圈如果min(m,n)有奇数的话，进入最后一轮，就会赋值重复，(debug发现因为左右没有值，所以上下，在下上，赋值会重复)，所以需要单独给矩阵最中间的位置赋值。
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int l = Math.min(m, n);
        int loop = 0;
        List<Integer> list = new ArrayList<>();
        int i, j;
        int startx = 0;
        int starty = 0;
        while ((loop++) < l / 2) {
            for (j = startx; j < n - startx - 1; j++) {
                list.add(matrix[startx][j]);
            }
            for (i = starty; i < m - starty - 1; i++) {
                list.add(matrix[i][j]);
            }
            for (; j > startx; j--) {
                list.add(matrix[i][j]);
            }
            for (; i > starty; i--) {
                list.add(matrix[i][j]);
            }
            startx++;
            starty++;
        }
        if (l % 2 == 1) {
            if (m < n) {
                for (j = startx; j < n - startx; j++) {
                    list.add(matrix[startx][j]);
                }
            } else {
                for (i = starty; i < m - starty; i++) {
                    list.add(matrix[i][starty]);
                }
            }
        }
        return list;
    }
}
//注意边界条件，单独给矩阵中间赋值的边界条件，画个图一下子就看出来了

LCR 146. 螺旋遍历二维数组

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
45
46
class Solution {
    public int[] spiralArray(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return new int[0];
        }
        int n = matrix[0].length;
        int ans[] = new int[m * n];
        int count = 0;
        int l = Math.min(m, n);
        int loop = 0;
        int i, j;
        int startx = 0;
        int starty = 0;
        while ((loop++) < l / 2) {
            for (j = startx; j < n - startx - 1; j++) {
                ans[count++] = matrix[startx][j];
            }
            for (i = starty; i < m - starty - 1; i++) {
                ans[count++] = matrix[i][j];
            }
            for (; j > startx; j--) {
                ans[count++] = matrix[i][j];
            }
            for (; i > starty; i--) {
                ans[count++] = matrix[i][j];
            }
            startx++;
            starty++;
        }
        if (l % 2 == 1) {
            if (m < n) {
                for (j = startx; j < n - startx; j++) {
                    ans[count++] = matrix[startx][j];
                }
            } else {
                for (i = starty; i < m - starty; i++) {
                    ans[count++] = matrix[i][starty];
                }
            }
        }
        return ans;

    }
}
//思路一样，只是返回值变成了数组