可以每次右移一位遍历统计，也可以用n & (n - 1) 快速将最低位的1消去，统计消去所有1所需的次数，即为1的个数。原理：设n的最低位1为第i位，那么n肯定是这样的形式...10...0（i - 1个0），那么n - 1的形式为...01...1（i - 1个1），可以看出n与n - 1最低i位都互不相同，那么n & (n - 1) 的最低i位全部为0，这样就相当于消去了n的最低位1。class Solution { public: int NumberOf1(int n) { int res = 0; while (n) {...

2 * i的矩形可以由2 * (i - 1)的矩形竖放一块2 * 1的矩形得到，也可以由2 * (i - 2)的矩形横放两块2 * 1的矩形得到（不能计算竖放两块2 * 1的矩形，因为竖放一块时就是2 * (i - 1)的矩形，已经计算在上一种情况中了），所以写出递推式为dp[i] = dp[i - 1] + dp[i - 2]，可以看出又是斐波那契，由于i = 0时约定为0，所以起始位置的情况需要单独计算。class Solution { public: int rectCover(int number) { if (number <= 2) return nu...

第一步先写出递推式dp[n] = dp[n - 1] + dp[n - 2] + ... + dp[1]，然后观察，由于dp[n - 1] = dp[n - 2] + ... + dp[1]，化简后得到dp[n] = 2 * dp[n - 1]。class Solution { public: int jumpFloorII(int number) { if (number == 1) return 1; int res = 1; for (int i = 2; i <= number; i++) { res...

与斐波那契数一样，只是提前了一位而已。class Solution { public: int jumpFloor(int number) { if (number == 1) return 1; if (number == 2) return 2; int n1 = 1, n2 = 2, n3; for (int i = 3; i <= number; i++) { n3 = n1 + n2; n1 = n2; n2 = n3; ...

递推式为dp[i] = dp[i - 1] + dp[i - 2]，可以递归（重复计算占用大量时间空间，可能超时），也可以建立dp数组，但是观察递推式可以发现当前值只与前两次的值有关，所以可以将dp数组缩减为三个变量。class Solution { public: int Fibonacci(int n) { if (n == 1 || n == 2) return 1; int n1 = 1, n2 = 1, n3; for (int i = 3; i <= n; i++) { n3 = n1 + n2;...

二分查找，数组要么没有旋转，要么旋转成为两段局部有序的子数组。如果mid的值大于right端点的值，说明只可能是两段有序的子数组，且最小值必定出现在mid右端；如果小于，说明两种情况都可能存在，但此时最小值必定出现在mid左端；如果等于，无法判断最小值出现的区间，但是可以肯定right不会是唯一最小值（即使是最小值也有mid的值与它相同，减去没有影响），所以可以把right减一。class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int l = 0, r...

很经典的题了。第一个栈用来push，第二个栈用来pop。如果第二个栈为空，就把第一个栈的元素全部pop出来再依次push进第二个栈，因为栈是先进后出后进先出的，先进第一个栈的元素最后被pop出来push入第二个栈，因此最先从第二个栈被pop出来，简单来说就是负负得正。class Solution { public: void push(int node) { stack1.push(node); } int pop() { if (stack2.empty()) { while (!stack1.empty())...

与树有关的问题第一时间尝试递归，分解子问题。前序遍历的顺序是中左右，所以如果利用遍历结果建树，那么前序遍历数组的第一个数一定是根节点存储的树。在中序遍历数组中找到这个根节点存储的数，因为中序遍历的顺序是左中右，所以中序遍历数组中该数左边的部分一定是根节点左子树存储的数，该数右边的部分一定是根节点右子树存储的数。因为知道了中序遍历数组的左边界、右边界和根节点所在的下标，所以可以求出左子树、右子树的中序遍历数组长度，根据这些长度可以同样划分前序遍历数组。利用划分出来的左右子树的前序遍历、中序遍历数组，对左子树和右子树递归建树，最后将指针赋值给根节点的左右子树指针，返回根节点即可。class Sol...

两次遍历，一次统计长度，一次逆序输出。int* printListFromTailToHead(struct ListNode* listNode, int* returnSize ) { int *res; struct ListNode* tmp = listNode; int n = 0; while (tmp) { n++; tmp = tmp->next; } printf("%i", n); *returnSize = n; res = (int*)malloc(sizeof(in...

先统计空格个数。每个空格替换成%20，长度增加2，所以如果空格数为cnt，修改后的总长度为length + 2 * cnt，最大下标为length + 2 * cnt - 1。维护两个指针，一个指针j指向修改后字符串，i指向修改前字符串。因为是原地修改，且j比i移动得快，所以需要从后往前遍历，防止没有遍历到的数据被覆盖。class Solution { public: void replaceSpace(char *str,int length) { int cnt = 0; for (int i = 0; i < length; i++) { if (str[i] ==...

从左下角搜索到右上角（反过来也可以，原理一样）。因为数组从上到下、从左到右是有序的，所以如果当前查找的数大于target，那么其上方的数也一定会大于target；如果当前查找的数小于target，那么其左边的数也一定会小于target。bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) { int m = arrayRowLen - 1, n = 0; while (m >= 0 && n < *arrayColLen) { if (array[...