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

8 G  A9 |  x; x' h8 {) Z

上岸算法

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

我们直击上岸

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

5 E" ~  D1 W! J! |' l

No.1

字符串中不同整数的数目

解题思路

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

4 k% w0 k/ D2 ]* F4 C6 T+ z: {

代码展示

1. class Solution {
   " E  e# }- E# w5 u
2.     public int numDifferentIntegers(String word) {
   8 C6 D5 s/ D; b3 M: V
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   
4.         Set<String> set = new HashSet<>();
   
5.         for (String num : nums) {
   
6.             if (!num.equals("")) {
   + E; _" Z. A+ ^& f; R0 D. a! e
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
     `2 U3 l# E- s: L
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   . O1 Z& N4 C- O) s) }
9.                 set.add(trimLeadingZero);
   - T6 O+ g4 N  y7 U. y' u+ b8 v
10.             }
    
11.         }
    
12.         return set.size();
    
13.     }
    % `+ Q/ F. c6 |/ Z
14. }

复制代码

% c7 A% k; N( v5 |

5 r0 [# l; u3 j# `

No.2

还原排列的最少操作步数

解题思路

模拟还原过程。

代码展示

1. class Solution {
   
2.     public int reinitializePermutation(int n) {
   ( q6 [9 b* |% ~0 P. j; z8 Z0 O3 W' }
3.         int[] perm = new int[n];
   
4.         for (int i = 0; i < n; i++) {
   % I5 Y8 e# G+ e, Z, @
5.             perm = i;
   
6.         }
   
7.         int count = 1;
   0 H2 Q* k! ^9 R
8.         perm = conv(perm);
   
9.         while (!check(perm)) {
   & w$ |" @+ M& d( i& o: Z
10.             perm = conv(perm);
    3 v& l# N. l! `" z7 u& @" `
11.             count++;
    , T& N  r, K0 z0 k! e
12.         }
    
13.         return count;
    % g1 y3 D$ X8 j4 L; P7 F
14.     }
    5 M+ F3 d+ I  j# `, s6 J3 _, M2 q2 Q
15. 
    4 @3 C  D) [2 I+ D/ B
16.     boolean check(int[] perm) {
    0 |3 b5 ^7 ^2 x" }; b
17.         for (int i = 0; i < perm.length; i++) {
    
18.             if (perm != i) {
    
19.                 return false;
    1 o0 T; ^6 A- ]% v; N% a4 ]2 a
20.             }
    
21.         }
    " Z6 U( J! _, S! G$ [
22.         return true;
    $ l7 j: d! M( W
23.     }
    
24. 
    9 z$ D4 [0 D8 F
25.     int[] conv(int[] perm) {
    1 V: V6 N) j+ y3 h9 x
26.         int[] result = new int[perm.length];
    
27.         for (int i = 0; i < perm.length; i++) {
    
28.             if (i % 2 == 0) {
    ; a, I) r( u3 }# |8 Y7 Q
29.                 result = perm[i / 2];
    
30.             } else {
    - R; W4 G: T6 |: s- }
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    
32.             }
    
33.         }
    8 o% l2 v( @: T7 Y
34.         return result;
    
35.     }
    4 s/ R0 t2 O  z$ W- r3 G" Z  O
36. }

复制代码

No.3

替换字符串中的括号内容

解题思路

使用 Map 储存 knowledge，然后查找替换即可。
4 N3 j- e6 [+ _

( I6 ]  D) n3 `( r

代码展示

1. class Solution {
   + [* q; a) f" k' K+ r2 l
2.     public String evaluate(String s, List<List<String>> knowledge) {
   
3.         Map<String, String> map = new HashMap<>();
   
4.         for (var kv : knowledge) {
   & k7 {$ e2 U  u5 h: f' P
5.             map.put(kv.get(0), kv.get(1));
   4 ]# f! N% Y1 |) ?
6.         }
   9 L  j8 n8 N5 m
7.         StringBuilder sb = new StringBuilder();
   
8.         for (int i = 0; i < s.length(); i++) {
   
9.             if (s.charAt(i) != '(') {
   
10.                 sb.append(s.charAt(i));
    3 s1 @/ C/ H; C# [% P% s/ z
11.                 continue;
    
12.             }
    - C/ |' J# E: y  ^$ e$ C+ A' u
13.             int j = i + 1;
    
14.             while (s.charAt(j) != ')') {
    : s: B/ z; O: M% h
15.                 j++;
    5 r8 D0 L2 n8 E9 v1 P% U  A  L
16.             }
    3 B9 |2 N* t% _/ P2 L
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    
18.             i = j;
    0 b7 b: }# R! U; D4 P3 T
19.         }
    7 `$ H6 [5 ^0 i) m$ S
20.         return sb.toString();
    % a- ]. v* H$ V
21.     }
    ! Z. E. {2 A# K
22. }
    - p8 T$ s# Q; K0 y

复制代码

: c5 L8 N7 X* d+ A

No.4

好因子的最大数目

解题思路

假如 n 有质因子 a, a, a, ..., b, b, b, ..., c, c, c...，那么它的一个好因子 x 必定至少由一个 a、一个 b、一个 c 组成。所以 n 的好因子数量就是 numsOfA * numsOfB * numsOfC
( s3 N5 m; D+ m, Q  I- k

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

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

代码展示

1. class Solution {
   # a- a6 X% r" K! s$ m" m) j- l1 ]
2.     public int maxNiceDivisors(int primeFactors) {
   , {+ `; x/ d% y# v, o+ N
3.         int k = ((primeFactors - 2) % 3) + 2;
   , a0 r5 A$ {8 s
4.         int num3 = (primeFactors - k) / 3;
     J; B2 }, r6 l' [9 T
5.         long mod = (long) (1e9 + 7);
   4 e8 n" w: T6 d; G3 p1 {4 z* N1 V
6.         long res = k * pow(3, num3, mod) % mod;
   ) E# F+ w1 F, ^8 t6 {8 T& B- N- R# M
7.         return (int) res;
   , i- g. X- n0 l& h0 f" H
8.     }
   
9. 
   & ]0 J  ^4 U: D/ k& @
10.     long pow(long x, long y, long mod) {
    4 s7 B+ U/ Y9 R' L& j
11.         if (y == 0) {
      B9 p. @+ U+ s
12.             return 1;
    
13.         }
    
14.         long half = pow(x, y >> 1, mod);
    
15.         if ((y & 1) != 0) {
    
16.             return half * half * x % mod;
    " A% S2 C2 L; Z: O0 I
17.         }
    
18.         return half * half % mod;
    
19.     }
    
20. }

复制代码

上岸DS秋招最新大厂面经公开课

; i7 y  {5 {1 b; u

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

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

活动安排：

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

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

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

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

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群

; u9 S& E3 _: r# _