No.1 判断路径是否相交

★解题思路

使用一个 Set 记录已经走过的点即可.

代码展示

class Solution { 
   public boolean isPathCrossing(String path) { 
       // 一个点 (x, y), 使用 x * 100000 + y 即可唯一表示这个点 
       // 因为题目说明操作不超过 10^4, 即 x, y 的绝对值不会超过 10^4 
       Set<Long> set = new HashSet<>(); 
       char[] str = path.toCharArray(); 
       long x = 0, y = 0; 
       set.add(x * 100000 + y); 
       for (char c : str) { 
           switch (c) { 
               case 'N' -> x++; 
               case 'S' -> x--; 
               case 'W' -> y--; 
               case 'E' -> y++; 
           } 
           if (set.contains(x * 100000 + y)) { 
               return true; 
           } 
           set.add(x * 100000 + y); 
       } 
       return false; 
   } 
}

No.2 检查数组对是否可以被k整除

★解题思路

详情见注释.

代码展示

class Solution { 
   public boolean canArrange(int[] arr, int k) { 
       int n = arr.length; 
       for (int i = 0; i < n; i++) { 
           // 将数组的元素转换成 [0, k) 范围内的值 
           // % 运算不影响两个数相加后是否可以被 k 整除  
           arr[i] = ((arr[i] % k) + k) % k; 
       } 
       // 排序 
       Arrays.sort(arr); 
       // 统计 0 的个数 
       int zero = 0; 
       while (zero < n && arr[zero] == 0) zero++; 
       if (zero % 2 != 0) return false; // 奇数个 0, 非法 
       // 非 0 的必须两两成对, 相加等于 k (即原本的两个数相加可以被 k 整除) 
       for (int left = zero, right = n - 1; left < right; ) { 
           if (arr[left] + arr[right] == k) { 
               left++; 
               right--; 
           } else { 
               return false; 
           } 
       } 
       return true; 
   } 
}

No.3 满足条件的子序列数目

★解题思路

详情见注释.

代码展示

class Solution { 
   public int numSubseq(int[] nums, int target) { 
       Arrays.sort(nums); 
       long res = 0; 
       // 依次计算以每个元素为最小值时的序列个数 
       for (int left = 0, right = nums.length - 1; left <= right; left++) { 
           while (left <= right && nums[left] + nums[right] > target) right--; 
           if (left <= right && nums[left] + nums[right] <= target) { 
               // 以 left 为最小值时, [left, right] 之间的任意元素可以做最大值 
               // 以 r 为最大值时, 子序列有 2 ^ (r - left - 1) 个, 特殊地, left == r 时有 1 个子序列 
               // 即 1 + 1 + 2 + 4 + ... + 2^(right-left-1) = 2^(right-left) 
               // 不能直接用 1 << x 来求 2 ^ x, 可能会溢出 
               res += mypow(2L, right - left, 1000000007L); 
               res %= 1000000007L; 
           } 
       } 
       return (int)res; 
   } 
   // 递归式的快速幂 
   long mypow(long x, int y, long mod) { 
       if (y == 0) return 1L; 
       if (y == 1) return x % mod; 
       long t = mypow(x, y / 2, mod); 
       if (y % 2 == 0) return t * t % mod; 
       else return (t * x % mod) * t % mod; 
   } 
}

No.4 满足不等式的最大值

★解题思路

单调队列.

队列中保存 x 坐标比当前点小的点, 同时越靠前的点越优秀 (与当前点计算得到的答案越大).

代码展示

class Solution { 
   public int findMaxValueOfEquation(int[][] points, int k) { 
       LinkedList<int[]> queue = new LinkedList<>(); 
       int n = points.length; 
       int res = Integer.MIN_VALUE; 
       queue.add(points[0]); 
       for (int i = 1; i < n; i++) { 
           // 将 x 坐标超出范围的点出队 
           while (!queue.isEmpty() && points[i][0] - queue.getFirst()[0] > k) queue.pollFirst(); 
           // 队不为空, 则用队首与当前点计算答案 
           if (!queue.isEmpty()) { 
               int[] p = queue.getFirst(); 
               res = Math.max(res, points[i][1] + p[1] + Math.abs(points[i][0] - p[0])); 
           } 
           // 当前点入队前, 判断是否比队尾优秀 
           // 若比队尾优秀, 那么将队尾出队, 以维持单调性 
           // 因为计算方式为 y1+y2+|x1-x2|, 所以只要 y 的增长超过了 x 的增长, 那么当前点就比队尾更优秀 
           while (!queue.isEmpty() && points[i][1] - queue.getLast()[1] > points[i][0] - queue.getLast()[0]) queue.pollLast(); 
           queue.add(points[i]); 
       } 
       return res; 
   } 
}

杭州上岸算法网络科技有限公司

上岸科技，一家位于西雅图致力于帮助北美小伙伴们上岸的团体。

团队主要由一群怀揣情怀于美国高校毕业的一线IT公司工程师构成。我们坚持采用小班课形式，并结合大量”面试式“和”白板“的教学和交流形式，最终帮助大家提升求职成功概率同时大大减少刷题的痛苦。

正如我们的信仰：我们教的是如何上岸而不仅是算法。