leetcode第三部分

关于递归，回溯，位运算

今天我的心情非常不爽

不是因为今天过节，而是因为我拒绝了谷歌的现场笔试。

我知道这个机会非常来之不易，本来可以去瞻仰一下谷歌的工作氛围的，作为一个程序员，我是多么渴望进谷歌看看。但是500道的leetcode，我才做了不到一百道，这简直是在扯犊子，所以被迫临时取消了。

唉，机会总是留给有准备的人。我不是（微笑脸

这里是一个缓冲区，因为单拿出来每一个都是一大堆题目，留待后续整理

递归

读到研二递归还没弄明白其实挺难过的

递归算法详解

汉诺塔问题里的代码如下：

1
2
3
4
5
6
7
8
9
10
void Hanoi (int n, char A, char B, char C){
    if (n==1){ //end condition
        move(A,B);//‘move’ can be defined to be a print function
    }
    else{
        Hanoi(n-1,A,C,B);//move sub [n-1] pans from A to B
        move(A,C);//move the bottom(max) pan to C
        Hanoi(n-1,B,A,C);//move sub [n-1] pans from B to C
    }
}

为什么种子值只有move(A,B)呢

因为A，B是两个变量不是盘子A和盘子B呀大傻子

递归的核心是从父节点向子节点迁移

  • 定义函数功能
  • 结束条环
  • 结束过程

回溯

以22. Generate Parentheses为例说一下回溯

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

所谓 Backtracking 都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集

所以你思考递归题时，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。即 “ORT 原则”（这个是我自己编的）

对于这道题，在任何时刻，你都有两种选择：

  1. 加左括号。
  2. 加右括号。

同时有以下限制：

  1. 如果左括号已经用完了，则不能再加左括号了。
  2. 如果已经出现的右括号和左括号一样多，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。

结束条件是：

左右括号都已经用完。

结束后的正确性：

左右括号用完以后，一定是正确解。因为

  1. 左右括号一样多
  2. 每个右括号都一定有与之配对的左括号。因此一旦结束就可以加入解集（有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断）。

递归函数传入参数：

限制和结束条件中有 “用完” 和“一样多”字样，因此你需要知道左右括号的数目。
当然你还需要知道当前局面 sublist 和解集 res。

因此，把上面的思路拼起来就是代码：

1
2
3
4
5
6
7
8
9
10
if (左右括号都已用完) {
  加入解集，返回
}
// 否则开始试各种选择
if (还有左括号可以用) {
  加一个左括号，继续递归
}
if (右括号小于左括号) {
  加一个右括号，继续递归
}

但是注意这个题里得看顺序，左括号和右括号不是任意排列的，所以还得判断l > r才行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 0:
            return []
        res = []
        self.helper(n, n, '', res)
        return res
        
    def helper(self,l,r,item,res):
        # 只有在右括号比左括号少的时候才有必要继续
        if r < l:
            return
        # 左右括号都已用完,加入解集，返回
        if l == 0 and r == 0:
            res.append(item)
        # 还有左括号可以用
        if l > 0:
            self.helper(l - 1,r,item+'(',res)
        # 还有右括号可以用
        if r > 0:
            self.helper(l,r - 1,item+')',res)

这其实是一个卡特兰数

我们可以来看一下卡特兰数

位运算

477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

1
2
3
4
5
6
7
8
9
10
Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        xor = x ^ y
        count = 0
        for i in range(32):
            # 原来逐位这么写呀
            count += (xor >> i) & 1
        return count

上面的遍历每一位的方法并不高效，还可以进一步优化，假如数为 num, num & (num - 1) 可以快速地移除最右边的 bit 1， 一直循环到 num 为 0, 总的循环数就是 num 中 bit 1 的个数。参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingDistance(int x, int y) {
        int res = 0, exc = x ^ y;
        while (exc) {
            ++res;
            exc &= (exc - 1);
        }
        return res;
    }
};

477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

1
2
3
4
5
6
7
8
Input: 4, 14, 2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

这道题是之前那道 Hamming Distance 的拓展，由于有之前那道题的经验，我们知道需要用异或来求每个位上的情况，那么我们需要来找出某种规律来，比如我们看下面这个例子，4，14，2 和 1：

4: 0 1 0 0

14: 1 1 1 0

2: 0 0 1 0

1: 0 0 0 1

我们先看最后一列，有三个 0 和一个 1，那么它们之间相互的汉明距离就是 3，即 1 和其他三个 0 分别的距离累加，然后在看第三列，累加汉明距离为 4，因为每个 1 都会跟两个 0 产生两个汉明距离，同理第二列也是 4，第一列是 3。我们仔细观察累计汉明距离和 0 跟 1 的个数，我们可以发现其实就是 0 的个数乘以 1 的个数，发现了这个重要的规律，那么整道题就迎刃而解了，只要统计出每一位的 1 的个数即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        for x in range(32):
            mask = 1 << x
            zero = one = 0
            for num in nums:
                if num & mask:
                    one += 1
                else:
                    zero += 1
            ans += zero * one
        return ans

476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:

1
2
3
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

mask – 1为和num二进制位等长的所有位数为1的数，与num取^可以得到和num相反的数字。

真是机智啊

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        mask = 1
        tmp = num
        while(tmp):
            tmp >>= 1
            mask <<= 1
        return (mask - 1) ^ num

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

注意审题！敲黑板

这道题给我们 n 个数字，是 0 到 n 之间的数但是有一个数字去掉了，让我们寻找这个数字，要求线性的时间复杂度和常数级的空间复杂度。那么最直观的一个方法是用等差数列的求和公式求出 0 到 n 之间所有的数字之和，然后再遍历数组算出给定数字的累积和，然后做减法，差值就是丢失的那个数字

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        s = n * (n + 1) * 0.5
        missingnum = int(s - sum(nums))
        return missingnum

思路是既然 0 到 n 之间少了一个数，我们将这个少了一个数的数组合 0 到 n 之间完整的数组异或一下，那么相同的数字都变为 0 了，剩下的就是少了的那个数字了，参加代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            res ^= (i + 1) ^ nums[i];
        }
        return res;
    }
};

342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

Credits:
Special thanks to @yukuairoy for adding this problem and creating all test cases.

Subscribe to see which companies asked this question.

从数学的角度出发，数 num 是 4 的阶乘需要满足的条件是

1）(num -1)%3 == 0

2）num & (num-1) == 0

另外一道题，数 num 是 2 的阶乘需要满足的条件是

num & (num-1) == 0

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0:
            return False
        if num == 1:
            return True
        if num & (num - 1) == 0 and (num - 1) % 3 == 0:
            return True
        return False

405. Convert a Number to Hexadecimal

将数字转化为 16 进制字符串，负数采用补码表示。不允许使用系统函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def toHex(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num < 0: 
            num += 0x100000000
        ans = []
        hexs = '0123456789abcdef'
        while num:
            ans.append(hexs[num % 16])
            num /= 16
        if ans:
            return ''.join(ans[::-1])
        return '0'

389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.

利用异或的性质，相同位返回 0，这样相同的字符都抵消了，剩下的就是后加的那个字符

1
2
3
4
5
6
7
8
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        return chr(reduce(operator.xor, map(ord, s + t)))

map()和reduce()函数

Add Two Numbers 两数相加

Write a function that adds two numbers. You should not use + or any arithmetic operators.

这道题让我们实现两数相加，但是不能用加号或者其他什么数学运算符号，那么我们只能回归计算机运算的本质，位操作 Bit Manipulation，我们在做加法运算的时候，每位相加之后可能会有进位 Carry 产生，然后在下一位计算时需要加上进位一起运算，那么我们能不能将两部分拆开呢，我们来看一个例子 759+674

  1. 如果我们不考虑进位，可以得到 323

  2. 如果我们只考虑进位，可以得到 1110

  3. 我们把上面两个数字假期 323+1110=1433 就是最终结果了

然后我们进一步分析，如果得到上面的第一第二种情况，我们在二进制下来看，不考虑进位的加，0+0=0， 0+1=1, 1+0=1， 1+1=0，这就是异或的运算规则，如果只考虑进位的加 0+0=0, 0+1=0, 1+0=0, 1+1=1，而这其实这就是与的运算，而第三步在将两者相加时，我们再递归调用这个算法，终止条件是当进位为 0 时，我们直接返回第一步的结果，参见代码如下：

1
2
3
4
5
6
int add(int a, int b) {
    if (b == 0) return a;
    int sum = a ^ b;
    int carry = (a & b) << 1;
    return add(sum, carry);
}

参考链接

举个例子: 11+5, 其二进制形式为 11: 1011, 5: 0101

  1. 那么两个位置都为 1 的地方就需要进位, 所以进位值就为 0001. 原位置两个数相加的结果为那个位置值的异或即 1110, 即两个位置值如果不一样就为 1, 一样的话要么两个位置原来值都为 0 结果也为 0, 要么进位, 那么结果依然是 0.

  2. 接下来就要把进位位和下一位相加, 所以进位值左移一位, 即 0001 变为 0010, 重复上面操作可得新的进位值为 0010, 原位置异或 (即相加) 结果为 1100.

  3. 继续重复上面操作直到进位为 0, 可得到最终结果 10000, 即 16

进位：与运算
相加：异或

python版本非常崩溃反正我没看懂

一个不成熟的小问题

动态规划

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

求和最大的连续子数组

滑动窗口

属于一种 DP 问题。已知了前 k 个元素的最大子序列和为 maxSub（已经被记录下来了），以及一个临时和 sum，如果添加了第 k+1 这个元素，由于是连续子序列这个限制，所以如果 k+1 这个元素之前的和是小于 0 的，那么对于增大 k+1 这个元素从而去组成最大子序列是没有贡献的，所以可以把 sum 置 0。举个例子，-1， -2 ，4， -5， 7 这里假定 7 为第 k+1 个元素，那么很明显可以看出，之前的 sum = -5 + 4 =-1，那么这样对于 7 来说只会减少它，所以直接置 sum = 0， 0 + 7 才能得到正确的答案。再拓展这个数组， -1， -2， 4， -5， 7， 1 这里 1 之前的 sum = 7 > 0，对于后面的 1 来组成最大子序列是有贡献的，所以 sum = 7 + 1 =8。再注意一点，只要 sum 不减到负数，中间出现小于 0 的元素是没关系的，sum 仍然可以继续累加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        cursum = 0
        maxSum = nums[0]
        for num in nums:
            if cursum < 0:
                cursum = 0
            cursum = cursum + num
            maxSum = max(cursum,maxSum)
        return maxSum
算法
算法