注意负数的情况，将基数和次方处理一下 这里使用分治减少一半复杂度 class Solution { public: double Power(double base, int exponent) { if (exponent < 0) { base = 1 / base; exponent = -exponent; } double res = 1; for (int i = 1; i <= exponent / 2; ++i) { res *= base; } res *= res; if (exponent % 2) { res *= base; } return res; }...

做C++练习题学到的。 n & n - 1 统计二进制中1的个数，这里考虑负数的情况需要先将其转换为无符号整数 统计二进制0的个数，使用 n | n + 1 class Solution { public: int NumberOf1(int n) { int res = 0; // 将其转为无符号整数 unsigned int num = n; while (num > 0) { ++res; // 每次消除一个1 num = num & (num - 1); } return res; } };

贪心需要数学定理，证明不了。。。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int cutRope(int n) { // 贪心 if (n <= 3) { return n - 1; } int res = 1; // 余下情况为 2 3 4，4 由 1 和 3 组成，分成 2 2 更大 while (n > 4) { res *= 3; n -= 3; } return res * n; } };  dp比...

一开始想错了，机器人只能从一个点进入，不可以随机挑选点进入 class Solution { public: int movingCount(int threshold, int rows, int cols) { int res = 0; std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols, 0)); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { matrix[i][j] = i %...

和岛屿问题很像，递归加回溯。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix char字符型vector<vector<>> * @param word string字符串 * @return bool布尔型 */ bool hasPath(vector<vector<char> >& matrix, string word) { if (matrix.empty()) { return false; } boo...

/* struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *right; struct TreeLinkNode *next; TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { } }; */ class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if (pNode->right) { // 当前结点有右子树，则寻找其...

递归或者翻转，递归空间换时间 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { std::vector<int> res; recursion(head, res); return res; } private: void recursi...

从后往前替换，避免每次都要挪动后面的元素 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string replaceSpace(string s) { if (s.empty()) { return ""; } int blank = 0; int old_size = s.size(); for (const auto &it : s) { if (it == ' ') { ++blank; } } ...

已知数据范围，利用哈希散射，统计对应值出现的次数。 通过两次遍历找出第一个重复的数字 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型vector * @return int整型 */ int duplicate(vector<int>& numbers) { if (numbers.empty()) { return -1; } int res = 0; std::vector<int> hash(numbers.size...

今天终于把101刷完了 不刷了，就重复刷这些题就好了。 接下来的时间要打好基础和项目。 class Solution { public: /** * lfu design * @param operators int整型vector<vector<>> ops * @param k int整型 the k * @return int整型vector */ vector<int> LFU(vector<vector<int> >& operators, int k) { capacity = k; std::vector<...

使用双向链表和哈希表实现 O(1) 时间复杂度 class Solution { public: Solution(int capacity) : lru(capacity), cap(capacity) { } int get(int key) { if (hash.count(key)) { auto tmp = *(hash[key]); lru.erase(hash[key]); lru.push_front(tmp); hash[key] = lru.begin(); return tmp.second; } return -1; } void set(int key, int va...

和矩阵移位一样，对比前后找规律 class Solution { public: vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) { for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { // 交换上三角和下三角 std::swap(mat[i][j], mat[j][i]); } } for (int i = 0; i < n; ++i) { std::reverse(mat[...

不断缩小边界 class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { if (matrix.empty()) { return std::vector<int>(); } std::vector<int> res; int left = 0, right = matrix[0].size() - 1, up = 0, down = matrix.size() - 1; while (left <= right &am...

原本以为跳着改变元素能够较快完成了已经，没想到这更简洁。。。 class Solution { public: /** * 旋转数组 * @param n int整型 数组长度 * @param m int整型 右移距离 * @param a int整型vector 给定数组 * @return int整型vector */ vector<int> solve(int n, int m, vector<int>& a) { // write code here m %= n; std::reverse(a.begin(), a.end()); std::reve...