01背包 class Solution { public: const int inf = 0x3f3f3f3f; int minMoney(vector<int>& arr, int aim) { int n = arr.size(); int dp[aim + 1]; memset(dp, inf, sizeof(dp)); dp[0] = 0; for(int i = 0; i < n; i ++){ for(int v = arr[i]; v...

回溯 class Solution { public: vector<vector<int>> res; vector<int> vec; void helper(const vector<int>& S, int start, int n){ if(start == n) return; for(int i = start; i < n; i++){ vec.push_back(S[i]); res.push_back(vec)...

模拟大法 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param s string字符串 第一个整数 * @param t string字符串 第二个整数 * @return string字符串 */ string solve(string s, string t) { // write code here while(s.length() > 1 && s[0]...

模拟题 class Solution { public: /** * 验证IP地址 * @param IP string字符串 一个IP地址字符串 * @return string字符串 */ string solve(string IP) { // write code here const string IPS[3] = {"IPv4", "IPv6", "Neither"}; int idx = 2; vect...

排序题 class Solution { public: /** * 最大数 * @param nums int整型vector * @return string字符串 */ string solve(vector<int>& nums) { // write code here sort(nums.begin(), nums.end(), [](int a, int b){ return to_string(a) + to_string(b) > to_...

后序遍历(1)跟[二叉树的最大路径和]一个思路，不同的是这里树不一定是二叉;(2)注意，起始根结点不一定是0，只要是叶子节点都可以作为根结点进行计算，另外边也不一定是从父节点到子节点，看用什么做根，所以邻接表需要无向边，而不是有向边。 /** * struct Interval { * int start; * int end; * }; */ class Solution { public: struct Node{ int v; int dis; Node(int _v, int _dis):v(_v), di...

数学如下表所示，每轮去掉的数的后一个数重新设置为0开头，重新排序0,1,2,...，然后逆向找对应的idx n m = 2 f(n,m) 5 0,√,2,3,4 f(5,2)=(f4,2)+2)%5=2 4 3,x,0,√,2 f(4,2)=(f(3,2)+2)%4=0 3 √,x,2,x,0 f(3,2)=(f(2,2)+2)%3=2 2 x,x,0,x,√ f(2,2)=(f(1,2)+2)%2=0 1 x,x,0,x,x f(1,2)=0 √表示每轮需要去掉的数，x表示每轮不存在的数时间复杂度：空间复杂度： class Solution { public:...

层序遍历序列化与反序列化 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(root == NULL) return NULL; queue<...

数学 class Solution { public: /** * * @param x int整型 * @return bool布尔型 */ bool isPalindrome(int x) { // write code here if(x < 0) return false; int ans = 0; while(x > ans){ ans = ans * 10 + x % 10; x /= 10; ...

字典树 class Solution { private: struct Trie{ int cnt; Trie* next[26]; Trie(){ cnt = 0; for(int i = 0; i < 26; i ++) next[i] = NULL; } }; Trie* root = new Trie(); public: /** * * @param strs string字符串vector * @r...

栈 class Solution { public: /** * * @param s string字符串 * @return int整型 */ int longestValidParentheses(string s) { // write code here int n = s.length(); stack<int> stk; stk.push(-1); //最后一次未匹配的右括号 int ans = 0; for(int...

回溯+排序剪枝 class Solution { public: vector<vector<int> > combinationSum2(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); int n = nums.size(); vis.resize(n, false); this -> target = target; helper(nums, 0, n, 0); ...

递归 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ bool hasPathSum(TreeNode* root, int sum) { // wr...

简单回溯 class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ vector<string> restoreIpAddresses(string s) { // write code here helper(s, 0, s.length(), 0); return res; } vector<string> res; string i...