0%

leetcode-第195场周赛

Posted on Edited on In ,

第195场周赛

判断路径是否相交

image1

使用集合来存储已经走过的点的坐标，如果该点的坐标已经在集合中出现，那么说明有相交的路径，否则就没有。初始坐标为$(0,0)$。若方向为N，则横坐标y加1，方向为S，横坐标减1。若方向为E，则横坐标x加1，方向为W，横坐标减1。

1
class Solution {
2
    public boolean isPathCrossing(String path) {
3
        int len = path.length();
4
        int row = 0;
5
        int col = 0;
6
      	//也可以使用String来存储坐标
7
        Set<List<Integer>> set = new HashSet<List<Integer>>();
8
        List<Integer> list = new ArrayList<>();
9
        list.add(row);
10
        list.add(col);
11
        set.add(list);
12
        for(int i=0; i<len; i++){
13
            char c = path.charAt(i);
14
            if(c == 'N'){
15
                col++;
16
            }else if(c == 'S'){
17
                col--;
18
            }else if(c == 'E'){
19
                row++;
20
            }else{
21
                row--;
22
            }
23
            List<Integer> list1 = new ArrayList<>();
24
            list1.add(row);
25
            list1.add(col);
26
            if(set.contains(list1)){
27
                return true;
28
            }else{
29
                set.add(list1);
30
            }
31
        }
32
        return false;
33
    }
34
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。

##检查数组对是否可以被 k 整除

image2

image3

k的所有余数都在$[0,k-1]$之间，如果余数为$i$的个数和余数为$k-i$的个数相同，那么它们就能进行配对被k整除，所以只需要按余数分类并统计个数。对于余数为0的情况，需要看余数为0的个数是否为偶数，若为偶数，就可以自己和自己配对，若为奇数，那么最后就会剩余一个从而无法配对。对于余数出现负数的情况，就先加上k，再对k取余。

1
class Solution {
2
    public boolean canArrange(int[] arr, int k) {
3
        int n = arr.length;
4
        int[] mod = new int[k];
5
        for(int i=0; i<n; i++){
6
            int num = (arr[i]%k+k)%k;
7
            mod[num]++;
8
        }
9
        for(int i=1; i<k/2; i++){
10
            if(mod[i] != mod[k-i]){
11
                return false;
12
            }
13
        }
14
        return mod[0]%2==0;
15
    }
16
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。

满足条件的子序列数目

image4

image5

方法一：二分查找

  • 排序。
  • 遍历左端点$i$，二分查找出小于等于$target-nums[i]$的最后一个下标$j$。
  • 包含左端点$i$的满足条件的所有子序列个数为$2^{j-i}$个。

如果$j-i$的数很大的话，那么直接用Math.pow()的话会很慢而且数会很大，即使是用double也存储不下。因此我们使用一个长度为$nums.length$的数组来存储2的幂次方取模的结果。

1
class Solution {
2
    public int numSubseq(int[] nums, int target) {
3
        Arrays.sort(nums);
4
        if(nums[0]*2 > target){
5
            return 0;
6
        }
7
        int n = nums.length;
8
        int res = 0;
9
        int mode = (int) 1e9 + 7;
10
        //快速幂，存储2的幂次方取模
11
        int[] pow = new int[n];
12
        pow[0] = 1;
13
        for(int i=1;i<n;i++){
14
            pow[i] = pow[i-1] * 2;
15
            pow[i] = pow[i] % mode;
16
        }
17
        for(int i=0; i<n; i++){
18
            int pos = binarySearch(nums, target-nums[i]);
19
            if(pos>=i){
20
                res += pow[pos-i];
21
                res %= mode;
22
            }
23
        }
24
        return res;
25
    }
26
    //二分查找
27
    public int binarySearch(int[] nums, int target) {
28
        int low = 0, high = nums.length;
29
        while (low < high) {
30
            int mid = (high - low) / 2 + low;
31
            if (mid == nums.length) {
32
                return mid;
33
            }
34
            int num = nums[mid];
35
            if (num <= target) {
36
                low = mid + 1;
37
            } else {
38
                high = mid;
39
            }
40
        } 
41
        return high-1;
42
    }
43
}

复杂度分析：

  • 时间复杂度：$O(nlogn)$。
  • 空间复杂度：$O(n)$。

方法二：双指针

  • 排序
  • 双指针，左指针left指向下标0，右指针right指向下标nums.length-1。当$left<=right$时，如果$nums[left]+nums[right]<=target$时，说明满足条件，那么结果加上$2^{right-left}$，接着将左指针右移。否则就将右指针左移。
1
class Solution {
2
    public int numSubseq(int[] nums, int target) {
3
        Arrays.sort(nums);
4
        if (nums[0] * 2 > target) {
5
            return 0;
6
        }
7
        int left = 0;
8
        int right = nums.length - 1;
9
        int res = 0;
10
        int[] pow = new int[nums.length];
11
        pow[0] = 1;
12
        int mode = (int) 1e9 + 7;
13
        for (int i = 1; i < nums.length; i ++) {
14
            pow[i] = pow[i-1] * 2;
15
            pow[i] %= mode;
16
        }
17
        while (left <= right) {
18
            if (nums[left] + nums[right] <= target) {
19
                res += pow[right - left];
20
                res %= mode;
21
                left++;
22
            }
23
            else {
24
                right--;
25
            }
26
        }
27
        return res;
28
    }
29
}

复杂度分析：

  • 时间复杂度：$O(nlogn)$。
  • 空间复杂度：$O(n)$。

满足不等式的最大值

image6

image7

由于当$i<j$时，$x_i < x_j$，所以$y_i + y_j + |x_i - x_j|$可以变为$y_i + y_j + x_j - x_i$即$(x_j + y_j) + (y_i - x_i)$。所以题目变为对于某一下标$j$时，找出$y_i - x_i$的最大值，同时满足$|x_i - x_j|<=k$。可以使用单调队列解决此问题，流程如下。

  • 维护一个单调队列，队首为$y-x$最大的横坐标$x_{head}$。
  • 对于点$j$，首先从队首依次删除不满足$x_j - x_{head}>k$的点，$x_{head}$为队首。
  • 之后取出队首$x_{head}$，计算$x_j+y_j+y_{head}-x_{head}$，更新ans。
  • 维护队列单调性，更新队列，从队尾开始删除$y_{tail}-x_{tail} < y_j - x_j$的元素，删除完毕后将点$j$插入队尾。
1
class Solution {
2
    public int findMaxValueOfEquation(int[][] points, int k) {
3
        Deque<Integer> deque = new ArrayDeque<>();
4
        int ans = Integer.MIN_VALUE;
5
        for(int i=0; i<points.length; i++){
6
            while(!deque.isEmpty() && (points[i][0]-points[deque.peekFirst()][0]>k)){
7
                deque.pollFirst();
8
            }
9
            if(!deque.isEmpty()){
10
                int head = deque.peekFirst();
11
                ans = Math.max(ans, points[head][1]-points[head][0]+points[i][0]+points[i][1]);
12
            }
13
            while(!deque.isEmpty() && isLess(points, deque.peekLast(), i)){
14
                deque.removeLast();
15
            }
16
            deque.offerLast(i);
17
        }
18
        return ans;
19
    }
20
21
    public boolean isLess(int[][] points, int tail, int i){
22
        if(points[tail][1]-points[tail][0] < points[i][1]-points[i][0]){
23
            return true;
24
        }else{
25
            return false;
26
        }
27
    }
28
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。