[每天两道题]坚持找到工作为止

adbase

27. Remove Element
这一题大意和上一题差不多，上一题是删除重复的，这一题要求你删除指定的数字，然后把其他的数字排除掉指定数字之后，复制到数组的前面。可以颠倒循序。

题目分析
还是老套路，数组删除，那么就是找数字，因为要复制数字，所以如同上一题还是快慢指针。
这次指针移动的规律是：
用一个循环，依次用快指针检验当前数字
若是遇到要删除的数字，就让快指针跳到下一位。
若是遇到其他数字，那么就把快指针的数字复制到慢指针的位置上，然后二者同时移动到下一位。

所以代码就是：

public int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while(fast < nums.length) {
if(nums[fast] == val) {
fast++;
}else {
nums[slow] = nums[fast];
fast++;
slow++;
}
}
return slow;
}

复制代码

adbase

28. Implement strStr()
这个题也不太好，让你实现java 中的indexOf()。给你两个字符串a, b。要你返回b在a中第一次出现的位置，若是没有出现就返回－1。若是b是空的就返回0；

题目分析和解答。
这个题不是很好，但是算法很重要吧。
先说说我的笨的方法，因为字符串就是array的题，然后它是让我找一串substring，也就是滑动窗口。所以我的暴力解法就是，先匹配第一个字符，若是str的某一个位置，有一个字符匹配了needle中第一个字符。我们就用另外一个循环，验证它紧接着的后面的字符，是不是和needle是一样的，若是是一样的，那么就返回匹配第一个字符的位置。

这其实就是暴力解法，代码是

public int strStr(String haystack, String needle) {
char[] hc = haystack.toCharArray();
char[] nc = needle.toCharArray();
if(nc.length == 0) return 0;
loop1 : for(int i = 0; i < hc.length - nc.length + 1; i++) {
if(hc[i] == nc[0]){
for(int j = 0; j < nc.length; j++) {
if(nc[j] != hc[i + j]){
continue loop1;
}
}
return i;
}
}
return -1;
}

复制代码

下面说说正确的解法，我没有写到这里，大家可以自己去搜索。
正确的解法，就是kmp算法。其实kmp算法的思路就是对我的解法的优化。它的解法还是匹配第一个字符，但是若是匹配失败，那么后面匹配失败的长度就可以跳过了。但是聪明的人肯定会想到，若是前面某个字符和后面是重复的，那么若是都跳过，岂不是跳多了。比如needle
= abcdabd。去匹配 str = abcdabcdabd。
若是在前面失败了之后都跳过，那么只剩下cdabd，肯定最后不会匹配到结果，也就是前面abcdab匹配失败之后，不能都跳过，而是从倒数后一个的abc开始下一次的验证。

所以kmp的算法的精髓，就是计算这个最后一段重复的ab的位置。它的思想是前缀和后缀的比较。一个次的前缀就是一个词所有单词，从前数到某一个长度比如 abc前缀就是［a , ab ,abc］。后缀就是反过来－ abc后缀就是［c ，bc， abc］。kmp算法就是，找出前缀和后缀重复的一段，那就是我们下一次跳越的位置，比如abcdabd 前缀［a ab abc abcd abcda abcdab abcdabd］。它去匹配abcdabcdabd，那么我们第一次失败的字符是abdcdab。它的后缀是[b ab dab cdab bcdab abcdab] 所有它们共有的单词，是ab，长度是2,，所以也就是从后面两个单词开始进行下一次的循环。

这里我就不放kmp的代码了，大家可以自行去搜索和学习。

adbase

29. Divide Two Integers
这题也非常不好，今天的题都不太好，限制比较多，考察的知识点也很偏门。面试中这种题很容让对方混乱，需要解释很久。
这道题是给你两个数字，要求你做除法，但是不能用除号，或者乘号。

题目分析
这道题就是数学题了，数学题都比较难，因为它不是考编程了……
不能用乘除，却要我们实现除法，暴力的方法就是一直减。因为除法就是减法吗……
当然实际的考点，其实是位运算。

位运算面试中只要掌握一个知识点我感觉基本就够了，那就是正数左移1位，等于乘以2。
那么题目其实就变成，你每次只能乘以2，能不能实现任意数的除法？

当然是可以的，做除法，其实就是做减法吗。
比如我要计算19 / 6
由于我们只能乘以2，所以我们先让6，每次都左移一次，也就是相当于每次都乘以2，直某一次，最后大于19了，那么此时偏移量－ 1就是一个尽量大数字。在 19 ／ 6中，我们左移一次 : 6 <<1 = 6＊ 2 ＝ 12 < 19。再左移一次 12 << 1 = 12 * 2 =24 > 19
那么我们就找到了一个尽量大的数－ 12。偏移量是1，因为我们左移了一次。
我们再把19 － 12 ＝ 7。继续左移6 ： 6 << 1 = 12 > 7。所以我们左移了一次，就大于7了。那么偏移量就是0，也就是不偏移，6本身就是一个尽量大的数字了。然后我们再用7 － 6 ＝ 1；此时 1 <6。我们的除法已经做完了，1 就是余数。

那么答案是多少呢？我们第一次左移了1次，第二次左移了0次。
所以答案就是 2 ^ 1 + 2 ^ 0 = 2 + 1 = 3。
也就是说 19 /6 = 3 余 1

所以这个题目的核心代码不是很长，但是我们要处理很多特殊案例，一个是除以0，我们返回最大或者最小的整数值，还有就是负的最小值除以－1要特殊处理，因为会溢出，还有就是被除数是0也要特殊处理。最后还要注意，为了防止左移溢出，必须把原来的数字变成long，还有就是因为只有正数的左移才等于乘以2，所以我们必须把原数字都取正，所以代码就是：

public int divide(int dividend, int divisor) {
if(divisor == 0){
return dividend > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
if(divisor == -1 && dividend == Integer.MIN_VALUE){
return Integer.MAX_VALUE;
}
if(dividend == 0) return 0;
boolean sign = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
long a = Math.abs((long)dividend);
long b = Math.abs((long)divisor);
int rs = 0;
while(a >= b){
int shift = 0;
while(a >= (b << shift)){
shift++;
}
a -= b << (shift - 1);
rs += 1 << (shift - 1);
}
return sign ? -rs : rs;
}

复制代码

adbase

30. Substring with Concatenation of All Words
题目分析
这是array的题，让我们找substring，所以一定就是滑动窗口。先找左窗口，因为列表里字符串是等长的，所以我们就用这写字符串的长度，一段一段去验证。
若是发现某一个位置，出现了字符串，那么我们就开一个新的循环，验证后面的几段，是不是恰好包含了列表里所有的字符串。

到这里思路都很好想，然后难点就是，这么样才能知道后面几段包含了列表里所有的字符串呢？
方法就是用map，key是列表里的字符串，value就是它的数量。然后验证的时候，再建一个一样的map2，存substring里面，出现的每一段的字符串，以及它的数量。然后二者做比较，一样的key，value也一定是一样的，若是不一样，或者key少了，或者出现了前者不存在的key，那么就是失败的匹配。否则，就是成功的匹配，那么我们把substring的第一位下标放进答案中即可。

这个题不算很难，代码有点啰嗦，不过思路并不难想

class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> rs = new ArrayList<>();
if(words.length == 0 || s.length() == 0) return rs;
Map<String, Integer> map1 = new HashMap<>();
for(String word : words){
int count = map1.getOrDefault(word, 0);
map1.put(word, count + 1);
}
int len = words[0].length();
loop1: for(int i = 0; i < s.length() - words.length * len + 1; i++) {
String temp = s.substring(i, i+ len);
if(map1.containsKey(temp)){
Map<String, Integer> map2 = new HashMap<>();
for(int j = i; j < i + (words.length * len); j = j+len) {
String word = s.substring(j, j + len);
if(map1.containsKey(word)){
int count = map2.getOrDefault(word, 0);
if(count + 1 > map1.get(word)){
continue loop1;
}
map2.put(word, count + 1);
}else{
continue loop1;
}
}
rs.add(i);
}
}
return rs;
}
}

复制代码

adbase

31. Next Permutation
这是一道很重要的高频题。要求找出下一个更大的数字，记得这个题在后面很多难题里都会作为步骤的一部分出现。比如很多题都要求按照字母排序返回结果，就是这个题的变种。因为字母排序说道理还是数字的大小，因为字母本质就是ascII码。

找下一个更大的数字，方法比较死，也比较简单。用双指针
第一个指针，从右边开始，找第一个下降的数字，也就是从右边开始数，第一个nums[p1] < nums[p1 ＋ 1]的数字。
第二个指针，我们再从右边开始，找第一个比nums[p1]更大的数字 - nums[p2] > nums[p1]。
然后我们交换p1和p2 ＋1的数字，也就是交换p1和它右侧比它小的第一个数字。
交换完成之后，我们再把p1右侧的数字，全部颠倒一下循序，比如532就变成235。

这样，我们就得到了一个比原数字更大一点的，也是由原数字所欲数字组成的一个新的数字。
这个题的本质，是单调栈，但是因为题目要求不能定义任何可变长度的数据结构，所以只能用双指针来做。
代码是：

class Solution {
public void nextPermutation(int[] nums) {
int left = nums.length - 2;
while(left >= 0 && nums[left] >= nums[left + 1]){
left--;
}
if(left >= 0) {
int right = nums.length - 1;
while(nums[left] >= nums[right]){
right--;
}
swap(nums, left, right);
}
reverse(nums, left + 1, nums.length - 1);
}
private void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
private void reverse(int[] nums, int a, int b){
while(a < b){
swap(nums, a, b);
a++;
b--;
}
}
}

复制代码

adbase

32. Longest Valid Parentheses
这个是一道非常好的面试题－给一个字符串，返回最长包含合法括号的子串。
这个题的做法很多，既考验逻辑性又可以考编程。题面简单易懂。是一个可以区分面试者做题努力水平的一个题（收藏起来去坑害其他面试者，哈哈哈）

题目解答
给了字符串，搜索一个字串，当然就是想到滑动窗口。滑动窗口的唯一难点，是如何伸缩窗口。我没有想出最佳答案，做完之后看了其他人更快的解法，虽然更巧妙，但是思想本质还是再回答如何更有效率地伸缩窗口上。
难得自己能解出一个hard，记录一下自己的做法。
因为是括号题，自然地想到用stack栈来解决。我的方法是
0 定义一个栈，再定义一个数组－ int[] map，长度和字符串长度相等，这是为了记录每个位置的括号是非法的还是合法的。我用int[] ,0是合法，1是非法的。
1 用0位开始依次检查字符
2 遇到左括号，就把左括号的下标入栈。
3 遇到右括号，
      -检查栈是否有值，
      若是栈为空，那么这个右括号就是一个多余的，我们让map[i] = 1;
      若是不为空，那么这个右括号和左括号都是合法的，我们把做括号弹出栈
4 检验完所有的字符之后，若是栈内还有多余的左括号，那么它们就都是非法的。我们把它们的下标出栈，然后让map[stack.pop()] = 1;

这样，我们的int[] map就记录了所有的非法的字符。接下来，题目就变成了在一个数组中，找最长的0。
那么找最长0，当然就是简单地左右指针就可以了。
所以代码就是

class Solution {
public int longestValidParentheses(String s) {
char[] sc = s.toCharArray();
int[] map = new int[sc.length];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < sc.length; i++) {
if(sc[i] == '('){
stack.push(i);
}else {
if(stack.isEmpty()){
map[i]++;
}else
stack.pop();
}
}
while(!stack.isEmpty()){
map[stack.pop()]++;
}
int right =0;
int rs = 0;
for(int i = 0; i < map.length; i++) {
if(map[i] == 1) continue;
right = i;
while(right < map.length && map[right] == 0) {
right++;
}
rs = Math.max(rs, right - i);
}
return rs;
}
}

复制代码

更好的解法其实不用栈，思路还是差不多，
还是依次检验字符，然后用两个数，统计左右括号的数量。然后再用一个指针初始化位置位0，来记录合法字符的位置。
每次遇到一个左括号，就左括号数量加1，反之右括号加1。若是左右数量相等了，那么就此时记录一下长度。若是右括号多了，说明这个右括号肯定是一个非法的，那么我们就以它的下一位起点，重新把指针位置移到它的下一个位置，并且把左右括号数量清零。

如此重复，我们就找到了，所有的右括号非法的情况下，最大的字符串的长度。然后我再反过来，从字符串的尾巴数用同样的方法数左括号非法的情况下，最大合法字符串的长度。

二次比较之后，最大的一个值就是答案了。
这里不放代码了，因为不是我的。不过可以看出这个方法，还是在试图找出滑动窗口的边界，只不过我是用栈和数组，记录下了所有的边界，它则是更巧妙地用左右对称原则，用更小的空间复杂度解决了问题。

adbase

33. Search in Rotated Sorted Array
排好序的数组，以某个点旋转一下，然后在旋转后的数组中用二分法找某个值。

题目心得和解答，
这个题也很经典，也是面试高频题，我自己面狗家就遇到了这个题。这题提示很明显了，log(n)复杂度就是要考二分法。
这道题可以背诵，因为写法几乎就是唯一的，你可以无脑背下来，不要太理解细节。此外这道题还有一个加强的问法，一个有序数组，旋转n次，然后再让你找某一个值，怎么找？
其实做法是一样的，我当时被问住了。后来摆了一下，才发现，无论旋转多少次，最后数组特征还是一样的，也就是还是只有一个旋转点。旋转多次，只是在移动旋转点而已。
二分法的模版目前我只能背最基本的，幸好这个题只用最基本的就可以了。最基本的就是说，数组没有重复数字，找某个值。那么循环条件是left <= right。每次上下都更新。

然后就是处理旋转，基本思想是旋转之后，总有一半是有序的。
那么我就先判断哪一半有序。方法是用nums[mid]和nums[right]比较大小。若是nums[mid]更大，说明旋转点在右边，因此mid的左侧就一定是有序的。若是nums[mid]比较小，那么就是mid的右侧是有序的。

然后我们就可以再分情况讨论了－
若是mid右侧是有序的，此时若是target恰好在右侧 nums[mid] < target <= nums[right]。那么我们就让l = mid + 1; 反之其他情况，r = mid -1;
若是 mid左侧是有序的，此时若是恰好 nums[left] <= target < nums[mid]，那么我们就让 r = mid - 1。反之其他情况，l = mid + 1;

若是 nums[mid] = target . 返回mid即可
若是最后循环结束，说明我们没有找到target，返回-1即可
代码就是：

class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int l = 0, r = nums.length - 1;
while(l <= r){//0 0
int mid = l + ((r - l) >> 1);
if(nums[mid] == target) {
return mid;
}
if(nums[mid] < nums[r]){
if(nums[mid] < target && target <= nums[r]) {
l = mid + 1;
}else r = mid - 1;
}else {
if(nums[mid] > target && target >= nums[l]) {
r = mid - 1;
}else l = mid + 1;
}
}
return -1;
}
}

复制代码

adbase

34. Find First and Last Position of Element in Sorted Array
经典的二分法练习题，非常推荐隔一段时间用它来复习一下。

二分法有三种写法，用于不同的场景：
1. 查找某一个数字：
while(l <= r)
mid = l + (r - l) /2
mid > t - r = mid - 1;
mid < t - l = mid + 1
return l
2. 有重复答案，找最左的答案
while(l < r)
min = 1 + (r - l) / 2
mid > t - r = mid ;
min < t - l = mid + 1;
mid = t - r - 1;
return l
3. 有重复答案，找最右的答案
while(l < r)
min = 1 + (r - l) / 2 + 1
mid > t - r = mid - 1 ;
min <= t - l = mid ;
return r

那么这道题就是情况2、3各写一遍，先找左边界，再找右边界。最后返回[l,r]。
代码就是：

class Solution {
public int[] searchRange(int[] nums, int target) {
int[] rs = {-1, -1};
if(nums == null || nums.length == 0) return rs;
int l = 0, r = nums.length - 1;
while(l < r) {
int mid = l + ((r - l) >> 1);
if(nums[mid] == target) {
r--;
}else if(nums[mid] > target) {
r = mid;
}else if(nums[mid] < target) {
l = mid + 1;
}
}
if(nums[l] != target) return rs;
else rs[0] = l;
l = 0;
r = nums.length - 1;
while(l < r) {
int mid = l + ((r - l) >> 1) + 1;
if(nums[mid] == target) {
l++;
}else if(nums[mid] > target) {
r = mid - 1;
}else if(nums[mid] < target) {
l = mid;
}
}
rs[1] = r;
return rs;
}
}

复制代码

adbase

35. Search Insert Position
还是二分法的题，让你找插入点，或者返回已经存在的下标。
这里用经典的二分法模版就可以解决，当然用左边界，或者右边界都可以，因为它没有重复数字，所以任何模版的效果都是一样的，我自己都试过，的确都一样。

这题唯一的变化就是返回值，要判断一下，最后nums[l]，和目标值的大小，若是nums[l] > = target。那么就返回l，也就是本身的位置，因为最后要插入到它的左边，那么现在这个数字下标自然就＋1。若是nums[l] < target，那么就返回l + 1;这也很好理解，因为要插入到它的下一位吗，当然就是l + 1；
所以代码就是：

class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while(l < r){
int mid = l + ((r - l) >> 1) ;
if(nums[mid] > target){
r = mid ;
}else if(nums[mid] < target){
l = mid + 1;
}else return mid;
}
return nums[l] >= target ? l : l + 1;
}
}

复制代码

adbase

36. Valid Sudoku

验证数独。这个题一般是前置问题，后面就会要你解决数独。
这个问题是，给你谜面，也就是一个9x9的格子，里面有的是数字，有的是点。点的意思就是要你将来填写数字的地方。
规则就是横竖不能有重复的数字，然后每个3x3的box也不能有重复的数字。
注意，就算这题最后结果为true，也不一定能有数独的解。也就是不一定能把点的格子都按规则填满。所以这题只是让你判断谜面是不是正确，不是让你解决数独问题。

这个题解法也很直接，就是定义三个map，分别存储9个行的数字，9个列的数字，和9个box的数字。若是有重复的，那就返回false，没有就继续插入数字，若能成功结束，那么就返回true;

难点就是这个box怎么判断。这里有个二位数组一维化的公式
count = x * board.length + y
这个公式转化之后，[0,0] 会变成0 ［0，1］会变成1……原矩阵中每一个数字，按照从左到右，从上到下，依次增大。
那么我们就利用这个公式，一个位置于［i， j］的数字，它一定属于第
box_id = (i / 3) * 3 + (j / 3) 个box里面
各位可以用笔演算一下。

所以解决了这个box的编号问题之后，这个题就很简单了。
剩下的就是编程小知识，我定义了数据结构中用了hashset。它的add（）方法其实是会返回一个boolean值的，利用这一单可以简化一些代码。所以最后的代码就是

class Solution {
public boolean isValidSudoku(char[][] board) {
Map<Integer, Set<Character>> row = new HashMap<>();
Map<Integer, Set<Character>> col = new HashMap<>();
Map<Integer, Set<Character>> box = new HashMap<>();
for(int i = 0; i< board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
char c = board[i][j];
if(c == '.') continue;
Set rset = row.getOrDefault(i, new HashSet<Character>());
if(!rset.add(c)) return false;
row.put(i,rset);
Set cset = col.getOrDefault(j, new HashSet<Character>());
if(!cset.add(c)) return false;
col.put(j,cset);
int boxid = (i / 3) * 3 + (j / 3);
Set bset = box.getOrDefault(boxid, new HashSet<Character>());
if(!bset.add(c)) return false;
box.put(boxid,bset);
}
}
return true;
}
}

复制代码

[每天两道题]坚持找到工作为止

浏览过的版块