找回密码
 注册账号
img_loading
智能检测中
置顶:如何加入2024届新生微信群

[吹水聊天] 上岸算法 I LeetCode Weekly Contest 241解题报告【含秋招咨询群】

上岸算法 回复:0 | 查看:2512 | 发表于 2021-5-17 07:19:53 |阅读模式 |复制链接

UWCSSA提醒您:

警惕网络诈骗与盗号,不要在他人发送的网站中输入密码,换汇或付款时请小心诈骗。

为了避免个人信息泄漏,建议在帖子中使用不常用的邮箱,或使用私信发送联系方式(点击对方的头像,然后“发送消息”)。

帖子通过审核只代表内容不违规,CSSA 不会验证内容的真实性。请谨防诈骗。


7 v1 \; D9 F( f; n: I6 _4 i
2021 秋招时间线如下,建一个求职免费咨询群,群内将有FLAG 面试官就秋招趋势/如何准备等问题亲自答疑

) \" S" u- C) t) }6 f# U
9 N% L# D% b1 {* [* e

# N% \- I7 C0 D
/ }# j( V( ^1 N- F0 z8 X/ R
No.1 找出所有子集的异或总和再求和
解题思路
通过二进制位枚举一个集合的所有子集。
代码展示
  1. class Solution {
    & K" r) `! g1 u4 E
  2.     public int subsetXORSum(int[] nums) {8 t. k# M4 t4 x& _0 P8 _
  3.         int n = nums.length;
    7 Z8 C# ^& y# R- n, t
  4.         int sum = 0;
    . A0 e6 F" b: K: X  \- n* s* q$ c2 m
  5.         for (int i = 0; i < (1 << n); i++) {6 I: s7 r" z; X
  6.             int xor = 0;
    " F. A+ h2 X. H! R' ?8 c% C& L2 p
  7.             for (int j = 0; j < n; j++) {& \4 N2 D: l6 I7 @9 x+ B0 T7 A
  8.                 if (((1 << j) & i) > 0) {
    ! u2 ]* w' U# K8 m2 v# H* d
  9.                     xor ^= nums[j];
    ' M, y: n7 `, d- D9 X
  10.                 }1 O7 e$ s( g1 ?$ P, D7 B6 t
  11.             }
    % H8 U# R* F+ Z" F
  12.             sum += xor;: f: g- @: }3 ?/ g" Y
  13.         }' o2 v- S) c9 `" R( X* f
  14.         return sum;4 B) a! R- u  P* o7 u. O
  15.     }: }, d  C  C6 ?& ^
  16. }
复制代码
No.2 构成交替字符串需要的最小交换次数
解题思路
如果 0 和 1 相差的数量超过 1 则直接返回 -1
如果 0 和 1 一样多,那么最终结果有两种情况,反之最终结果是唯一的。只需要统计出多少个数字位置不对即可,因为每次交换都可以减少 2 个位置不对的数字的数量。
代码展示
  1. class Solution {" |$ A7 B5 w7 Z2 t: J
  2.     public int minSwaps(String s) {5 D1 I, m7 f  p: w4 s1 U6 N
  3.         char[] str = s.toCharArray();  M% A. v( f3 D! z
  4.         int cnt = 0;
    % ^+ |6 ^8 x+ T. W/ {- F
  5.         for (int i = 0; i < str.length; i++) {# g4 n; T& h6 f# ]' z
  6.             if (str[i] == '0') {; T, f: Z# K* K1 q) Y3 M
  7.                 cnt++;
    " j3 b" p! L4 n, [7 m9 _- [; m- {
  8.             } else {
    / Y6 x, i/ n  y- T7 Y
  9.                 cnt--;6 a- q* E$ A2 E* |
  10.             }3 W7 g% b) M! a$ x6 |+ S4 M
  11.         }
    ) P& ~8 g3 i# @' t; ?/ J& `) F8 `
  12.         if (cnt > 1 || cnt < -1) {+ `& S% c$ y' p0 P- J- L
  13.             return -1;
    - c; a7 K$ p' f% b- N4 N
  14.         }
    5 k) {( D% P* p+ Y- z1 v
  15.         if (cnt == 0) {6 p2 {5 x( z8 a9 o! r
  16.             return Math.min(minSwaps(str, 0), minSwaps(str, 1));
    3 s; S8 Q/ p+ \8 P1 a
  17.         }
    9 E4 G4 d7 t# \, Z; M7 U" Q8 S
  18.         if (cnt == 1) {
    4 E2 G0 S$ j, z/ Q& f8 j, _3 h* _
  19.             return minSwaps(str, 0);
    + y+ w2 e4 U7 ], B; \7 o
  20.         }
    # C* _8 H: Z' |+ C' `3 i
  21.         return minSwaps(str, 1);9 j7 n% X' x5 P4 ?
  22.     }
    / J0 l! ~: l! Y9 X

  23.   b1 P* l3 E( L/ F- P
  24.     int minSwaps(char[] str, int start) {( x( g2 i& j, L8 r2 C0 P; d$ e
  25.         int cnt = 0;
    3 `$ v4 Z+ A  }0 Y2 T* G
  26.         for (int i = 0; i < str.length; i++) {
    7 z8 }$ a7 U3 ?) A
  27.             if (str[i] != '0' + start) {8 q4 S/ |2 [3 S- b
  28.                 cnt++;
    5 U! [# o( L! u5 e8 r
  29.             }% ]4 k* \7 M7 ]: Z7 O
  30.             start ^= 1;
    ! I! d1 \% R5 S& Q5 u
  31.         }9 }8 a" _0 Q8 J. a! L
  32.         return cnt / 2;$ }) A, o7 N" c% c
  33.     }
    . b( P* T( F7 ?8 Y8 G$ T
  34. }
复制代码
No.3 找出和为指定值的下标对
解题思路
根据数据范围,使用 Map 维护 nums2 中各个数值的数量,每次统计时枚举 nums1 即可。
代码展示
  1. class FindSumPairs {
    / ]- I4 q$ V$ h: q( p" |/ P

  2. ! i( t% M. k- e- a; N
  3.     Map<Integer, Integer> count2;
    / e: |" Y% R2 N: l# P8 |+ s$ b
  4.     int[] nums1;
    ) U2 P6 [: h/ z5 p8 ]0 h
  5.     int[] nums2;  A" s  F9 }1 U' k7 a' x

  6. 6 j$ ]" `' I' a
  7.     public FindSumPairs(int[] nums1, int[] nums2) {7 A! R' F& X  p1 k" A
  8.         count2 = new HashMap<>();
    + b- X' T8 M9 q
  9.         this.nums1 = nums1;
    2 k5 B2 o1 l- h1 w4 S
  10.         this.nums2 = nums2;1 Q' ?9 o! q" P% F
  11.         for (int num : nums2) {
    0 n- P4 x' g  G
  12.             count2.put(num, count2.getOrDefault(num, 0) + 1);
    ( k+ Z2 t' l' K9 \5 f& l
  13.         }
    1 p% ]4 z+ j$ `) X1 G
  14.     }
    ( Y$ P7 i- ~8 Q. l# o* i* J

  15. 9 y+ i" o# h  L0 l$ L
  16.     public void add(int index, int val) {2 @6 M) ]$ l; z+ j: Y% y% c( j4 P7 G. ]
  17.         count2.put(nums2[index], count2.getOrDefault(nums2[index], 0) - 1);
    7 B0 c) \0 E) v: C! H: l6 z
  18.         nums2[index] += val;# n! [) d% B" H$ }. B* |& x1 C9 @3 p
  19.         count2.put(nums2[index], count2.getOrDefault(nums2[index], 0) + 1);
    $ q+ O, z2 n" s0 U8 F7 L) x% f$ ?
  20.     }; m+ A8 N! g& T  t

  21. 8 s9 j" Z: T1 q* T# k! v6 l& c
  22.     public int count(int tot) {4 `/ E& K5 z, x8 _4 {
  23.         int res = 0;2 J0 ]( D7 l4 E% U) U+ y* j
  24.         for (int num : nums1) {
    + c6 H) F; X1 \2 F
  25.             res += count2.getOrDefault(tot - num, 0);1 f; d9 t; q# b1 {2 t- z
  26.         }: c% o% v/ c8 o; L4 g
  27.         return res;
    . F/ B1 g7 x- ]6 W, F
  28.     }5 @/ y- v4 q# r/ N+ g. |
  29. }
复制代码
No.4 恰有 K 根木棍可以看到的排列数目
解题思路
动态规划,dp[n][k] = dp[n-1][k-1]*(n-1) + dp[n-1][k]
思考过程就是从高到低依次放木板。
代码展示
  1. class Solution {8 X$ ^- L3 t; G; }( r5 N0 O
  2.     public int rearrangeSticks(int n, int k) {7 j0 W/ `4 b# X) Q$ n4 w
  3.         long[][] dp = new long[2000][2000];" F! Q+ f, h7 w9 a/ X& _$ C, A
  4.         long mod = 1000000007;
    3 S5 e6 u6 G$ H4 [# ?, D3 I0 |% L
  5.         dp[1][1] = 1;
    1 P, ^2 j9 E/ O/ ^. t+ ^
  6.         for (int i = 2; i <= n; i++) {  z5 s# l  i$ f3 ^) u* K1 {# D7 Z0 s
  7.             for (int j = 1; j <= i; j++) {( o4 R. z, y* p& j, n  R' a7 V
  8.                 dp[i][j] = (dp[i - 1][j] * (i - 1) + dp[i - 1][j - 1]) % mod;8 S4 \/ B9 X9 [9 z7 ]( G$ H+ {
  9.             }
    9 T5 H/ _( o) k# T
  10.         }
    7 m* ~/ r% ^# C/ n) P
  11.         return (int) dp[n][k];: g- D/ C! y0 @& a* \  i
  12.     }0 S- R) E( p+ Z) F5 V
  13. }
复制代码
上岸算法网络科技有限公司
上岸算法网络科技有限公司是一家致力于用高质量,高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量,高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟,用最高效,经济,合理的方式帮助更多学生快速找到梦寐以求的工作。

' w. ^/ G; m' _& Q3 N6 i4 `
; @9 I3 `$ k# {0 A8 p
( |6 d* v, W1 [+ s+ u/ o
# v! l: ]1 [1 ^- u

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

登录 发布 快速回复 返回顶部 返回列表