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

上岸算法

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

我们直击上岸

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

' t. r, i% `3 Y. D$ O& ~6 b8 f

No.1

字符串中不同整数的数目

解题思路

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

" h- p0 y- M% l& a1 r+ ~. f) u

代码展示

1. class Solution {
   9 A6 ^  d* g& T4 F$ o3 M  K
2.     public int numDifferentIntegers(String word) {
   # s1 J% a  R% m1 r
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   7 n0 s( X( z; J, d! N) O6 j
4.         Set<String> set = new HashSet<>();
   . `& B" |# K) [
5.         for (String num : nums) {
   0 n! r% w5 E% k" H$ Y
6.             if (!num.equals("")) {
   ! }& ^% o8 e, s8 ^
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
   
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   
9.                 set.add(trimLeadingZero);
   + [% e9 m9 l! a6 j/ P1 O
10.             }
    7 |8 ]; k1 R7 H. f; x) ^
11.         }
    
12.         return set.size();
    
13.     }
    
14. }

复制代码

# M# E0 u9 f! b1 M

+ \; \" q9 i% W7 n  V) Q

No.2

还原排列的最少操作步数

: h5 E: B$ Q3 Y3 r$ O: x

解题思路

模拟还原过程。

代码展示

1. class Solution {
   
2.     public int reinitializePermutation(int n) {
   
3.         int[] perm = new int[n];
   
4.         for (int i = 0; i < n; i++) {
   ) A* M& b4 T9 J# O- K- m
5.             perm = i;
   
6.         }
   ' W, F* G8 W; K
7.         int count = 1;
   - e) I& W8 u" a
8.         perm = conv(perm);
   
9.         while (!check(perm)) {
   3 ^3 y- z# Q; ^: S: z
10.             perm = conv(perm);
    3 Z' `$ P" r: Y8 R) V
11.             count++;
    $ N/ @' ~; J, ]9 N. R! N& A2 h) V
12.         }
    
13.         return count;
    
14.     }
    
15. 
    
16.     boolean check(int[] perm) {
    $ V* B- O2 k5 [( z: i  [& Q
17.         for (int i = 0; i < perm.length; i++) {
    
18.             if (perm != i) {
    3 Y! C2 o2 f. ~* L/ N
19.                 return false;
    
20.             }
    
21.         }
    
22.         return true;
    
23.     }
    
24. 
    
25.     int[] conv(int[] perm) {
    
26.         int[] result = new int[perm.length];
    
27.         for (int i = 0; i < perm.length; i++) {
    4 W, K; e3 @# f! E6 ?* P  O
28.             if (i % 2 == 0) {
    " T  d: z* o4 c: E. y( `2 g/ f
29.                 result = perm[i / 2];
    : L2 Z% u& ~( U1 \) e+ N' {, E( z- D
30.             } else {
    3 l- K: g, E( J' j( Y/ V. q
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    
32.             }
    
33.         }
    
34.         return result;
    ; V- Z- O! ]2 l1 |. k
35.     }
    5 X( y+ b7 f8 T) Q8 A
36. }

复制代码

No.3

替换字符串中的括号内容

解题思路

使用 Map 储存 knowledge，然后查找替换即可。
7 l3 h1 g% I/ A! v5 t0 X: \0 @

0 x6 ^+ K; ?: @1 u# f6 s' i8 k. Q

代码展示

1. class Solution {
   ; B8 z+ v" ~; z  m2 T$ [
2.     public String evaluate(String s, List<List<String>> knowledge) {
   
3.         Map<String, String> map = new HashMap<>();
   3 {4 K- T: K$ Y) B
4.         for (var kv : knowledge) {
   
5.             map.put(kv.get(0), kv.get(1));
   4 L* @! ~; Q3 Y
6.         }
   5 `, [$ A2 E% g: S/ j: ^3 u9 q
7.         StringBuilder sb = new StringBuilder();
   ; B+ z0 h: O7 C" |
8.         for (int i = 0; i < s.length(); i++) {
   
9.             if (s.charAt(i) != '(') {
   
10.                 sb.append(s.charAt(i));
    
11.                 continue;
    9 ~" v& H! l: C+ @/ R
12.             }
    4 ^; I& o! m  v: H) S
13.             int j = i + 1;
    - S" d+ B3 N6 ^
14.             while (s.charAt(j) != ')') {
    
15.                 j++;
    
16.             }
    6 E" c* O% B$ o( p3 x6 A
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    
18.             i = j;
    1 w  t% S1 @( y0 F8 \0 B2 z% [
19.         }
    # j- J; E& |6 Y4 i% [& o6 S7 y( K
20.         return sb.toString();
    6 x5 s. S3 @- T% l
21.     }
    , g9 ]. _4 Z" y$ P$ @
22. }
    

复制代码

* e; k' I4 w  Y6 w( k

No.4

好因子的最大数目

) u" E1 J: p; L. e0 j; X7 W- G

解题思路

假如 n 有质因子 a, a, a, ..., b, b, b, ..., c, c, c...，那么它的一个好因子 x 必定至少由一个 a、一个 b、一个 c 组成。所以 n 的好因子数量就是 numsOfA * numsOfB * numsOfC
9 d. y% M$ K  ^5 f, Z( L+ y+ t9 ^. m

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

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

9 y1 ?  ?+ f( P

代码展示

1. class Solution {
   
2.     public int maxNiceDivisors(int primeFactors) {
   3 E. B+ i+ `: S7 x6 v
3.         int k = ((primeFactors - 2) % 3) + 2;
   3 A7 t; S! F: S: s- O
4.         int num3 = (primeFactors - k) / 3;
   
5.         long mod = (long) (1e9 + 7);
   - t4 T% [8 t2 g% A
6.         long res = k * pow(3, num3, mod) % mod;
   
7.         return (int) res;
   & |  c% W! c; _8 Z4 n' Q, ~
8.     }
   
9. 
   
10.     long pow(long x, long y, long mod) {
    
11.         if (y == 0) {
    
12.             return 1;
    ; ^3 h# ?& O$ u' Q; ^3 @/ q) r
13.         }
    
14.         long half = pow(x, y >> 1, mod);
    
15.         if ((y & 1) != 0) {
    ; s. w) \0 {  v6 b
16.             return half * half * x % mod;
    8 g! \" G7 }' ]/ C# `" w0 U$ x
17.         }
    
18.         return half * half % mod;
    2 e: b6 h1 h; a' b8 k4 a
19.     }
    
20. }

复制代码

上岸DS秋招最新大厂面经公开课
1 g: H* Q8 y# L" n, v
( p2 z- T# ?( ^$ v7 ]

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

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

活动安排：

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

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

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

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

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群