面试经典150题【21-30】

6.Z字形变换

对于“LEETCOD”且参数为3的时候，3代表有三行需要创建三个res数组

class Solution {public String convert(String s, int numRows) {if(numRows < 2) return s;List<StringBuilder> rows = new ArrayList<StringBuilder>();for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());  //将数组创建且填充完成int i = 0, flag = -1;for(char c : s.toCharArray()) {rows.get(i).append(c);if(i == 0 || i == numRows -1) flag = - flag;  //如果到了最上面或最下面，则方向进行调转。i += flag;  //i决定下一个字母写到第几行}StringBuilder res = new StringBuilder();for(StringBuilder row : rows) res.append(row);return res.toString();}
}

28.找出字符串中第一个匹配项的下标

Sunday算法。
偏移表的作用是存储每一个在 模式串 中出现的字符，在 模式串 中出现的最右位置到尾部的距离 +1+1+1，例如 aab：

a 的偏移位就是 len(pattern)-1 = 2
b 的偏移位就是 len(pattern)-2 = 1
其他的均为 len(pattern)+1 = 4

要不就是移动到已有的（在Pianyi数组中），要不就是全部移动（移动nSize+1）

public class LC28 {static int strStr(String haystack,String needle){int hSize=haystack.length();int nSize=needle.length();HashMap<Character,Integer> pianyi=new HashMap<Character, Integer>();for(int i=0;i<needle.length();i++){//建立偏移表pianyi.put(needle.charAt(i),nSize-i);}//遍历int i=0;while(i<=hSize-nSize){//判断是否成功if(haystack.substring(i,i+nSize).equals(needle)) return i;else{//判断是否越界if(i+nSize > hSize-1) return -1;else{if(pianyi.containsKey(haystack.charAt(i+nSize))){//匹配，考虑往后移动几下//取最后的下一位字母，来判断应该偏移几位。这样偏移了以后，就满足他离最后还差几位。i+=pianyi.get(haystack.charAt(i+nSize));}else{i+=nSize+1; //不匹配，连这个字母也跳过}}}}return-1;}public static void main(String[] args) {String haystack = "w222sadbutsad", needle = "sad";System.out.println(strStr(haystack,needle));}
}

68.文本左右对齐

模拟题

三种情况：
1.当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格；
2.当前行不是最后一行，且只有一个单词：该单词左对齐，在行末填充空格；
3.当前行不是最后一行，且不只一个单词。

public class LC68 {@Testpublic void test(){String[] words= {"This", "is", "an", "example", "of", "text", "justification."};int maxWidth=16;List<String> strings = fullJustify(words, maxWidth);for(String s1:strings){System.out.println(s1);}}public List<String> fullJustify(String[] words, int maxWidth) {List<String> ans = new ArrayList<String>();int right = 0, n = words.length;while (true) {int left = right; // 当前行的第一个单词在 words 的位置int sumLen = 0; // 统计这一行单词长度之和// 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {sumLen += words[right++].length();}// 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格if (right == n) {StringBuilder sb = join(words, left, n, " ");sb.append(blank(maxWidth - sb.length()));ans.add(sb.toString());return ans;}int numWords = right - left;int numSpaces = maxWidth - sumLen;// 当前行只有一个单词：该单词左对齐，在行末填充剩余空格if (numWords == 1) {StringBuffer sb = new StringBuffer(words[left]);sb.append(blank(numSpaces));ans.add(sb.toString());continue;}// 当前行不只一个单词int avgSpaces = numSpaces / (numWords - 1);int extraSpaces = numSpaces % (numWords - 1);StringBuffer sb = new StringBuffer();sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接额外加一个空格的单词sb.append(blank(avgSpaces));sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其余单词ans.add(sb.toString());}}// blank 返回长度为 n 的由空格组成的字符串public String blank(int n) {StringBuilder sb = new StringBuilder();for (int i = 0; i < n; ++i) {sb.append(' ');}return sb.toString();}// join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串public StringBuilder join(String[] words, int left, int right, String sep) {StringBuilder sb = new StringBuilder(words[left]);for (int i = left + 1; i < right; ++i) {sb.append(sep);sb.append(words[i]);}return sb;}
}

#125.验证回文串

先把所有字母放到一个大字符串里（全部放小写字母），然后进行双指针的比较或直接比reverse也行
Character.isLetterOrDigit(ch) //判断是否为数字或字母
Character.toLowerCase(ch) //转小写

392.判断子序列

子序列和子串不一样。
“abc”是"ahbgdc"的子序列

167.两数之和

可以用双指针，缩减搜索空间。或者空间复杂度高一点做一个哈希表，每次读取了元素之后存到哈希表里。
return new int[]{hashMap.get(target-numbers[i])+1,i+1}

11.盛最多水的容器

求法就是双指针，面积就是底乘高。height[i]小就i++, height[j]小就j–;
若向内 移动短板 ，水槽的短板min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
若向内 移动长板 ，水槽的短板 min(h[i],h[j])​ 不变或变小，因此下个水槽的面积 一定变小

15.三数之和

先定一个first，然后就是求两数之和，双指针。注意不要重复的数字。

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();// 枚举 afor (int first = 0; first < n; ++first) {// 优化1 : 设 s = nums[first] + nums[first+1] + nums[first+2]，如果 s >// 0，由于数组已经排序，后面无论怎么选，选出的三个数的和不会比 s 还小，所以只要 s > 0 就可以直接 break 外层循环了。if (first + 2 < n && nums[first] + nums[first + 1] + nums[first + 2] > 0) {return ans;}// 优化2 ： 当nums[i] + nums[length - 1] + nums[length - 2] < 0 时，// nums[i]不可能符合条件，i++if (nums[first] + nums[n - 1] + nums[n - 2] < 0) {continue;}// 枚举的数字需要与上一个不同if (first > 0 && nums[first] == nums[first - 1]) {continue;}int third = n - 1;// 定义 b+c的目标位targetint target = -nums[first];// 枚举bfor (int second = first + 1; second < n; second++) {// 枚举数字需要与上一个不同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 两数之和, 对于每一个second,枚举cwhile (second < third && nums[second] + nums[third] > target) {--third;}// 重合了就退出循环if (second == third)break;if (nums[second] + nums[third] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}

209.长度最小的子数组

正常的话要考虑两个东西，一个是找不到则答案输出为0，还有是因为是Min函数，要考虑ans的初始值。
但是也可以用一个三目运算符搞定。

class Solution {public int minSubArrayLen(int target, int[] nums) {int i=0,sum=0,len=0;for(int j=0;j<nums.length;j++){sum+=nums[j];while(sum>=target){len= len==0? (j-i+1) :Math.min(len,j-i+1);sum-=nums[i++];}}return len;}
}

找不到答案，说明target太大，走不进while循环里。
只要大了，就取当前长度(j-i+1) 与 len 做比较。

3.无重复字符的最长子串

用set

public class LC3 {public int lengthOfLongestSubstring(String s) {if(s.length() ==0)  return 0;Set<Character> c1=new HashSet<Character>();int left=0,maxStr=0;for(int i=0;i<s.length();i++){while(c1.contains(s.charAt(i))){//因为有abcaad这种情况。所以应该删一次. 并且要将if改为while//移除的是最左边的元素，但是while判断里的是 i元素。c1.remove(s.charAt(left));left++;}maxStr=Math.max(maxStr,i-left+1);c1.add(s.charAt(i));}return maxStr;}
}

用hash

public class LC3 {public int lengthOfLongestSubstring(String s) {if(s.isEmpty())  return 0;Map<Character,Integer> map=new HashMap<>();int maxStr=0,left=0;for(int i=0;i<s.length();i++){if(map.containsKey(s.charAt(i))){//肯定是发生了abca这种，所以要把left从a变到b//left=map.get(s.charAt(i))+1;//如果遇到abba呢，会造成指针回跳，所以要修改//+1应该在括号里，因为有zmmuyrz的情况。答案应该是muyrz五个数。//一般都是走后面的情况，防止指针回跳加了个Max(leftleft=Math.max(left,map.get(s.charAt(i))+1);}map.put(s.charAt(i),i);maxStr=Math.max(maxStr,i-left+1);}return maxStr;}
}

30.串联所有单词的子串

这个滑动窗口太硬了，还是直接暴力吧。用一个hashMap来记录每个单词出现的次数。

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> res = new ArrayList<Integer>();int wordNum = words.length;if (wordNum == 0) {return res;}int wordLen = words[0].length();// HashMap1 存所有单词HashMap<String, Integer> allWords = new HashMap<String, Integer>();for (String w : words) {int value = allWords.getOrDefault(w, 0);allWords.put(w, value + 1);}// 遍历所有子串for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {// HashMap2 存当前扫描的字符串含有的单词HashMap<String, Integer> hasWords = new HashMap<String, Integer>();int num = 0;// 判断该子串是否符合while (num < wordNum) {String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);// 判断该单词在 HashMap1 中if (allWords.containsKey(word)) {int value = hasWords.getOrDefault(word, 0);hasWords.put(word, value + 1);// 判断当前单词的 value 和 HashMap1 中该单词的 valueif (hasWords.get(word) > allWords.get(word)) {break;}} else {break;}num++;}// 判断是不是所有的单词都符合条件if (num == wordNum) {res.add(i);}}return res;}}