上岸算法 I LeetCode Weekly Contest 234解题报告

* @8 p) z* c8 r# [  b9 B

上岸算法

任何只教知识的课程都是耍流氓

我们直击上岸

关注我们，第一时间获得大厂面试真题讲解

9 W6 r% g- [+ N$ X! I

No.1

字符串中不同整数的数目

解题思路

使用正则表达式去掉非数字字符和每个字符串的前导 0 即可。

代码展示

1. class Solution {
   / y2 s2 ]! x  k
2.     public int numDifferentIntegers(String word) {
   2 U2 v' w* ^3 e5 J! s  {
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   
4.         Set<String> set = new HashSet<>();
   
5.         for (String num : nums) {
   
6.             if (!num.equals("")) {
   9 q3 h- Z" o  G7 h2 M) H; |9 q& `  R
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
   # q8 O4 N, |; U
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   
9.                 set.add(trimLeadingZero);
   2 R5 ^9 l8 K5 t- k0 G
10.             }
    
11.         }
    
12.         return set.size();
    
13.     }
    
14. }

复制代码

7 M4 r8 t5 N& f4 Q

No.2

还原排列的最少操作步数

7 o: K; P) n: C2 U- I

解题思路

模拟还原过程。

; u( p) P) v% [$ ^

代码展示

1. class Solution {
   ( R7 T/ _" X; ]2 j# A! m
2.     public int reinitializePermutation(int n) {
   
3.         int[] perm = new int[n];
   ; @9 I: |  o3 G4 U
4.         for (int i = 0; i < n; i++) {
   . L& H, ?9 o5 H3 c# t" W
5.             perm = i;
   
6.         }
   
7.         int count = 1;
   3 @* t# _. V+ x2 U+ z% l
8.         perm = conv(perm);
   4 U/ K3 s9 l3 k$ R$ k
9.         while (!check(perm)) {
   0 R' F6 Y) S! Y% o! B. `, K
10.             perm = conv(perm);
    
11.             count++;
    - n# Y* U& V* e- T/ m3 D6 C
12.         }
    
13.         return count;
    
14.     }
    
15. 
    ) y# t. s* [1 I, j
16.     boolean check(int[] perm) {
    8 A! C. ^) M. {1 R$ N2 m
17.         for (int i = 0; i < perm.length; i++) {
    ' Y3 h" x& ]4 j5 [  p
18.             if (perm != i) {
    
19.                 return false;
    9 ?1 Q2 U5 _3 E9 o
20.             }
    
21.         }
    
22.         return true;
    / w5 {; j7 @6 O- e
23.     }
    
24. 
    5 x: q# W: w& Z# q" W4 ~
25.     int[] conv(int[] perm) {
    % K0 K9 m. V$ p. E& W
26.         int[] result = new int[perm.length];
    
27.         for (int i = 0; i < perm.length; i++) {
    9 C$ w# }8 v, {# k8 c* i4 X
28.             if (i % 2 == 0) {
    
29.                 result = perm[i / 2];
    
30.             } else {
    
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    
32.             }
    6 P* r. v1 g5 B2 y5 D
33.         }
    
34.         return result;
    ) _$ i, `5 v8 K* R4 r6 O
35.     }
    
36. }

复制代码

No.3

替换字符串中的括号内容

解题思路

使用 Map 储存 knowledge，然后查找替换即可。
7 z  K' S' m7 _" N" y

代码展示

1. class Solution {
   - T# ]7 o; e) {* s2 m# w
2.     public String evaluate(String s, List<List<String>> knowledge) {
   
3.         Map<String, String> map = new HashMap<>();
   
4.         for (var kv : knowledge) {
   
5.             map.put(kv.get(0), kv.get(1));
   $ r0 ^) F( I* k; a8 B0 U/ D
6.         }
   
7.         StringBuilder sb = new StringBuilder();
   
8.         for (int i = 0; i < s.length(); i++) {
   * c& [: ]" b/ U) x
9.             if (s.charAt(i) != '(') {
   
10.                 sb.append(s.charAt(i));
    4 z7 a+ l- j1 [% L( g& |0 t
11.                 continue;
    
12.             }
    
13.             int j = i + 1;
    & s7 c! P- B. J/ n) T3 V
14.             while (s.charAt(j) != ')') {
    8 C9 ^& j1 J2 Y  Y( r7 Q
15.                 j++;
    
16.             }
    7 I5 F4 r5 ^$ h/ P0 ~2 R$ ~% @$ C! b3 T
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    
18.             i = j;
    
19.         }
    
20.         return sb.toString();
    , E; q$ v# t0 K
21.     }
    ( w. R; t. W( D% |# j
22. }
    

复制代码

No.4

好因子的最大数目

解题思路

假如 n 有质因子 a, a, a, ..., b, b, b, ..., c, c, c...，那么它的一个好因子 x 必定至少由一个 a、一个 b、一个 c 组成。所以 n 的好因子数量就是 numsOfA * numsOfB * numsOfC
( R8 g7 b3 g" ]* R/ F

那么该题目就等价于：将 primeFactors 拆分成若干个数的和，使这些数的和乘积最大。

证明思路参考：https://blog.csdn.net/nameofcsdn/article/details/53333542

$ h1 Y% y# ?' N7 i4 m3 G* }/ U* U+ w

代码展示

1. class Solution {
   
2.     public int maxNiceDivisors(int primeFactors) {
   
3.         int k = ((primeFactors - 2) % 3) + 2;
   
4.         int num3 = (primeFactors - k) / 3;
   
5.         long mod = (long) (1e9 + 7);
   / N4 I4 X( V* h( y: y1 D/ s5 G' l
6.         long res = k * pow(3, num3, mod) % mod;
   
7.         return (int) res;
   $ O4 m4 }* `3 h. ~$ k8 |
8.     }
   
9. 
   ; @9 T1 I8 S7 B( t- B
10.     long pow(long x, long y, long mod) {
    
11.         if (y == 0) {
    
12.             return 1;
    + s, w0 H6 C) w7 V, O9 m
13.         }
    
14.         long half = pow(x, y >> 1, mod);
    / l. r/ Q9 U8 ^
15.         if ((y & 1) != 0) {
    
16.             return half * half * x % mod;
    $ k+ d, d2 D$ C( \
17.         }
    
18.         return half * half % mod;
    , d& p4 T' h5 m; v( J
19.     }
    
20. }

复制代码

! O+ m. T" i, `+ T2 u
; Y6 [  B1 ?3 x/ v0 Q6 X上岸DS秋招最新大厂面经公开课

活动介绍：为北美同学免费提供大厂面试官面经重点，为你在线提分
: x  }. G- c8 W9 d活动时间：2021/4/5-2021/4/26

活动全程  免费 免费 免费！！！

活动安排：

4/05  小k 老师（资深FLAG 面试官）:简历项目深挖

4/17  莎莎老师（资深数据科学家）：上岸大厂有哪些技巧

4/19  小春老师（FLAG 现职工程师）：推荐系统公开课

4/26  小雨老师（资深数据科学家）：SQL 带刷专场

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群