数组复习

Posted on Edited on

704 二分查找

左闭右开

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 search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] > target){
                right = mid;
            } else {
                left = mid + 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
23
24
25
class Solution {
    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;

        while (left <= right){
            int mid = left + ((right - left) >> 1);

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

        return -1;
    }
}

35 搜索插入位置

二分查找，输出mid或左值

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 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;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target) {
                return mid;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[] {-1, -1};
        int index = binarySearch(nums, target);
        if (index == -1) return new int[] {-1, -1};
        else {
            int left = index;
            int right = index;

            for (int i = index; i >= 0; i--){
                if (nums[i] == target) left--;
            }

            for (int i = index; i < nums.length; i++){
                if (nums[i] == target) right++;
            }

            return new int[] {left + 1, right - 1};

        }
        
    }
    private int binarySearch(int[] nums, int target){
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;
        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target){
                return mid;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return -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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[] {getLeftBorder(nums, target), getRightBorder(nums, target)};
    }

    private int getLeftBorder(int[] nums, int target){
        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target){
                for (int i = mid; i >= left; i--){
                    if (nums[mid] == target) mid--;
                }

                return mid + 1;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                right = mid;
            }
        } 

        return -1;
    }

    private int getRightBorder(int[] nums, int target){
        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target){
                for (int i = mid; i < right; i++){
                    if (nums[mid] == target) mid++;
                }

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

        return -1;
    }
}

69 x的平方根

注意返回的数字 是 右 - 1

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 mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;

        int left = 0;
        int right = x;
        while (left < right){
            int mid =  left + ((right - left) >> 1);
            long midSquare = (long) mid * mid;
            if (midSquare == (long) x){
                return mid;
            } else if (midSquare < x){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right - 1;
    }
}

367 有效的完全平方数

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 boolean isPerfectSquare(int num) {
        if (num == 0 || num == 1) return true;

        int left = 0;
        int right = num;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            long midS = (long) mid * mid;

            if (midS == (long) num) {
                return true;
            } else if (midS < num){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        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 slowIndex = 0;

        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if (nums[fastIndex] != val){
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
}

左右指针

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 left = 0;
        int right = nums.length - 1;

        for (left = 0; left <= right; left++){
            if (nums[left] == val){
                nums[left] = nums[right--];
                left--;
            }
        }

        return left;
    }
}

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

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int removeDuplicates(int[] nums) {
        int fastIndex = 0;
        int slowIndex = 1;

        for (fastIndex = 1; fastIndex< nums.length; fastIndex++){
            if (nums[fastIndex] != nums[slowIndex - 1]){
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }

        return slowIndex;
        
    }
}

283 移动零

快慢指针的另种用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void moveZeroes(int[] nums) {
        int fastIndex = 0;
        int slowIndex = 0;

        for (fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if (nums[fastIndex] != 0){
                nums[slowIndex++] = nums[fastIndex];
            }
        }

        for (int i = slowIndex; i < nums.length; i++){
            nums[i] = 0;
        }
    }
}

844 比较含退格的字符串

利用stringbuilder

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 boolean backspaceCompare(String s, String t) {
        s = getString(s);
        t = getString(t);
        return s.equals(t);
    }

    private String getString(String s){
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char i : chars){
            if (i == '#'){
                if (sb.length() != 0){
                    sb.delete(sb.length() - 1, sb.length());
                }
            } else {
                sb.append(i);
            }
        }

        return sb.toString();
    }
}

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
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        while (left <= right){
            int leftS =  nums[left] * nums[left];
            int rightS =  nums[right] * nums[right];

            if (leftS <= rightS) {
                result[index--] = rightS;
                right--;
            }
            else {
                result[index--] = leftS; 
                left++;
            }
        }

        return result;
    }
}

209 长度最小的子数组

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (right = 0; right < nums.length; right++){
            sum += nums[right];
            while (sum >= target){
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

904 水果成篮

利用HashMap计数，然后在hashmap里面为0时删除
记录length 比较最长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int totalFruit(int[] fruits) {
        int result = 0;
        Map<Integer, Integer> map = new HashMap<>();

        int left = 0; 
        int right = 0;
        for (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++;
            }
            result = Math.max(result, right - left + 1);
        }
            return result;
        } 
        
}

76 最小覆盖子串

利用两个hashmap记录次数，

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
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char i : t.toCharArray()){
            need.put(i, need.getOrDefault(i, 0) + 1);
        }

        int left = 0, right = 0;
        // valid character count;
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;
        
        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }

            while (valid == need.size()){
                if (right - left < len){
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);

                left++;

                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }

                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

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[][] result = new int[n][n];
        int start = 0;
        int count = 1;
        int offset = 1;
        int loop = n / 2;
        int i = 0, j = 0;
        while (loop-- > 0){
            for (j = start; j < n - offset; j++){
                result[start][j] = count++;
            }

            for (i = start; i < n - offset; i++){
                result[i][j] = count++;
            }

            for (;j > start; j--){
                result[i][j] = count++;
            }

            for (;i > start; i--){
                result[i][j] = count++;
            }
            start++;
            offset++;
        }

        if (n % 2 == 1){
            result[start][start] = count;
        }

        return result;

    }
}

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
       List<Integer> list = new ArrayList();
        int m = matrix.length, n = matrix[0].length;
        int rowSt = 0, colSt = 0, rowEnd = m - 1, colEnd = n - 1;
        while(list.size() < m * n){
            //For starting row addition
            for(int i = colSt; i <= colEnd; i++){
                list.add(matrix[rowSt][i]);
            }

            //To add last colm
            for(int i = rowSt + 1; i <= rowEnd; i++){
                list.add(matrix[i][colEnd]);
            }
            //To add last row
            if(rowSt != rowEnd){
                for(int i = colEnd - 1; i >= colSt; i--){
                    list.add(matrix[rowEnd][i]);
                }
            }
            //To add first colm
            if(colSt != colEnd){
                for(int i = rowEnd - 1; i >= rowSt + 1; i--){
                    list.add(matrix[i][colSt]);
                }
            }
            colSt++;
            colEnd--;
            rowSt++;
            rowEnd--;
        }
        return list;
    }
}