leetcode-数组

leetcode-数组

数组是存放在连续内存空间上的相同类型数据的集合。

二分查找

/**
     * 二分查找  leetcode704
     */
public int search(int[] nums, int target) {
    if(target < nums[0] || target > nums[nums.length-1]){
        return -1;
    }
    int left = 0;
    int right = nums.length-1;
    int middle = 0;
    while (left <= right){
        middle = (left + right)/2;
        if(target == nums[middle]){
            return middle;
        }else if(target < nums[middle]){
            right = middle-1;
        }else {
            left = middle+1;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

搜索插入位置 leetcode-35

public int searchInsert(int[] nums, int target) {
    if(target < nums[0] ){
        return 0;
    }
    if(target > nums[nums.length-1]){
        return nums.length;
    }
    int left = 0;
    int right = nums.length-1;
    int middle = 0;
    while (left <= right){
        middle = (left + right)/2;
        if(target == nums[middle]){
            return middle;
        }else if(target < nums[middle]){
            right = middle-1;
        }else {
            left = middle+1;
        }
    }
  /*  for (int i = 0; i < nums.length; i++) {
        if(target > nums[i] && target < nums[i+1]){
            return i+1;
        }
    }
    return -1;*/
    return left; //这里可以用奇数或者偶数个序列试一下，可以发现查找不到的时候就是返回left
}
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

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

由于是非递减的顺序，可以考虑二分法。

在第一次找到target时，向左右探测。

在左边和右边分别执行二分法找到target后返回下标。

public int[] searchRange(int[] nums, int target) {
    int[] arr = {-1, -1};
    arr[0] = search2(nums, target, 0); //左边
    arr[1] = search2(nums, target, 1); //右边
    return arr;
}

public int search2(int[] nums, int target, int flag) {
    if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) {
        return -1;
    }
    int left = 0;
    int right = nums.length - 1;
    int middle = 0;
    int ret = -1;
    while (left <= right) {
        middle = (left + right) / 2;
        if (target == nums[middle]) {
            ret = middle;
            if (flag == 1) { //探测左边
                right = middle - 1;
            } else { //探测右边
                left = middle + 1;
            }
        } else if (target < nums[middle]) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return ret;
}
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

x 的平方根 leetcode-69

/**
     * 69题  求平方根
     *
     * @param x
     * @return
     */
public int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }
    if (x == 1) {
        return 1;
    }
    int l = 0;
    int r = x;
    int middle = 0;
    while (l <= r) {
        middle = (l + r) / 2;
        if (x / middle < middle) { //用乘法会溢出
            r = middle-1;
        } else if(x / middle > middle){
            l = middle+1;
        }else{
            return middle;
        }
    }
    return r; //跳出循环后 l>r 将值小的返回
}
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

有效的完全平方数 leetcode-367

public boolean isPerfectSquare(int num) {
    if (num == 0 || num == 1) {
        return true;
    }
    int l = 0;
    int r = num;
    while (l <= r) {
        int m = (l + r) / 2;
        long square = (long) m *m;
        if (square == num) {
            return true;
        } else if (square <num) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

移除元素

/**
     * leetcode 27题
     * @param nums
     * @param val
     * @return
     */
public int removeElement(int[] nums, int val) {
    //        int j = 0;
    //        for (int i = 0; i < nums.length; i++) {
    //            if(nums[i] == val){
    //                j++;
    //            }else{
    //                nums[i-j] = nums[i];
    //            }
    //        }
    //        return nums.length-j;
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] != val){
            nums[j++] = nums[i];
        }
    }
    return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

删除排序数组中的重复项 leetcode-26

/**
     * leetcode-26.删除排序数组中的重复项
     * @param nums
     * @return
     */
public int removeDuplicates(int[] nums) {
    int j = 0;
    int len = nums.length;
    for (int i = 0; i < len+-1; i++) {
        if(nums[i] == nums[i+1]){
            j++;
        }else{
            nums[i+1-j] = nums[i+1];
        }
    }
    //        for (int i = 0; i < nums.length; i++) {
    //            System.out.printf("%d",nums[i]);
    //        }
    return len-j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

leetcode-283 移动零

/**
     * leetcode-283 移动零
     * @param nums
     */
public void moveZeroes(int[] nums) {
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] != 0){
            //非零元素与零元素交换
            int temp = nums[j];
            nums[j++] = nums[i];
            nums[i] = temp;
        }
    }
    for (int n : nums) {
        System.out.println(n);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

比较含退格的字符串 leetcode-844.

⭐️

/**
     * 844. 比较含退格的字符串
     *
     * @param s
     * @param t
     * @return
     */
public boolean backspaceCompare(String s, String t) {
    return convert(s).equals(convert(t));
}

public String convert(String s) {
    int skip = 0;
    StringBuilder sb = new StringBuilder();
    char[] arrayStr = s.toCharArray();
    for (int i = arrayStr.length-1; i >= 0; i--) { //倒序遍历
        if(arrayStr[i] == '#'){
            skip++;
        }else if(skip==0){
            sb.append(arrayStr[i]);
        }else{
            skip--;
        }
    }
    return sb.toString();
}
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

有序数组的平方

/**
* leetcode-977
* @param nums
* @return
*/
public int[] sortedSquares(int[] nums) {
    int len = nums.length;
    int negative = 0; //负数的最后一个下标
    for (int i = 0; i < len; i++) {
        if(nums[i] < 0){
            negative = i;
        }else {
            break;
        }
    }
    int[] ans = new int[len];
    int i= negative;int j=negative+1;
    int index = 0;
    //负数平方后会变成一个递减序列 而正数是递增序列  将这两个序列用归并排序的方法放入ans
    while (i >=0 && j< len){
        if(nums[i]*nums[i] <= nums[j]*nums[j]){
            ans[index++] = nums[i]*nums[i];
            i--;
        }else {
            ans[index++] = nums[j]*nums[j];
            j++;
        }
    }
    while (i >= 0){
        ans[index++] = nums[i]*nums[i];
        i--;
    }
    while (j < len){
        ans[index++] = nums[j]*nums[j];
        j++;
    }
    return ans;
}
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

长度最小的子数组

用滑动窗口的方式解决。

在找到一个满足大于等于target的集合后，起始位置往后移动（即缩小窗口大小），减去缩小部分的值，若依然满足条件则继续往后移动，否则跳出循环，终止位置往后移动。

/**
     * 长度最小的子数组 leetcode-209
     * @param target
     * @param nums
     * @return
     */
public int minSubArrayLen(int target, int[] nums) {
    int j = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    //快指针走到数组末尾后就可以停止 因为找的是最小
    for (int i = 0; i < nums.length; i++) {
        sum+=nums[i];
        while (sum >= target){
            minLen = Math.min(minLen,i-j+1);
            sum-=nums[j++]; //起始位置往后移
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法2：

public String minWindow3(String s, String t) {
    if (s == null || s.length() == 0 || t == null || t.length() == 0) {
        return "";
    }
    int minLen = Integer.MAX_VALUE;
    int begin = 0; //保存起始位置
    int left = 0, right = 0, valid = 0;
    int[] needs = new int[26];
    int[] window = new int[26];
    for (char c : t.toCharArray()) {
        needs[c - 'a']++;
    }
    int count = 0; //needs数组中非零值的个数 例如t="aa",则needs实际大小为1
    for (int i = 0; i < needs.length; i++) {
        if (needs[i] != 0) count++;
    }
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        if (needs[c - 'a'] != 0) {//窗口中只统计t中的字母
            window[c - 'a']++;
            if (window[c - 'a'] == needs[c - 'a'])
                valid++;
        }
        while (valid == count) {
            if (right - left < minLen) {
                minLen = right - left;
                begin = left; //记录起始位置和最小长度
            }
            //缩小窗口，优化
            char d = s.charAt(left);
            left++;
            if (needs[d - 'a'] != 0) {
                if (window[d - 'a'] == needs[d - 'a']) {
                    valid--;
                }
                window[d - 'a']--;
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(begin, begin + minLen);
}
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

水果成篮 leetcode -904

/**
     * 904. 水果成篮
     *
     * @param fruits
     * @return
     */
public int totalFruit(int[] fruits) {
    Map<Integer, Integer> map = new HashMap<>();
    int ans = 0;
    for (int i = 0, j = 0; i < fruits.length; i++) {
        int x = fruits[i];
        map.put(x, map.getOrDefault(x, 0) + 1); //获取key为x的value值，若存在则加1
        // 否则将新元素初始为1
        while (map.size() > 2) {
            int y = fruits[j++];
            map.put(y, map.get(y) - 1);
            if (map.get(y) == 0) {
                map.remove(y);
            }
        }
        ans = Math.max(ans, i - j + 1);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

也可以这样写：https://leetcode.cn/problems/fruit-into-baskets/solutions/1897490/by-ac_oier-skgk/

public int totalFruit(int[] fs) {
    int n = fs.length, ans = 0;
    int[] cnts = new int[n + 10];
    for (int i = 0, j = 0, tot = 0; i < n; i++) {
        if (++cnts[fs[i]] == 1) tot++;
        while (tot > 2) {
            if (--cnts[fs[j++]] == 0) tot--;
        }
        ans = Math.max(ans, i - j + 1);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12

最小覆盖子串 leetcode-76

public String minWindow(String s, String t) {
    if (s == null || s.length() == 0 || t == null || t.length() == 0){
        return "";
    }

    //先找到一个满足条件的序列
    int min = Integer.MAX_VALUE;
    int[] freqT = new int[128]; //统计t中各字符的数量
    int cnt = t.length(); //t序列的字符数量
    int begin = 0; //起始位置
    for (char c : t.toCharArray()) {
        freqT[c]++;
    }
    int l = 0, len = s.length(),r=0;
    while (r < len){
        char cR = s.charAt(r);
        if(freqT[cR] > 0){ //需要字符cR
            cnt--;
        }
        freqT[cR]--;

        //已找到满足条件的序列 缩小序列长度 找到最优
        if(cnt == 0){
            while (freqT[s.charAt(l)] < 0){
                freqT[s.charAt(l)]++;
                l++;
            }
            if(r-l+1 < min){ //找到窗口最小值 记录下起始位置
                min = r-l+1;
                begin = l;
            }

            //l再增加一个位置，寻找下一个能满足条件的位置
            freqT[s.charAt(l)]++; //左边界右移之前需要释放s.charAt(l)
            l++;
            cnt++;
        }
        r++;
    }
    return min == Integer.MAX_VALUE ? "" : s.substring(begin,begin+min);
}

//稍简化
 public String minWindow(String s, String t) {
      int len = s.length();
      int lenT = t.length();
      if (len == 0 || lenT == 0) {
          return "";
      }
      int[] needMap = new int[128]; //映射,大小写都有 大小定义为128
      for (int i = 0; i < lenT; i++) {
          needMap[t.charAt(i)]++;
      }
      int minLen = len + 1; //最小的长度设置为一个不可能到达的大的数
      int left = 0, right = 0; //滑动窗口的左右边界
      int count = lenT; //真正需求的字符个数
      int startIdx = -1;
      while (right < len) { //减去表示进入窗口 加上表示离开窗口
          char c = s.charAt(right);
          if (needMap[c] > 0) { //证明该字符是t中需要的
              count--;
          }
          needMap[c]--;//加入窗口
          if (count == 0) { //找到一个可行解
              //优化可行解 找到更短的 例如 AABC 中优化为 ABC
              while (needMap[s.charAt(left)] < 0) { //排除多余元素
                  needMap[s.charAt(left)]++;
                  left++; //窗口缩小 此时left应该停留在第二个A的位置
              }
              if (right - left + 1 < minLen) { //找到了更短的长度
                  minLen = right - left + 1;
                  startIdx = left; //记录下取得最短时的起始下标 返回结果时用到
              }
              //让left再增加一个位置，开始寻找下一个满足条件的滑动窗口,空间要放出来
              needMap[s.charAt(left)]++;
              left++;
              count++;
          }
          right++;
      }
      return minLen == len + 1 ? "" : s.substring(startIdx, startIdx + minLen);
  }
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

螺旋矩阵

/**
     *  螺旋矩阵 II leetcode-59
     * @param n
     * @return
     */
public int[][] generateMatrix(int n) {
    int start = 0,end = n-1;
    int cnt = 1;
    int[][] ans = new int[n][n];
    int loop = n / 2;
    while (loop > 0){
        //从左至右
        for (int i = start; i <= end; i++) {
            ans[start][i] = cnt++;
        }
        //从上至下
        for (int i = start+1; i <= end ; i++) {
            ans[i][end] = cnt++;
        }
        //从右至左
        for (int i = end-1; i >= start ; i--) {
            ans[end][i] = cnt++;
        }
        //从下至上
        for (int i = end-1; i >= start+1 ; i--) {
            ans[i][start] = cnt++;
        }
        start++;end--;
        loop--;
    }
    if(n%2 != 0){
        ans[n/2][n/2] = cnt;
    }
    return ans;
}

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

螺旋矩阵

/**
     *  螺旋矩阵 leetcode-54
     * @param matrix
     * @return
     */
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    int column = matrix[0].length; //列数
    int row = matrix.length; //行数
    int loop = column*row;
    int start = 0,endY = column-1,endX = row-1;
    while (loop > 0){
        //从左至右
        for (int i = start; i <= endY; i++) {
            ans.add(matrix[start][i]);
            loop--;
        }
        if(loop == 0) break;
        //从上至下
        for (int i = start+1; i <= endX ; i++) {
            ans.add(matrix[i][endY]);
            loop--;
        }
        if(loop == 0) break;
        //从右至左
        for (int i = endY-1; i >= start ; i--) {
            ans.add(matrix[endX][i]);
            loop--;
        }
        if(loop == 0) break;
        //从下至上
        for (int i = endX-1; i >=start+1 ; i--) {
            ans.add(matrix[i][start]);
            loop--;
        }
        if(loop == 0) break;
        start++;
        endX--;endY--;
    }
    return ans;
}
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