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

8 J/ U* t$ S5 B2 Z3 R1 e, h" s/ F
* u" A- E6 l  f; r3 O, J3 i1 }9 t

上岸算法

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

我们直击上岸

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

3 B4 \5 X4 U3 J, n1 @
$ L; G, D9 c! ^% ^) e7 p

No.1

字符串中不同整数的数目

解题思路

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

代码展示

1. class Solution {
   
2.     public int numDifferentIntegers(String word) {
   
3.         String[] nums = word.replaceAll("\\D", " ").split(" +");
   8 H- P3 t# ?" N# n& d; x1 c( o
4.         Set<String> set = new HashSet<>();
   
5.         for (String num : nums) {
   0 ^0 W6 q/ ?4 U* l! C
6.             if (!num.equals("")) {
   
7.                 String trimLeadingZero = num.replaceAll("^0*", "");
   
8.                 trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero;
   / H5 L8 o# S* q2 _7 w
9.                 set.add(trimLeadingZero);
   ( v$ D6 l' I+ k# m
10.             }
    + q0 C$ c& H/ M
11.         }
    
12.         return set.size();
    
13.     }
    
14. }

复制代码

No.2

还原排列的最少操作步数

解题思路

模拟还原过程。

代码展示

1. class Solution {
   0 e7 g* C/ m3 }$ h; k# N' M6 G+ e( O
2.     public int reinitializePermutation(int n) {
   " C: o2 ?$ U0 }0 N
3.         int[] perm = new int[n];
   ! a0 k4 A# `1 o" A
4.         for (int i = 0; i < n; i++) {
   
5.             perm = i;
   
6.         }
   ; n0 p; d3 y& }/ ?$ U
7.         int count = 1;
   $ g7 u3 M  a, B4 Z) t
8.         perm = conv(perm);
   ( A1 s$ i" a( O: W% u
9.         while (!check(perm)) {
   
10.             perm = conv(perm);
    8 W! p) G7 ^2 j. P& k" e
11.             count++;
    
12.         }
    
13.         return count;
    * Y7 ~3 K! W* Q) k: s& i
14.     }
    
15. 
      m& e1 k. y" \1 x& {
16.     boolean check(int[] perm) {
    
17.         for (int i = 0; i < perm.length; i++) {
    5 V/ p( I+ @+ `% Z. [
18.             if (perm != i) {
    $ [/ X1 v+ ~- ^: k- q) O
19.                 return false;
    3 |, L9 I: }  F  ?. F- V- Q
20.             }
    ) D& u0 B  Q! L+ n" ]; ]
21.         }
    
22.         return true;
    7 L5 T- E( Q1 x1 j
23.     }
    
24. 
    
25.     int[] conv(int[] perm) {
    
26.         int[] result = new int[perm.length];
    
27.         for (int i = 0; i < perm.length; i++) {
    
28.             if (i % 2 == 0) {
    
29.                 result = perm[i / 2];
    
30.             } else {
    
31.                 result = perm[perm.length / 2 + (i - 1) / 2];
    6 p: A0 _' V- O+ G0 l
32.             }
    
33.         }
      p8 ]* n. {8 d+ w5 I; P: f1 G
34.         return result;
    . Z2 v+ Z4 h, \
35.     }
    
36. }

复制代码

No.3

替换字符串中的括号内容

解题思路

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

代码展示

1. class Solution {
   + S. g* o' e0 r1 G
2.     public String evaluate(String s, List<List<String>> knowledge) {
   
3.         Map<String, String> map = new HashMap<>();
   
4.         for (var kv : knowledge) {
   ; |: Z) d5 J- ?4 C. x' {
5.             map.put(kv.get(0), kv.get(1));
   
6.         }
   
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));
    
11.                 continue;
    1 s4 S- Z- U) K2 E
12.             }
    
13.             int j = i + 1;
    % g. E+ Q3 t% v. e2 P9 q
14.             while (s.charAt(j) != ')') {
    * M5 j$ i& ^* t/ k7 N- |
15.                 j++;
    % a8 D, B$ P6 o; X! ]9 `- ^0 T
16.             }
    # }6 g' D- g3 ?4 C8 E5 K# Q4 n
17.             sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
    ! e/ g; J' a& [6 _& J; ~+ x
18.             i = j;
    8 h/ C5 E6 x, U
19.         }
    
20.         return sb.toString();
    
21.     }
    
22. }
    

复制代码

' N! k8 K- p' N" r6 p

No.4

好因子的最大数目

- A( N: f5 d! a2 [1 P* b

解题思路

假如 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;
   ! o% G4 d4 l( B, G9 {0 R
4.         int num3 = (primeFactors - k) / 3;
   
5.         long mod = (long) (1e9 + 7);
   , d- l( N: P/ X
6.         long res = k * pow(3, num3, mod) % mod;
   
7.         return (int) res;
   
8.     }
   
9. 
   
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);
    
15.         if ((y & 1) != 0) {
    
16.             return half * half * x % mod;
    ) U7 u% [' J7 \* D! @4 z2 D
17.         }
      A: j1 p' d7 U" o
18.         return half * half % mod;
    
19.     }
    
20. }

复制代码

' m) s, M/ M3 p3 F
上岸DS秋招最新大厂面经公开课

% L4 c% z) N; B$ t! i$ F' ?; v

活动介绍：为北美同学免费提供大厂面试官面经重点，为你在线提分
) Y5 V3 E) j0 R& v( |) d" e活动时间：2021/4/5-2021/4/26

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

活动安排：

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

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

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

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

另有两场DS 求职技术讲座

参与方式：

联系小年糕，邀请进群

4 r6 |3 }+ g) J