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

# `4 s6 A- [: Q% _* y' S

上岸算法

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

我们直击上岸

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

) N4 W! |. g( _/ u

No.1

字符串中不同整数的数目

解题思路

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

代码展示

1. class Solution {
   
2.     public int numDifferentIntegers(String word) {
   7 }% E$ F' C) ]8 m
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   1 q7 G' {! C) Z- ]" j3 E! s# c
4.         Set<String> set = new HashSet<>();
   
5.         for (String num : nums) {
   
6.             if (!num.equals("")) {
   
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
   
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   " x/ v- U  x( y. T
9.                 set.add(trimLeadingZero);
   
10.             }
    & m9 j  a' ^: D
11.         }
    
12.         return set.size();
    
13.     }
    
14. }

复制代码

' F4 y3 }+ D" \

- v! z1 o# B6 e9 Y

No.2

还原排列的最少操作步数

解题思路

模拟还原过程。

! Q1 G9 E3 Z, R7 O0 g# w2 F

代码展示

1. class Solution {
   8 I) I2 Y+ r  \& _4 G6 X
2.     public int reinitializePermutation(int n) {
   6 ^: O8 x" e8 u: x/ A8 I; X0 ]
3.         int[] perm = new int[n];
   3 _2 y) U. W: S, S* M0 ]
4.         for (int i = 0; i < n; i++) {
   5 K+ m9 A' K/ M/ i0 x* P/ c
5.             perm = i;
   7 S+ ~8 V* x9 P; \) h9 [8 E
6.         }
   
7.         int count = 1;
   - v3 z: E+ T; V3 |& E& y0 g
8.         perm = conv(perm);
   8 d8 Y- L" \, G% e& D6 N0 F
9.         while (!check(perm)) {
   6 i" N. `( R$ |# b. x
10.             perm = conv(perm);
    + D2 l8 c' [+ @+ e# d
11.             count++;
    ! O& \( X9 u8 i3 ?( T, Q* H' N2 I
12.         }
    
13.         return count;
    4 D6 i6 R5 Y  W: G
14.     }
    + s% p( ]6 I# b$ i$ X8 s
15. 
    
16.     boolean check(int[] perm) {
    ( Z8 Q: {, j7 ~  b% _" C# [
17.         for (int i = 0; i < perm.length; i++) {
    : b8 t8 W* P9 P% j
18.             if (perm != i) {
    
19.                 return false;
    " i  A$ A) ?% @$ a1 R
20.             }
    % A3 X& c, s) a, l+ h7 a) F
21.         }
    ) E, @9 C2 ^& a+ A* I5 |
22.         return true;
    
23.     }
    2 t; h2 A; c% x  }3 g$ N
24. 
    ! c6 G1 q$ B- B$ }1 D
25.     int[] conv(int[] perm) {
    
26.         int[] result = new int[perm.length];
    % ]  \( i! m. ^; |- l! _
27.         for (int i = 0; i < perm.length; i++) {
    
28.             if (i % 2 == 0) {
    
29.                 result = perm[i / 2];
    - g8 z9 l6 x) e4 O+ Q" Z
30.             } else {
    
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    
32.             }
    " w( B8 A5 \7 v$ d: ~0 h
33.         }
    3 }0 q& l  {) v! [
34.         return result;
    
35.     }
    
36. }

复制代码

1 A( r7 F- M( I! X) p  _, H0 A' {7 @

No.3

替换字符串中的括号内容

解题思路

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

代码展示

1. class Solution {
   
2.     public String evaluate(String s, List<List<String>> knowledge) {
   0 s( v. c/ d2 F, a
3.         Map<String, String> map = new HashMap<>();
     {4 X' Q% |8 a( T( U
4.         for (var kv : knowledge) {
   " S+ i) Q" A1 ~" T: G( ]5 g
5.             map.put(kv.get(0), kv.get(1));
   ( o) _5 u* A2 P0 C9 g% `  c! e
6.         }
   " D5 Z1 B- d" u0 w
7.         StringBuilder sb = new StringBuilder();
   2 {& |, {% x8 Y7 r
8.         for (int i = 0; i < s.length(); i++) {
   ( o& @% m! \- }
9.             if (s.charAt(i) != '(') {
   
10.                 sb.append(s.charAt(i));
    
11.                 continue;
    
12.             }
    $ J* ?* X1 v& k0 W
13.             int j = i + 1;
    
14.             while (s.charAt(j) != ')') {
    
15.                 j++;
    # B. b, Z3 t% v+ V2 W7 |1 _( N
16.             }
    
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    3 q0 W7 |$ X* W4 @  p
18.             i = j;
    
19.         }
    " C0 K, @" _' h! |/ d3 S
20.         return sb.toString();
    $ H( }' \' K6 ~  s
21.     }
    
22. }
    

复制代码

$ ?, d  j+ A: _& f7 a. }

No.4

好因子的最大数目

. |1 R5 S. l9 L( n0 q( m

解题思路

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

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

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

代码展示

1. class Solution {
   % a/ a; S0 [! g. h. s5 |6 s7 b2 _
2.     public int maxNiceDivisors(int primeFactors) {
   ; Q% n( u. v0 v$ R  [* w
3.         int k = ((primeFactors - 2) % 3) + 2;
   - E2 h( i0 G& h5 w3 A
4.         int num3 = (primeFactors - k) / 3;
   
5.         long mod = (long) (1e9 + 7);
   
6.         long res = k * pow(3, num3, mod) % mod;
   ! W6 F& r4 S6 X& ?( S* T* c) l
7.         return (int) res;
   % A* x% J; b+ J8 J& i. o' V
8.     }
   
9. 
   5 X4 d4 @! O! R$ T9 F8 w  N- J
10.     long pow(long x, long y, long mod) {
    
11.         if (y == 0) {
    ) h# t9 c2 h7 ~8 k; g) e% w+ K6 G' Y: Y) Z
12.             return 1;
    ; k6 U; j7 h6 G$ G: N
13.         }
    
14.         long half = pow(x, y >> 1, mod);
    
15.         if ((y & 1) != 0) {
    4 [3 O" B' q$ L! ]- u9 O
16.             return half * half * x % mod;
    
17.         }
    " ^6 _5 R0 u, h9 p2 {" C3 R
18.         return half * half % mod;
    
19.     }
    
20. }

复制代码

" R' B4 z4 B: k  ?+ O! s4 t上岸DS秋招最新大厂面经公开课

5 B4 Z# l" \" g' x$ s2 G

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

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

活动安排：

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

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

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

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

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群