題目

統計前后綴下標對 I

給你一個下標從0開始的字符串數組words。

定義一個布爾函數isPrefixAndSuffix，它接受兩個字符串參數str1和str2：

當str1同時是str2的前綴（prefix）和后綴（suffix）時，isPrefixAndSuffix(str1,str2)返回true，否則返回false。
例如，isPrefixAndSuffix(“aba”,“ababa”)返回true，因為"aba"既是"ababa"的前綴，也是"ababa"的后綴，但是isPrefixAndSuffix(“abc”,“abcd”)返回false。

以整數形式，返回滿足i<j且isPrefixAndSuffix(words[i],words[j])為true的下標對(i,j)的數量。

解題思路

暴力判斷每一個字符串是否是開頭或結尾，代碼如下：

class Solution {public int countPrefixSuffixPairs(String[] words) {int res=0;int len=words.length;for(int i=0;i<len;i++){for(int j=i+1;j<len;j++){if (isPrefixAndSuffix(words[i],words[j])){res++;}}}return res;}public boolean isPrefixAndSuffix(String a,String b){return  b.startsWith(a)&&b.endsWith(a);}}

最長公共前綴長度

給你兩個正整數數組arr1和arr2。

正整數的前綴是其最左邊的一位或多位數字組成的整數。例如，123是整數12345的前綴，而234不是。

設若整數c是整數a和b的公共前綴，那么c需要同時是a和b的前綴。例如，5655359和56554有公共前綴565，而1223和43456沒有公共前綴。

你需要找出屬于arr1的整數x和屬于arr2的整數y組成的所有數對(x,y)之中最長的公共前綴的長度。

返回所有數對之中最長公共前綴的長度。如果它們之間不存在公共前綴，則返回0。

解題思路

預先處理arr1所有前綴到set中，然后arr2依次判斷即可，代碼如下：

class Solution {public int longestCommonPrefix(int[] arr1, int[] arr2) {Set<Integer> st = new HashSet<>();for (int x : arr1) {for (; x > 0; x /= 10) {st.add(x);}}int mx = 0;for (int x : arr2) {for (; x > 0 && !st.contains(x); x /= 10) ;mx = Math.max(mx, x);}return mx > 0 ? Integer.toString(mx).length() : 0;}
}

出現頻率最高的質數

給你一個大小為mxn、下標從0開始的二維矩陣mat。在每個單元格，你可以按以下方式生成數字：

最多有8條路徑可以選擇：東，東南，南，西南，西，西北，北，東北。

選擇其中一條路徑，沿著這個方向移動，并且將路徑上的數字添加到正在形成的數字后面。

注意，每一步都會生成數字，例如，如果路徑上的數字是1,9,1，那么在這個方向上會生成三個數字：1,19,191。

返回在遍歷矩陣所創建的所有數字中，出現頻率最高的、大于10的質數；如果不存在這樣的質數，則返回-1。如果存在多個出現頻率最高的質數，那么返回其中最大的那個。

注意：移動過程中不允許改變方向。

解題思路

對于每個單元格，枚舉八個方向，生成數字，統計其中質數個數。代碼如下：

class Solution {private static final int[][] DIRS = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};public int mostFrequentPrime(int[][] mat) {int m = mat.length;int n = mat[0].length;Map<Integer, Integer> cnt = new HashMap<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {for (int[] d : DIRS) {int x = i + d[0];int y = j + d[1];int v = mat[i][j];while (x >= 0 && x < m && y >= 0 && y < n) {v = v * 10 + mat[x][y];if (isPrime(v)) {cnt.merge(v, 1, Integer::sum);}x += d[0];y += d[1];}}}}int ans = -1;int maxCnt = 0;for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {int v = e.getKey();int c = e.getValue();if (c > maxCnt) {ans = v;maxCnt = c;} else if (c == maxCnt) {ans = Math.max(ans, v);}}return ans;}private boolean isPrime(int n) {for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;}
}

統計前后綴下標對 II

給你一個下標從0開始的字符串數組words。

定義一個布爾函數isPrefixAndSuffix，它接受兩個字符串參數str1和str2：

當str1同時是str2的前綴（prefix）和后綴（suffix）時，isPrefixAndSuffix(str1,str2)返回true，否則返回false。
例如，isPrefixAndSuffix(“aba”,“ababa”)返回true，因為"aba"既是"ababa"的前綴，也是"ababa"的后綴，但是isPrefixAndSuffix(“abc”,“abcd”)返回false。

以整數形式，返回滿足i<j且isPrefixAndSuffix(words[i],words[j])為true的下標對(i,j)的數量。

解題思路

本題跟第一題一致，不過在用暴力法就沒辦法解決了。可以用字典樹解決本題。

class Node {Map<Integer, Node> son = new HashMap<>();int cnt;
}class Solution {public long countPrefixSuffixPairs(String[] words) {long ans = 0;Node root = new Node();for (String S : words) {char[] s = S.toCharArray();int n = s.length;Node cur = root;for (int i = 0; i < n; i++) {int p = (s[i] - 'a') << 5 | (s[n - 1 - i] - 'a');cur = cur.son.computeIfAbsent(p, k -> new Node());ans += cur.cnt;}cur.cnt++;}return ans;}
}

總結

參與了許多周賽，卻始終在第三題上遇到瓶頸，難以突破。反復總結經驗后發現，雖然題解看起來簡單，但親自動手解決時總是遇到難題，無法順利通過。為了改進這一狀況，在接下來的練習中，我打算從第三題開始著手，以此作為突破口，提升我的解題能力。