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

2 x* U- {# Z* `- p; m/ ?" [
4 ?3 T5 V5 y( H* J8 {2 l0 i' X

上岸算法

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

我们直击上岸

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

No.1

字符串中不同整数的数目

解题思路

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

4 U" T5 J: p) q9 z+ }% q' l+ ^

代码展示

1. class Solution {
   
2.     public int numDifferentIntegers(String word) {
   " _. t# M% v: k' U1 ?2 I( |
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   + ^  o* H* |( M- E' J+ s8 i
4.         Set<String> set = new HashSet<>();
   ; S+ W4 }, b5 a3 h' {6 L
5.         for (String num : nums) {
   
6.             if (!num.equals("")) {
   % r' ^- [5 D5 ~/ X. m) M8 H# C2 E
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
     V2 N. h* k/ q; d
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   
9.                 set.add(trimLeadingZero);
   ( b3 H8 C- w  Y$ P8 v/ |
10.             }
    
11.         }
    
12.         return set.size();
    
13.     }
    2 _- u; r- r9 }+ V
14. }

复制代码

No.2

还原排列的最少操作步数

" ^7 q. l  h0 m# d$ }* q: K- @

解题思路

模拟还原过程。

代码展示

1. class Solution {
   
2.     public int reinitializePermutation(int n) {
   
3.         int[] perm = new int[n];
   
4.         for (int i = 0; i < n; i++) {
   
5.             perm = i;
   
6.         }
   4 u1 s9 V' Z+ R+ p
7.         int count = 1;
   
8.         perm = conv(perm);
   8 ^8 Y2 \9 a8 C* c, H6 U- r/ O
9.         while (!check(perm)) {
   1 v0 J: e6 y1 m9 D% Z% U! |/ k4 g4 g& `
10.             perm = conv(perm);
    
11.             count++;
    6 D9 I' a  v0 S7 L1 z6 v& O
12.         }
    
13.         return count;
    
14.     }
    
15. 
    
16.     boolean check(int[] perm) {
    
17.         for (int i = 0; i < perm.length; i++) {
    - Y5 n) k! J3 D) K9 f) K
18.             if (perm != i) {
    ) O+ V6 `. [# i2 {
19.                 return false;
    + N. x5 ^0 M  |- p
20.             }
    ) d5 `& D: _$ d( k, {
21.         }
    
22.         return true;
    1 C4 I! ~+ ~. K8 k% u2 c' _% ]
23.     }
    3 G/ y$ S/ \) t# y
24. 
    
25.     int[] conv(int[] perm) {
    9 y, d; l- ^% n3 X9 A
26.         int[] result = new int[perm.length];
    * g9 J' G0 F: I. o" ?+ B
27.         for (int i = 0; i < perm.length; i++) {
    . d, X& ]& E) o7 \: }0 j3 i$ H
28.             if (i % 2 == 0) {
    ) J- t6 U7 S0 @
29.                 result = perm[i / 2];
    
30.             } else {
    , e7 W5 v7 r$ f2 D" D; T0 z: G
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    ( n5 F; A, p: I8 {8 V
32.             }
    / R: L+ G0 U( \
33.         }
    
34.         return result;
    
35.     }
    
36. }

复制代码

No.3

替换字符串中的括号内容

解题思路

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

) K# s/ Z2 D# q: g2 J& u- H

代码展示

1. class Solution {
   " A5 y0 r% m: x) b! H5 E1 Z9 l
2.     public String evaluate(String s, List<List<String>> knowledge) {
   0 {4 X; y/ j; Y' K
3.         Map<String, String> map = new HashMap<>();
   . {6 ?5 c) E' Z3 m, T; u: }7 z
4.         for (var kv : knowledge) {
   
5.             map.put(kv.get(0), kv.get(1));
   / U5 L+ h  B- |: W5 ^
6.         }
   5 T7 [7 ?9 Y7 c* R
7.         StringBuilder sb = new StringBuilder();
   
8.         for (int i = 0; i < s.length(); i++) {
   
9.             if (s.charAt(i) != '(') {
   # q0 j1 t+ r$ `3 q, J! M- F% g1 r
10.                 sb.append(s.charAt(i));
    
11.                 continue;
    8 V  D. G5 C! ^) J! E
12.             }
    7 |5 Y& s* Z) G5 t4 A0 O/ \
13.             int j = i + 1;
    7 t" ^( d$ ~2 u
14.             while (s.charAt(j) != ')') {
    + @3 @. }" S. @  g( P, c
15.                 j++;
    # c  G9 g+ T7 B+ H( m$ M
16.             }
    
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    ; V6 T2 x9 g# K. Y$ L( |$ l. L
18.             i = j;
    & G( w' }( q% @2 f, a: j
19.         }
    3 E3 F7 S" a$ v$ S6 c
20.         return sb.toString();
    
21.     }
    . R: `) C7 x  c6 c6 Y
22. }
    * B3 V$ E& Q! [

复制代码

1 k* A1 q) L0 O0 k6 @% n

No.4

好因子的最大数目

( l2 s  x0 U# s/ Q$ M' E

解题思路

假如 n 有质因子 a, a, a, ..., b, b, b, ..., c, c, c...，那么它的一个好因子 x 必定至少由一个 a、一个 b、一个 c 组成。所以 n 的好因子数量就是 numsOfA * numsOfB * numsOfC
' ?- c. s0 h7 p# o+ m# m4 D

那么该题目就等价于：将 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;
   6 N; f# b9 ?5 |  i+ f
4.         int num3 = (primeFactors - k) / 3;
   1 H1 z8 b# r. e4 j  d
5.         long mod = (long) (1e9 + 7);
   ; L% Y; Y4 N* P2 O% [3 [2 K
6.         long res = k * pow(3, num3, mod) % mod;
   
7.         return (int) res;
   
8.     }
   
9. 
   9 N* g! K1 ?! E
10.     long pow(long x, long y, long mod) {
    3 e* D" o3 B3 A* M- N
11.         if (y == 0) {
    1 J" ?2 J5 d8 N
12.             return 1;
    / K, |$ P8 Q1 Q: V5 j: M
13.         }
    " }- {: J! I/ b; {% n
14.         long half = pow(x, y >> 1, mod);
    
15.         if ((y & 1) != 0) {
    9 h; e9 t( U& ^2 \5 D! B& X
16.             return half * half * x % mod;
    ) |% T& o2 M# D4 T, j
17.         }
    + `& H9 m8 }% p
18.         return half * half % mod;
    
19.     }
    
20. }

复制代码

4 C+ t( o% q( [# Y' ~
4 ]; ]: Q5 A2 d  F9 G上岸DS秋招最新大厂面经公开课
6 U  t  T0 ~: u# I% d& N( C

活动介绍：为北美同学免费提供大厂面试官面经重点，为你在线提分
. N" K  w% s/ c2 ^) M5 F活动时间：2021/4/5-2021/4/26

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

活动安排：

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

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

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

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

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群

# I" T! b- z6 X! Y/ Z+ \