leetcode

二进制问题

338. Counting Bits

https://leetcode.com/problems/counting-bits/

问题

求0到n的二进制表示的1的数量

思路

二进制+进位处理+遍历统计1位数目(最低效)

代码
1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num+1, 0);
        for (int i = 1; i <= num; ++i)
            ret[i] = ret[i&(i-1)] + 1;
        return ret;
    }
};

重点在于 ret[i] = ret[i&(i-1)] + 1

  • 应该寻找序列规律
  • i&(i-1)的本质是2的次方所表示的范围
  • 思考i&(i-1)在算术上是什么作用

191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/

问题

求一个数的二进制表示法中的1的数量

代码
1
2
3
int hammingWeight(uint32_t n) {
    return n == 0 ? 0 : 1 + hammingWeight(n & (n - 1));
}
  • 思考i&(i-1)到底做了什么
    思路1
    使用&运算,(i&(i-1))的递推+1可得到二进制中1的数量
    思路2
    逻辑与运算1，像右移位并统计。

组合博奕

292. Nim Game

https://leetcode.com/problems/nim-game/

问题

一堆石头,你和对手都可以拿走1-3个石头,最后拿光的那个人赢,我先手,求是否能赢

思路

保持P状态就可赢,P状态指的是最小+最大可减数目=p状态
是否能进入p状态,n % 4 != 0 即可必胜

代码
1
2
3
4
5
6
class Solution {
public:
    bool canWinNim(int n) {
        return n&3;
    }
};

136. Single Number

https://leetcode.com/problems/single-number/

问题

给一数组,每个数都出现两次,除了一个,找出那一个数.

思路

异或算符的值为真仅当两个运算元中恰有一个的值为真，而另外一个的值为非真。
Xor运算 == 俩二进制不同为真

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

258. Add Digits

https://leetcode.com/problems/add-digits/

问题

给定一个非负数,对每位数进行相加,直到结果为一位数

思路

寻找规律,发现结果为对输入数进行9的求余

1
2
3
4
5
6
7
class Solution {
public:
    int addDigits(int num) {
		if (num < 9) return num;
		return (num %= 9) ? num : 9;
    }
};

104. Maximum Depth of Binary Tree

问题

求二叉树的最大深度

代码

Depth-first-search

1
2
3
4
5
6
class Solution {
public:
	int maxDepth(TreeNode* root) {
		return root == NULL ? 0 : max(maxDepth(root->left), maxDepth(root->right))+1;
	}
};

Breadth-first-search

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
int maxDepth(TreeNode *root)
{
    if(root == NULL)
        return 0;
    
    int res = 0;
    queue<TreeNode *> q;
    q.push(root);
    while(!q.empty())
    {
        ++ res;
        for(int i = 0, n = q.size(); i < n; ++ i)
        {
            TreeNode *p = q.front();
            q.pop();
            
            if(p -> left != NULL)
                q.push(p -> left);
            if(p -> right != NULL)
                q.push(p -> right);
        }
    }
    
    return res;
}