上岸算法 I LeetCode Weekly Contest 241解题报告【含秋招咨询群】

2021 秋招时间线如下，建一个求职免费咨询群，群内将有FLAG 面试官就秋招趋势/如何准备等问题亲自答疑

6 i& k) y2 J* ]" h0 n/ n

No.1 找出所有子集的异或总和再求和

解题思路

通过二进制位枚举一个集合的所有子集。

代码展示

1. class Solution {
   ) [& i) Q: W7 N. z8 T
2.     public int subsetXORSum(int[] nums) {
   
3.         int n = nums.length;
   ; y& @8 R" t. O- q
4.         int sum = 0;
   
5.         for (int i = 0; i < (1 << n); i++) {
   
6.             int xor = 0;
   
7.             for (int j = 0; j < n; j++) {
   4 S4 A8 o( _' F% l( I9 M
8.                 if (((1 << j) & i) > 0) {
   
9.                     xor ^= nums[j];
   
10.                 }
    ) z4 l  O, D1 l" Q$ W9 c
11.             }
    ! @; h" g. \3 N7 R* @
12.             sum += xor;
    
13.         }
    . [; T3 u# _! Q' }8 ?- {0 F
14.         return sum;
    
15.     }
    * u* r- n% S# L, t
16. }

复制代码

No.2 构成交替字符串需要的最小交换次数

解题思路

如果 0 和 1 相差的数量超过 1 则直接返回 -1

如果 0 和 1 一样多，那么最终结果有两种情况，反之最终结果是唯一的。只需要统计出多少个数字位置不对即可，因为每次交换都可以减少 2 个位置不对的数字的数量。

代码展示

1. class Solution {
   * V; e* V( a+ `
2.     public int minSwaps(String s) {
   
3.         char[] str = s.toCharArray();
   . ^9 |- u, ]# V3 L" i& [& r8 v8 t
4.         int cnt = 0;
   
5.         for (int i = 0; i < str.length; i++) {
   
6.             if (str[i] == '0') {
   
7.                 cnt++;
   ; \) F! J: O; M; t( V7 X6 \
8.             } else {
   9 q% S6 G0 n9 p, }4 Y# ^
9.                 cnt--;
   1 [0 f- y) N# Y( ~( h
10.             }
    4 w* R* a. V3 d$ d: }" U& h& Z; e
11.         }
    ' v% @/ N6 ~) w: Y, ^9 m. X# e
12.         if (cnt > 1 || cnt < -1) {
    1 J6 ~3 }) ~- e6 O  P: K
13.             return -1;
    : A' N- y7 @) a* i% g( q1 \
14.         }
    ) K+ @4 ~5 H- @, B/ l; `4 a
15.         if (cnt == 0) {
    
16.             return Math.min(minSwaps(str, 0), minSwaps(str, 1));
    : N" _7 n: `/ N0 B8 S+ M6 n& d
17.         }
    - i$ y: z) `. }$ h& a
18.         if (cnt == 1) {
    # p3 ^/ w+ ^9 M: E2 Y$ Y
19.             return minSwaps(str, 0);
    7 A7 x0 S$ `1 b
20.         }
    
21.         return minSwaps(str, 1);
    : Z( L' R7 L9 G1 x! {/ k' I) N# v
22.     }
    
23. 
    / b3 h4 q0 g) b- k" }, C
24.     int minSwaps(char[] str, int start) {
      ~! j# m6 M  C9 t; C. C
25.         int cnt = 0;
    9 x. X! |6 n  A5 Q
26.         for (int i = 0; i < str.length; i++) {
    
27.             if (str[i] != '0' + start) {
    
28.                 cnt++;
    
29.             }
    & U7 s8 @6 q! `/ Y, u- w, s2 M
30.             start ^= 1;
    
31.         }
    
32.         return cnt / 2;
    6 S* l+ V" q( G3 V$ v$ W
33.     }
    " E2 g5 d5 z* C- t) D( j/ N3 j' W
34. }

复制代码

No.3 找出和为指定值的下标对

解题思路

根据数据范围，使用 Map 维护 nums2 中各个数值的数量，每次统计时枚举 nums1 即可。

代码展示

1. class FindSumPairs {
   # A9 E$ ~& l# E2 B
2. 
     _( e+ v( s8 h# P1 Y
3.     Map<Integer, Integer> count2;
   
4.     int[] nums1;
   
5.     int[] nums2;
   / N" S6 F* h. D0 ^0 Q5 O$ v0 x7 q
6. 
   
7.     public FindSumPairs(int[] nums1, int[] nums2) {
   4 z" m4 c- X$ R8 Y3 {3 V
8.         count2 = new HashMap<>();
   
9.         this.nums1 = nums1;
   
10.         this.nums2 = nums2;
    9 a4 a$ r+ a4 K' s/ v
11.         for (int num : nums2) {
    1 N+ I# A- }9 ~  @) Y
12.             count2.put(num, count2.getOrDefault(num, 0) + 1);
    . t' F0 c8 x; {4 q, d5 p, E# H. b! x
13.         }
    
14.     }
    . S  s0 a; }  A% c& V: k1 W
15. 
    
16.     public void add(int index, int val) {
    
17.         count2.put(nums2[index], count2.getOrDefault(nums2[index], 0) - 1);
    
18.         nums2[index] += val;
    5 B- c+ S  H7 E( X/ Q. K: E4 J
19.         count2.put(nums2[index], count2.getOrDefault(nums2[index], 0) + 1);
    
20.     }
    " D' @2 H4 \, W
21. 
    
22.     public int count(int tot) {
    1 y5 M1 a: V/ ?  ]; N, ~
23.         int res = 0;
    
24.         for (int num : nums1) {
    
25.             res += count2.getOrDefault(tot - num, 0);
    
26.         }
    $ S5 `% C5 o9 |$ y& O4 |3 W8 z
27.         return res;
    
28.     }
    
29. }

复制代码

No.4 恰有 K 根木棍可以看到的排列数目

解题思路

动态规划，dp[n][k] = dp[n-1][k-1]*(n-1) + dp[n-1][k]

思考过程就是从高到低依次放木板。

代码展示

1. class Solution {
   
2.     public int rearrangeSticks(int n, int k) {
   # T+ |- r: T' U" ^: G# b
3.         long[][] dp = new long[2000][2000];
   
4.         long mod = 1000000007;
   2 J5 B( Z9 n9 h2 e1 }" i  T
5.         dp[1][1] = 1;
   
6.         for (int i = 2; i <= n; i++) {
   4 w& R- U( r9 }  Z0 H, p% s' f5 U
7.             for (int j = 1; j <= i; j++) {
   9 K, n! P. a: D% N( \' `
8.                 dp[i][j] = (dp[i - 1][j] * (i - 1) + dp[i - 1][j - 1]) % mod;
   - L. q. C: Y# H' K0 T( H
9.             }
   / E( u7 L$ X6 p0 k& M8 q0 s" _
10.         }
    
11.         return (int) dp[n][k];
    
12.     }
    ' j4 E; I, i: H; N
13. }

复制代码

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

上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。

7 D& }) W% ]3 v# X' X# v
& O. i, U; R* x+ l! y3 u6 e
0 j2 z- t9 j0 J$ C9 s