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

上岸算法

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

我们直击上岸

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

No.1

字符串中不同整数的数目

解题思路

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

0 q4 v# P5 Q, y+ L- ^

代码展示

1. class Solution {
   - }3 W" ?( x' I7 I1 D# N. u
2.     public int numDifferentIntegers(String word) {
   
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   ! {! I( V; Q; u( ?0 O& L
4.         Set<String> set = new HashSet<>();
   
5.         for (String num : nums) {
   4 t/ z; u7 m2 z, h: m) P. [. u
6.             if (!num.equals("")) {
   
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
   * n1 J- c' z5 R# w
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   5 H5 a& \2 U+ n8 a, e6 {6 E
9.                 set.add(trimLeadingZero);
   ( P# d( {3 K6 O( m# `/ @& M
10.             }
    & t* c$ P! B; l
11.         }
    ; h. `8 K: F& ^; Z# m" N* ~
12.         return set.size();
    9 u4 Q6 Y) X. A7 W, G# J
13.     }
    
14. }

复制代码

5 E) j  P+ @3 [

No.2

还原排列的最少操作步数

解题思路

模拟还原过程。

代码展示

1. class Solution {
   $ d4 Y" `& G" l" Y' j. I. W% h
2.     public int reinitializePermutation(int n) {
     ^7 ?  g, ]$ G7 v5 p; d  q
3.         int[] perm = new int[n];
   1 E6 P! `( r8 _3 m
4.         for (int i = 0; i < n; i++) {
   
5.             perm = i;
   
6.         }
   2 [5 f, e% A5 V/ t. K" t9 C
7.         int count = 1;
   
8.         perm = conv(perm);
   ! J4 u' X- d  e) w$ `' K- {
9.         while (!check(perm)) {
   3 i. ?% S* t+ [8 U. \
10.             perm = conv(perm);
    
11.             count++;
    , w. U: \2 a* K5 e9 o/ S
12.         }
    0 u) J2 D0 ^* a& G( |
13.         return count;
    1 z6 _. B9 ]) f6 ^7 p! M
14.     }
    & S) T  B! t0 v
15. 
    0 D$ [& }8 h% q" g; V
16.     boolean check(int[] perm) {
    ( {0 y$ ^- ]. w- k7 r' l4 d
17.         for (int i = 0; i < perm.length; i++) {
    $ A) S( X0 C! }& q3 C) i( `: ^
18.             if (perm != i) {
    9 F9 R+ K! H3 R; j: `! I/ w
19.                 return false;
    
20.             }
    
21.         }
    * [2 _/ Z- k7 r5 r9 l
22.         return true;
    6 w( Z9 a+ r8 [( C3 y, Y& a1 ?( {
23.     }
    * d( a' E8 I5 E* A
24. 
    
25.     int[] conv(int[] perm) {
    
26.         int[] result = new int[perm.length];
    9 B: `9 H' w$ G- s- ?; k, o+ J  J
27.         for (int i = 0; i < perm.length; i++) {
    9 k2 E# ?9 Q5 T) P: E$ Q9 ]" p
28.             if (i % 2 == 0) {
    
29.                 result = perm[i / 2];
    , e. p0 U2 U2 M( K6 E- s* k, G
30.             } else {
    
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    9 r, o6 {* u( w# G+ ~9 r
32.             }
    8 V/ d& G" U" _
33.         }
    ( }; g' ]0 r8 h3 S* G
34.         return result;
    
35.     }
    
36. }

复制代码

No.3

替换字符串中的括号内容

解题思路

使用 Map 储存 knowledge，然后查找替换即可。

3 J1 N* Q2 c1 d( I" w4 v* T8 O* E

代码展示

1. class Solution {
   , i) |* S% Y: T7 f! N5 n
2.     public String evaluate(String s, List<List<String>> knowledge) {
   
3.         Map<String, String> map = new HashMap<>();
   ! w+ Q3 q* P& ~+ Y- e3 h
4.         for (var kv : knowledge) {
   ( o  G3 R, U; @: Z- m; R
5.             map.put(kv.get(0), kv.get(1));
     P) P; h: D2 y5 u" O
6.         }
   
7.         StringBuilder sb = new StringBuilder();
   ( S+ |3 ~# A/ x4 i$ J) C5 e
8.         for (int i = 0; i < s.length(); i++) {
   " X" K5 L# H8 E# D* }
9.             if (s.charAt(i) != '(') {
   ) K' f4 S% M1 _* m' g
10.                 sb.append(s.charAt(i));
    
11.                 continue;
    
12.             }
    
13.             int j = i + 1;
    - A9 j8 e( e1 T. i1 p
14.             while (s.charAt(j) != ')') {
    # G3 L& ?; V. @" Y( A  v4 a
15.                 j++;
    
16.             }
    
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    
18.             i = j;
    / S  V7 A8 D7 O  W+ E  g
19.         }
    
20.         return sb.toString();
    
21.     }
    , ]% @$ g/ x, d6 p& A
22. }
    

复制代码

' ~' a3 l0 e+ `! H( U6 I5 i

No.4

好因子的最大数目

解题思路

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

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

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

1 j6 z( O7 H- J$ u* B0 G0 D2 ?

代码展示

1. class Solution {
   
2.     public int maxNiceDivisors(int primeFactors) {
   
3.         int k = ((primeFactors - 2) % 3) + 2;
   
4.         int num3 = (primeFactors - k) / 3;
   ' j$ ?; ?  q4 ]. g0 I' @9 ~4 @
5.         long mod = (long) (1e9 + 7);
   ( Y' h, O" @: }7 _; S5 O3 A& e; R7 k
6.         long res = k * pow(3, num3, mod) % mod;
   3 |- p5 n# A- ^
7.         return (int) res;
   
8.     }
   
9. 
   
10.     long pow(long x, long y, long mod) {
    
11.         if (y == 0) {
    ( r8 i% Y' R! U2 J7 q
12.             return 1;
    0 j3 Q- o9 P3 N1 w' C0 u: R) Q5 C
13.         }
    
14.         long half = pow(x, y >> 1, mod);
    3 M! v2 D) _5 z5 `; J* A
15.         if ((y & 1) != 0) {
    4 t% l3 |! g  ]" P* t0 K, c
16.             return half * half * x % mod;
    9 }$ |7 b, s4 t! |4 n! X% s6 m
17.         }
    " z0 \8 r% `; ~
18.         return half * half % mod;
    7 Y, b. |1 f( h6 g
19.     }
    . `% h( o2 L8 j) t5 R8 b5 Q
20. }

复制代码

( b2 X, H6 o! ^5 J6 @5 S+ f2 W5 P上岸DS秋招最新大厂面经公开课
& x8 |# m2 s$ F0 M
% c1 T' W4 N2 I3 Q2 W

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

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

活动安排：

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

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

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

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

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群