1. 位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。
示例 1：
输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为
32的 二进制串 。
进阶：
- 如果多次调用这个函数，你将如何优化你的算法？
出处：
https://edu.csdn.net/practice/26143233
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int hammingWeight(uint32_t n) { int count = 0; uint32_t res = 1; for (int i = 0; i < 32; i++) { if (res & n) { count++; } n >>= 1; } return count; } }; int main() { Solution s; uint32_t n = 0b00000000000000000000000000001011; cout << s.hammingWeight(n) << endl; n = 0b00000000000000000000000010000000; cout << s.hammingWeight(n) << endl; n = 0b11111111111111111111111111111101; cout << s.hammingWeight(n) << endl; return 0; }
输出：
3
1
31
代码2： bitset
C++11 用bitset.count()方法直接计数
int hammingWeight(uint32_t n) { bitset<32> bitN(n); return bitN.count(); }
#include <bits/stdc++.h> using namespace std; class Solution { public: int hammingWeight(uint32_t n) { bitset<32> bitN(n); return bitN.count(); } }; int main() { Solution s; uint32_t n = 0b00000000000000000000000000001011; cout << s.hammingWeight(n) << endl; n = 0b00000000000000000000000010000000; cout << s.hammingWeight(n) << endl; n = 0b11111111111111111111111111111101; cout << s.hammingWeight(n) << endl; return 0; }
2. 递归和非递归求和
编写一个递归函数和一个非递归函数，分别实现求1+2+3+...+n
出处：
https://edu.csdn.net/practice/26143234
代码：
#include <stdio.h> int sum(int n) { if(n == 1) return 1; else return n + sum(n-1); } int sum_2(int n) { int ss = 0; for (int i = 1; i <=n;i++) { ss += i; } return ss; } int main() { int n; printf("请输入n："); scanf("%d",&n); if(n == 0) { printf("请输入正整数n"); return -1; } int s1 = sum(n); int s2 = sum_2(n); printf("递归计算=%d;循环计算=%d\n",s1,s2); return 0; }
输出：
略
3. 俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
提示：
1 <= envelopes.length <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 104
出处：
https://edu.csdn.net/practice/26143235
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxEnvelopes(vector<vector<int>> &envelopes) { sort(envelopes.begin(), envelopes.end(), comp); vector<int> dp(envelopes.size(), 1); for (int i = 0; i < (int)envelopes.size(); ++i) { for (int j = 0; j < i; ++j) { if (envelopes[i][1] > envelopes[j][1]) dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1; } } int res = 0; for (int i = 0; i < (int)dp.size(); ++i) res = res > dp[i] ? res : dp[i]; return res; } static bool comp(const vector<int> &a, const vector<int> &b) { if (a[0] < b[0]) return true; else if (a[0] > b[0]) return false; else { if (a[1] > b[1]) return true; else return false; } } }; int main() { Solution s; vector<vector<int>> envelopes = {{5,4},{6,4},{6,7},{2,3}}; cout << s.maxEnvelopes(envelopes) << endl; envelopes = {{1,1},{1,1},{1,1}}; cout << s.maxEnvelopes(envelopes) << endl; return 0; }
输出：
3
1
