【面试经典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); // 滑动窗口中移除一个单词，相当于差值-1
if(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); // 滑动窗口中加入一个单词，相当于差值+1
if(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是否覆盖cntt
private 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;
}
}