2018-01-24 20:19:48
- 重复字符串匹配
问题描述：
问题求解：
使用brute force的方法求解，也就是依次比较，但是差别就是在A到末尾的时候循环从头开始继续进行比较。
public int repeatedStringMatch(String A, String B) { for (int i = 0,j; i < A.length(); i++) { for (j = 0; j < B.length() && B.charAt(j) == A.charAt((i+j) % A.length()); j++); // i就是A中前面失配的个数，j.length = 部分1 + n * A.length + 部分2 // i + j = i + 部分1 + n * A.length + 部分2 =(n + 1)* A.length + 部分2 // 所以其实就是一个向上取整 if(j == B.length()) return (i+j) / A.length() + ((i + j) % A.length() == 0 ? 0 : 1); } return -1; } 使用brute force的方法求解的运行效率是很低的，可以采用KMP算法加之改进。
public int repeatedStringMatch(String A, String B) { int[] prefix = new int[B.length()]; for (int i = 1, j = 0; i < B.length(); ) { if (B.charAt(i) == B.charAt(j)) prefix[i++] = ++j; else if (j == 0) i++; else j = prefix[j - 1]; } for (int i = 0, j = 0; i < A.length(); i += j - prefix[j - 1], j = prefix[j - 1]) { while (j < B.length() && A.charAt((i + j) % A.length()) == B.charAt(j)) j++; if (j == B.length()) return (int)Math.ceil((double)(i + j) / A.length()); if (j == 0) j++; } return -1; }
- 字符数组压缩
问题描述：
问题举例：
问题求解：
使用双层while循环可以避免使用单层for循环末尾取不到的问题，并且代码显得更加紧凑。
public int compress2(char[] chars) { int indexAns = 0; int index = 0; while(index < chars.length) { char currentChar = chars[index]; int count = 0; while(index < chars.length && chars[index] == currentChar) { index++; count++; } chars[indexAns++] = currentChar; if(count != 1) { for(char c : Integer.toString(count).toCharArray()) { chars[indexAns++] = c; } } } return indexAns; }
- 回文子串
问题描述：
问题求解：
最初想到的解法就是DP，就是不断从长度1，2，3生成判断是否回文，计数。
public int countSubstrings(String s) { int cnt = 0; boolean map[][] = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) { map[i][i] = true; cnt++; if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) { map[i][i + 1] = true; cnt++; } } for (int i = 2; i < s.length(); i++) { for (int j = 0; j < s.length() - i; j++) { if (s.charAt(j) == s.charAt(j + i) && map[j + 1][j + i - 1]) { map[j][j+i] = true; cnt++; } else { map[j][j+i] = false; } } } return cnt; } 事实上，也可以使用递归的思路，不断的生成字串进行判断，这种方法也是非常巧妙的。
int count = 0; public int countSubstrings2(String s) { if (s == null || s.length() == 0) return 0; for (int i = 0; i < s.length(); i++) { // i is the mid point extendPalindrome(s, i, i); // odd length; extendPalindrome(s, i, i + 1); // even length } return count; } private void extendPalindrome(String s, int left, int right) { while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) { count++; left--; right++; } }
-
Implement Magic Dictionary
问题描述：
问题求解：
使用Trie树可以很方便的进行求解，思路清晰。
public class MagicDictionary { class TrieNode { TrieNode[] child = new TrieNode[26]; boolean isWord = false; } TrieNode root; /** Initialize your data structure here. */ public MagicDictionary() { root = new TrieNode(); } /** Build a dictionary through a list of words */ public void buildDict(String[] dict) { for (String i : dict) { TrieNode cur = root; for (char j : i.toCharArray()) { if(cur.child[j - 'a'] == null) cur.child[j - 'a'] = new TrieNode(); cur = cur.child[j - 'a']; } cur.isWord = true; } } /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */ public boolean search(String word) { char[] s = word.toCharArray(); for (int i = 0; i < s.length; i++) { for (char j = 'a'; j <= 'z'; j++) { if(j == s[i]) continue; char pre = s[i]; s[i] = j; if (helper(s, root)) { return true; } s[i] = pre; } } return false; } boolean helper(char[] s, TrieNode root) { TrieNode tmp = root; for (char c : s) { if(tmp.child[c - 'a'] == null) return false; tmp = tmp.child[c - 'a']; } return tmp.isWord; }}
- 判断子串
问题描述：
问题求解：
方法一、双指针，遍历t一遍，就可以得到结果，代码简洁，时间复杂度为O(n)。
public boolean isSubsequence(String s, String t) { if (s.equals("")) return true; if (t.equals("")) return false; boolean res = false; int idxt = 0; int idxs = 0; char[] s1 = s.toCharArray(); char[] t1 = t.toCharArray(); for(;idxt < t1.length; idxt++) { if (t1[idxt] == s1[idxs]) idxs++; if (idxs == s1.length) { res = true; break; } } return res; } 方法二、follow up里提到，如果问题是一个t，多个s的情况下，使用上述的双指针，算法时间复杂度为O(kn)，就不那么理想了。一般来说这种问题，可以使用预处理的方法进行改进。我们可以使用一个HashMap，将每个字符出现的index保存下来。对于每个query，遍历一遍s，对每个字符进行查看，如果Hash中没有的话，直接返回false，如果存在，则寻找其index，进行判断。
public boolean isSubsequence(String s, String t) { if (s.equals("")) return true; if (t.equals("")) return false; HashMap > map = new HashMap<>(); char[] t1 = t.toCharArray(); char[] s1 = s.toCharArray(); for (int i = 0; i < t1.length; i++) { if (!map.containsKey(t1[i])) map.put(t1[i], new ArrayList ()); map.get(t1[i]).add(i); } int idx = 0; for (int i = 0; i < s1.length; i++) { if (!map.containsKey(s1[i])) return false; int k = Collections.binarySearch(map.get(s1[i]), idx); if (k < 0) k = -k - 1; if (k == map.get(s1[i]).size()) return false; idx = map.get(s1[i]).get(k) + 1; } return true; }