上岸算法

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

我们直击上岸

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

No.1字符串中不同整数的数目

解题思路

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

代码展示

class Solution { 
   public int numDifferentIntegers(String word) { 
       String[] nums = word.replaceAll("\\D", " ").split(" +"); 
       Set<String> set = new HashSet<>(); 
       for (String num : nums) { 
           if (!num.equals("")) { 
               String trimLeadingZero = num.replaceAll("^0*", ""); 
               trimLeadingZero = trimLeadingZero.equals("") ? "0" : trimLeadingZero; 
               set.add(trimLeadingZero); 
           } 
       } 
       return set.size(); 
   } 
}

No.2No.2

还原排列的最少操作步数

解题思路

模拟还原过程。

代码展示

class Solution { 
   public int reinitializePermutation(int n) { 
       int[] perm = new int[n]; 
       for (int i = 0; i < n; i++) { 
           perm[i] = i; 
       } 
       int count = 1; 
       perm = conv(perm); 
       while (!check(perm)) { 
           perm = conv(perm); 
           count++; 
       } 
       return count; 
   } 

   boolean check(int[] perm) { 
       for (int i = 0; i < perm.length; i++) { 
           if (perm[i] != i) { 
               return false; 
           } 
       } 
       return true; 
   } 

   int[] conv(int[] perm) { 
       int[] result = new int[perm.length]; 
       for (int i = 0; i < perm.length; i++) { 
           if (i % 2 == 0) { 
               result[i] = perm[i / 2]; 
           } else { 
               result[i] = perm[perm.length / 2 + (i - 1) / 2]; 
           } 
       } 
       return result; 
   } 
} 

No.3 替换字符串中的括号内容

解题思路

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

代码展示

class Solution { 
   public String evaluate(String s, List<List<String>> knowledge) { 
       Map<String, String> map = new HashMap<>(); 
       for (var kv : knowledge) { 
           map.put(kv.get(0), kv.get(1)); 
       } 
       StringBuilder sb = new StringBuilder(); 
       for (int i = 0; i < s.length(); i++) { 
           if (s.charAt(i) != '(') { 
               sb.append(s.charAt(i)); 
               continue; 
           } 
           int j = i + 1; 
           while (s.charAt(j) != ')') { 
               j++; 
           } 
           sb.append(map.getOrDefault(s.substring(i + 1, j), "?")); 
           i = j; 
       } 
       return sb.toString(); 
   } 
} 

No.4  好因子的最大数目

解题思路

假如 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

代码展示

class Solution { 
   public int maxNiceDivisors(int primeFactors) { 
       int k = ((primeFactors - 2) % 3) + 2; 
       int num3 = (primeFactors - k) / 3; 
       long mod = (long) (1e9 + 7); 
       long res = k * pow(3, num3, mod) % mod; 
       return (int) res; 
   } 

   long pow(long x, long y, long mod) { 
       if (y == 0) { 
           return 1; 
       } 
       long half = pow(x, y >> 1, mod); 
       if ((y & 1) != 0) { 
           return half * half * x % mod; 
       } 
       return half * half % mod; 
   } 
}