No.1 数组中的字符串匹配

★解题思路

该题目比较简单, 直接枚举即可, 使用 String.contains() 方法来判断一个字符串是否另一个字符串的子串.

有一个小细节, 在判断 sub 是否 word 的子串之前可以先判断长度, 必须严格小于才进一步调用 contains() 方法.

代码展示

class Solution { 
   public List<String> stringMatching(String[] words) { 
       List<String> res = new ArrayList<>(); 
       int n = words.length; 
       for (String sub : words) { 
           // 枚举, 判断 sub 是否某一个字符串的子串 
           for (String word : words) { 
               if (sub.length() < word.length() && word.contains(sub)) { 
                   res.add(sub); 
                   break; 
               } 
           } 
       } 
       return res; 
   } 
}

No.2查询带键的排列

★解题思路

该题目也比较简单, 解释见代码注释.

代码展示

class Solution { 
   public int[] processQueries(int[] queries, int m) { 
       int[] p = new int[m]; 
       for (int i = 0; i < m; i++) { 
           p[i] = i + 1;  
       } 
       int n = queries.length; 
       int[] res = new int[n]; 
       for (int i = 0; i < n; i++) { 
           // 枚举, 查找 queries[i] 在 p 中的位置 
           res[i] = indexOf(p, queries[i]); 
           // 将 p 数组的 [0, res[i]) 的元素向后移动一个位置 
           // 也可以调用 System.arraycopy 完成 
           for (int j = res[i]; j > 0; j--) { 
               p[j] = p[j - 1]; 
           } 
           // 将 queries[i] 放到第一个位置 
           p[0] = queries[i]; 
       } 
       return res; 
   } 

   int indexOf(int[] nums, int val) { 
       for (int i = 0; i < nums.length; i++) { 
           if (nums[i] == val) { 
               return i; 
           } 
       } 
       return -1; 
   } 
}

No.3HTML 实体解析器

★解题思路

只需要做简单的字符串替换即可. 下面的代码的做法是逐个字符处理, 遇到 & 则判断是否题目给定的字符实体之一, 是则进行替换, 否则直接加入到 StringBuilder.

代码展示

class Solution { 
   public String entityParser(String text) { 
       StringBuilder sb = new StringBuilder(); 
       for (int i = 0; i < text.length(); ) { 
           char c = text.charAt(i); 
           if (c != '&') { 
               sb.append(c); 
               i++; 
           } else if (i + 6 <= text.length() &&  
                      """.equals(text.substring(i, i + 6))) { 
               sb.append("\""); 
               i += 6; 
           } else if (i + 6 <= text.length() &&  
                      "'".equals(text.substring(i, i + 6))) { 
               sb.append("'"); 
               i += 6; 
           } else if (i + 5 <= text.length() &&  
                      "&".equals(text.substring(i, i + 5))) { 
               sb.append("&"); 
               i += 5; 
           } else if (i + 4 <= text.length() &&  
                      ">".equals(text.substring(i, i + 4))) { 
               sb.append(">"); 
               i += 4; 
           } else if (i + 4 <= text.length() &&  
                      "<".equals(text.substring(i, i + 4))) { 
               sb.append("<"); 
               i += 4; 
           } else if (i + 7 <= text.length() &&  
                      "⁄".equals(text.substring(i, i + 7))) { 
               sb.append("/"); 
               i += 7; 
           } else { 
               sb.append(c); 
               i++; 
           } 
       } 
       return sb.toString(); 
   } 
}

No.4给 N x 3 网格图涂色的方案数

★解题思路

动态规划问题.

• 定义状态: dp[i][c1][c2][c3] 表示第 i 列的三个格子颜色为 c1, c2, c3 时, 前 i 列的方案数
• 状态转移: 枚举上一列所有可能的状态即可, 只要不冲突, 就可以加到当前状态上, 即

dp[i][c1][c2][c3] = sum{ dp[i - 1][d1][d2][d3] } 相邻两列是 c1, c2, c3 和 d1, d2, d3 时颜色不冲突.

• 初始边界: dp[0][c1][c2][c3] = c1 != c2 && c2 != c3 ? 1 : 0
• 优化: 可以将 c1, c2, c3 这三维压缩成一维 27, 从而减少循环层数; 还可以使用滚动数组优化空间.

代码展示

class Solution { 
   public int numOfWays(int n) { 
       final int MOD = 1000000007; 
       int[][][][] dp = new int[n][3][3][3]; 
       for (int c1 = 0; c1 < 3; c1++) { 
           for (int c2 = 0; c2 < 3; c2++) { 
               for (int c3 = 0; c3 < 3; c3++) { 
                   dp[0][c1][c2][c3] = c1 != c2 && c2 != c3 ? 1 : 0; 
               } 
           } 
       } 
       for (int i = 1; i < n; i++) { 
           for (int c1 = 0; c1 < 3; c1++) { 
               for (int c2 = 0; c2 < 3; c2++) { 
                   for (int c3 = 0; c3 < 3; c3++) { 
                       for (int d1 = 0; d1 < 3; d1++) { 
                           for (int d2 = 0; d2 < 3; d2++) { 
                               for (int d3 = 0; d3 < 3; d3++) { 
                                   if (c1 == c2 || c2 == c3) continue; 
                                   if (d1 == d2 || d2 == d3) continue; 
                                   if (d1 == c1 || d2 == c2 || d3 == c3) continue; 
                                   dp[i][c1][c2][c3] += dp[i - 1][d1][d2][d3]; 
                                   dp[i][c1][c2][c3] %= MOD; 
                               } 
                           } 
                       } 
                   } 
               } 
           } 
       } 
       int ans = 0; 
       for (int c1 = 0; c1 < 3; c1++) { 
           for (int c2 = 0; c2 < 3; c2++) { 
               for (int c3 = 0; c3 < 3; c3++) { 
                   ans = (ans + dp[n - 1][c1][c2][c3]) % MOD; 
               } 
           } 
       } 
       return ans; 
   } 
}