【面试经典150】day 11
目录
1.无重复字符的最长子串
2.串联所有单词的子串
3.最小覆盖子串
4.有效的数独
1.无重复字符的最长子串
class Solution {public int lengthOfLongestSubstring(String s) {//定义哈希表Map<Character,Integer> dict=new HashMap<>();int ret=0;int i=-1;for(int j=0;j<s.length();j++){char c=s.charAt(j);//如果字符在字典中存在，更新左指针if(dict.containsKey(c)){i=Math.max(i,dict.get(c));}//存入最新的索引dict.put(c,j);ret=Math.max(ret,j-i);}return ret;}
}和python语言不同，java中的字典取值和存值,删除；
dict.get(key);
dict.remove(key);
dict.put(key,value);2.串联所有单词的子串
枚举起始位置，按步长统计单词个数是否一致。
默认的字典是不会自动赋值的；
out:是一个标签，用于continue或break语句跳转到指定位置。
有汇编那味了。
感觉像复制字典；
Map<String, Integer> cur = new HashMap<>(cnts);
class Solution {public List<Integer> findSubstring(String s, String[] words) {Map<String,Integer> dict=new HashMap<>();for(String word:words){//统计单词数组中单词的个数dict.put(word,dict.getOrDefault(word,0)+1);}List<Integer>ret=new ArrayList<>();out://枚举起始位置，按步长统计单词个数是否一致。for(int i=0,step=words[0].length(),n=words.length;i<=s.length()-step*n;i++){//字典定义，复制了Map<String,Integer> cur=new HashMap<>(dict);for(int j=0;j<n;j++){String subStr=s.substring(i+step*j,i+step*(j+1));if(!cur.containsKey(subStr)){continue out;}else{int v=cur.get(subStr);if(--v==0){cur.remove(subStr);}else{cur.put(subStr,v);}}}ret.add(i);}return ret;}
}好像超时了。
另解
class Solution {public List<Integer> findSubstring(String s, String[] words) {int ls = s.length(); // 字符串s的长度int m = words.length; // 总单词数量int n = words[0].length(); // 单个单词长度List<Integer> res = new ArrayList<>(); // 结果数组if (ls < m * n){return res; // 字符串s的长度小于所有单词拼接起来的长度，直接返回}// 枚举每一个切分单词的起点，共有[0, n-1]个起点for(int i = 0; i < n; i++){Map<String, Integer> diff = new HashMap<>(); // 记录滑动窗口中每个单词和words中对应单词的个数差值，diff为空，说明滑动窗口中的单词与word一致String w; // 子串// 从起点i开始，将前m个子串单词加入哈希表，前m个单词就是首个滑动窗口里的单词; j表示第几个单词for(int j = 0; j < m && i + (j + 1) * n <= ls; j++){w = s.substring(i + j * n, i + (j + 1) * n);diff.put(w, diff.getOrDefault(w, 0) + 1);}// 遍历words，进行做差for(String word: words){diff.put(word, diff.getOrDefault(word, 0) - 1);if(diff.get(word) == 0){diff.remove(word); // 单词数目为0，说明这个单词在滑动窗口和words的数目匹配，直接移除；}}// 移动这个长度固定为m*n的滑动窗口，左边界left为每个单词的起点，滑动窗口范围[left, left + m * n)for(int left = i; left <= ls - m * n; left += n){// 从第二个单词开始，开始要加入新单词，移除旧单词if(left > i){w = s.substring(left - n, left); // 当前left的前一个单词是要移除的单词diff.put(w, diff.getOrDefault(w, 0) - 1); // 滑动窗口中移除一个单词，相当于差值-1if(diff.get(w) == 0){diff.remove(w);}w = s.substring(left + (m - 1) * n, left + m * n); // 右边界right = left + (m - 1) * n，为要加入滑动窗口的单词的起点diff.put(w, diff.getOrDefault(w, 0) + 1); // 滑动窗口中加入一个单词，相当于差值+1if(diff.get(w) == 0){diff.remove(w);} }// diff为空，说明滑动窗口中的单词与word一致；left即为子串起点if(diff.isEmpty()){res.add(left); }}}return res; }
}
3.最小覆盖子串
class Solution {public String minWindow(String s, String t) {//字符数组char [] s1=s.toCharArray();int m=s1.length;int retleft=-1;int retright=m;int [] cnts=new int[128];int [] cntt=new int[128];//cntt代表字符串t中每个字符c的出现次数for(char c:t.toCharArray()){cntt[c]++;}//int left=0;//cnts代表字符串s中每个字符的出现次数for(int right=0;right<m;right++){cnts[s1[right]]++;while(isCovered(cnts,cntt)){//更小的覆盖子串if(right-left<retright-retleft){retleft=left;retright=right;}//向右移动遍历cnts[s1[left]]--;left++;}}return retleft<0?"":s.substring(retleft,retright+1);}//通过统计字符出现次数的字典来判断cnts是否覆盖cnttprivate boolean isCovered(int [] cnts,int[] cntt){for(int i='A';i<='Z';i++){if(cnts[i]<cntt[i]){return false;}}for(int i='a';i<='z';i++){if(cnts[i]<cntt[i]){return false;}}return true;}
}4.有效的数独
class Solution {public boolean isValidSudoku(char[][] board) {//不合格的数独其实就是某一行、某一列、某个方块中某个数字出现了不止一次。//那么我们一边遍历一边记录上述三个地方的数字标记为出现，遇到有相同数字存在直接返回false即可。int n=board.length;boolean [][] rows=new boolean[n][n],columns=new boolean[n][n],squares=new boolean[n][n];//取单元格int m=(int)Math.sqrt(n);for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(board[i][j]=='.'){continue;}int num=board[i][j]-'1',sq=i/m*m+j/m;if(rows[i][num]||columns[j][num]||squares[sq][num]){return false;}rows[i][num]=columns[j][num]=squares[sq][num]=true;}}return true;}
}