Leetcode second round 9/1

today's mission: 29 - 44

29: divide two integers

这个题目的算法还是记住比较好，用的其实是 a/b -> a = b * 2 ^n + b * 2^(n-1) +.....+ b* 2^0;
每次通过移位操作计算n， 但是要注意INT_MIN如果直接利用abs转换成负数的话，会造成溢出，所以我们需要先把INT_MIN --> long long的范围内再进行转换成正数。还要注意corner case的判断： 当 dividend 是INT_MIN, divisor 是 -1的时候， 会造成溢出，直接返回INT_MAX；

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        long long a = dividend;
        long long b = divisor;
        int count = 0;
        int rst = 0;
        a = abs(a);
        b = abs(b);
        while (a >= b) {
            while (a >= (b << count+1)) count++;
            a = a - (b << count);
            rst += 1 << count;
            count = 0;
        }
        return (dividend < 0 ^ divisor < 0) ? -rst : rst;
    }
};

30:  substring with concatenation of words
这个题目跟之前做过的那个找一个word是类似的， 算法是sliding window + string hashmap, 在处理方式上，有两种方法： 一种是固定长度window，s里面所有可能的window都遍历一次。一种是遍历所有可能开始的位置， 每次对整个string进行遍历， 进行匹配。前者在处理上优于后者。

31. next permutation
这个题目感觉解也要记住，因为没有什么规律可言啊，这种算法面试中也很难想到吧！

这个题目的解题算法是： 
1. 从右往左找到第一个违背升序排列的元素index， s[i-1] < s[i]
2. 从右往左找到第一个比step1里面那个index对应的元素大的值的index
3. swap这两个元素，然后将step1里那个index后面的元素进行reverse。
4. step1里如果找不到这两个元素，那么说明整个permutation是最大的，直接reverse整个顺序就可以了。

32: longest valid parentheses
这个题目是 valid parentheses的变形， 其实基本的思路和valid parentheses 差不多，只是这个题目需要求长度，我们可以在stack里面存index， 这样可以很方便地得出长度的信息， 但是要注意stack 为空的时候，取top是会造成越界的，所以取top是有条件的。

33： search in rotated sorted array
这个题目算法是很清晰的，但是还是有一些细节需要注意， binary search 在计算Mid的时候， Mid 是会靠 left那边的，所以必定存在mid == left这种情况，这种情况下并不代表 array里面有重复元素，而是一般情况下都存在的情况。时间复杂度： O(logn)

34: search for a range
这个题目也是对sorted array进行search，所以肯定是要用到binary search的，需要找到target出现的左边界和target 出现的右边界，所以需要用到两次binary search， 找target出现的左右边界，用到binary search的变形，判断条件出来为Left=right-1，相邻的位置。 要注意最后跳出来的left 和 right中并不一定有target, 可能有找不到的时候， 这个时候-1.

35. insert position
这个题目也是对sorted array进行操作，找到元素应该insert的位置， 如果找到返回Index, 如果没有找到返回应该insert的位置， 可以看到insert的位置都是靠左insert的，在basic的binary search之后，最后我们直接返回left的结果就可以了。time complexity: O(logn)

36：valid sudoku
关键是9个小格子的坐标怎么求？board[3*(i/3)+(j/3)][3*(i%3) + (j%3)]
用27个array， 每次循环3个array, size =10， 分别表示行， 列，小3*3 九宫格。

37: sudoku solver
这个题目的做法也是解决一个类型题目的通用做法，那就是对每一个空的需要填值的位置进行填值， 有很多个填值的地方，每一个地方有很多种可能的选值，这里采用的DFS其实是brute force的思想，去try 每一种可能的取值，对一个位置进行取值之后就给下一个位置取值。在这个过程中，并不能保证所有的可能的取法都是正确的，所以dfs需要返回一个bool 值，表明这种做法是否可行，如果可行，返回true, 如果不行， 返回false。isValid只是判断当前填的位置是否可以，不能看到全局， 如果dfs不定义成返回值的话，最后不能知道当前的做法是否正确， 可能最后的board完全没有改变。

在另一篇博客里面看到如果用backtracking 的DFS来解题，大部分情况下都是有返回值的，因为不然backtracking的DFS会一直recursion下去导致死循环，这种有返回值的backtracking的做法含义是说存在正确错误的结果，或者成功失败的结果，比如这里sudoku solver是否能够成功解决。对于一些没有对错的问题，也是可以没有返回结果，感觉这里说到的点是我在做这个题目的时候所忽略的，很有用。

38： count and say
这个题目属于string compress类型的，关键是找重复的char的个数，
39:   combination sum
40:   combination sumII
这两题是DFS的题目， 画出DFS 树很容易解，但是要注意结束条件， target == 0 ， 这题跟coins combination 类似， 也是有一个target，第二题要求相同的字符不能重复使用，这个其实是I的follow up, 画出DFS tree 发现，其实只需要在同一层的时候不 push_back相同的element 就可以了。在当前层用一个unordered_set来去重。

41: first missing positive
这个题目其实是很常见的题目，一看知道应该是先要对array进行counting sort, 如果能够开辟一个新的array来进行counting sort的话，这个题目就很简单了，但是题目要求O(1)的space, 所以就只能inplace sort了，也是用的counting sort的思想， index i 对应的元素应该是 nums[i]-1， 就是说 i == nums[i]-1， 怎么样才能将array sort后具有这个特点呢？ 如果直接在i == nums[i]-1这个条件上想不太好想出来，因为也不知道是哪个Index对应的元素是nums[i]-1啊，不好swap，但是我们可以换个角度， 如果 i == nums[i]-1，那么 nums[i] == nums[nums[i]-1]， 这个时候我们swap nums[i], nums[nums[i]-1]就可以使得index nums[i]-1 对应的元素是mums[i]，对于<=0 或者超出 array size范围的数不进行处理就可以了， 这个题目感觉思路有点绕！