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

- r1 n* W( r: c! c

上岸算法

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

我们直击上岸

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

: G0 R8 B" b% ]! a

No.1

字符串中不同整数的数目

解题思路

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

4 i+ }, h' T5 @8 f" o$ S

代码展示

1. class Solution {
   
2.     public int numDifferentIntegers(String word) {
   
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   
4.         Set<String> set = new HashSet<>();
   ' [$ L9 B0 \. U- Z3 `1 i
5.         for (String num : nums) {
   7 q, F$ ^* ?5 s# t8 [" F: w  a, ~
6.             if (!num.equals("")) {
   " Z3 O5 h+ @" ?" e5 L3 P  J
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
   ! W  S" z: A9 C6 Z, ~
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   
9.                 set.add(trimLeadingZero);
   
10.             }
    
11.         }
    9 X# h. u# P0 e1 |. W
12.         return set.size();
    
13.     }
    
14. }

复制代码

No.2

还原排列的最少操作步数

解题思路

模拟还原过程。

. N; l- ?$ L7 n  N  N3 J  a- d

代码展示

1. class Solution {
   , c9 a4 w$ Q1 Y- S8 H
2.     public int reinitializePermutation(int n) {
   
3.         int[] perm = new int[n];
   
4.         for (int i = 0; i < n; i++) {
   
5.             perm = i;
   " \$ K/ G  }) e3 H- O, G3 N7 t
6.         }
   
7.         int count = 1;
   * h* g6 U6 I" z9 ~
8.         perm = conv(perm);
   , ?0 F$ m4 p6 ?, D" n+ K  A
9.         while (!check(perm)) {
   
10.             perm = conv(perm);
    & \5 n: S$ I; \# t$ I
11.             count++;
    6 n/ [# O; ^" t" @4 o* [; T
12.         }
    # v' O( h# o6 F+ _  i) b. ?
13.         return count;
    
14.     }
      O" u0 ^! P  P* y$ H- u
15. 
    
16.     boolean check(int[] perm) {
    3 L- {, V4 n+ g7 f# b' h
17.         for (int i = 0; i < perm.length; i++) {
    
18.             if (perm != i) {
    3 b5 r2 Z% z. S/ f# P( d% d( r9 [
19.                 return false;
    + n5 {9 P$ J% P. |/ {
20.             }
    
21.         }
    
22.         return true;
    ' v$ ^& h- s. X8 T9 ^+ M3 v
23.     }
    
24. 
    $ g/ w, m! A. G3 ?- ~2 r! ^+ g
25.     int[] conv(int[] perm) {
    
26.         int[] result = new int[perm.length];
    ( v+ ~1 i+ T2 a
27.         for (int i = 0; i < perm.length; i++) {
    . n5 q. e8 G4 g# V6 T  E
28.             if (i % 2 == 0) {
    
29.                 result = perm[i / 2];
    
30.             } else {
    
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    8 d, h, ~7 T  {7 o. C
32.             }
    
33.         }
    
34.         return result;
    4 Q6 B" `# b* ]! X1 t% P
35.     }
    
36. }

复制代码

No.3

替换字符串中的括号内容

解题思路

使用 Map 储存 knowledge，然后查找替换即可。
& {: W6 W' C- z9 x& N3 [' ?

代码展示

1. class Solution {
   ' K, O& |/ w. V) W  I- Z
2.     public String evaluate(String s, List<List<String>> knowledge) {
   ' c5 v1 `8 R) h
3.         Map<String, String> map = new HashMap<>();
   
4.         for (var kv : knowledge) {
   
5.             map.put(kv.get(0), kv.get(1));
   " q- p1 {9 _! _2 R, S: ], }8 @; a8 e& K
6.         }
   
7.         StringBuilder sb = new StringBuilder();
   
8.         for (int i = 0; i < s.length(); i++) {
   ) A/ L4 Z: t. @- I
9.             if (s.charAt(i) != '(') {
   
10.                 sb.append(s.charAt(i));
    ' G, [- ^4 O* X0 j
11.                 continue;
    
12.             }
    * U( _$ F$ F: s% W. W2 Q
13.             int j = i + 1;
    6 S; `5 G$ X$ S- l- ~9 W* o2 v$ c
14.             while (s.charAt(j) != ')') {
    
15.                 j++;
    ' P6 f' S1 H2 m: s6 S
16.             }
    
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    ( `* T# X# F8 O3 q7 M
18.             i = j;
    0 k3 J$ [9 m# {$ r, h
19.         }
    
20.         return sb.toString();
    0 Z7 b) l5 J) a& g
21.     }
    3 c: E+ x1 |1 y9 i6 r
22. }
    . d; [% Z$ l" a* R/ \' N, H

复制代码

No.4

好因子的最大数目

  c# E/ O1 z1 w+ c1 Y" \- g

解题思路

假如 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. class Solution {
   
2.     public int maxNiceDivisors(int primeFactors) {
   
3.         int k = ((primeFactors - 2) % 3) + 2;
   ' I& E8 H8 @$ n% Q% X/ Q
4.         int num3 = (primeFactors - k) / 3;
   
5.         long mod = (long) (1e9 + 7);
   0 n3 D% [  `6 _( _$ ^
6.         long res = k * pow(3, num3, mod) % mod;
   
7.         return (int) res;
   & R* m/ ]" `$ F% h  q, d& F
8.     }
   
9. 
   0 j0 K! e" n! s8 `7 p# I0 E7 e$ E* H
10.     long pow(long x, long y, long mod) {
    
11.         if (y == 0) {
    
12.             return 1;
    
13.         }
    
14.         long half = pow(x, y >> 1, mod);
    $ |- B1 e5 j9 F5 T& ]3 V
15.         if ((y & 1) != 0) {
    
16.             return half * half * x % mod;
    7 U) c  g/ z8 V& C/ I
17.         }
    0 {" I6 h: T- K+ K# M5 X' y
18.         return half * half % mod;
    " Z) j+ Q/ O2 j& [% D7 m, d
19.     }
    
20. }

复制代码

3 O2 T1 U7 v" g0 g( c; j上岸DS秋招最新大厂面经公开课

活动介绍：为北美同学免费提供大厂面试官面经重点，为你在线提分
1 v8 C# e3 U5 k  L; n4 m/ e活动时间：2021/4/5-2021/4/26

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

活动安排：

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

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

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

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

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群

! o' o# @6 M# N( i& z