class Solution { public: // 哈希表，来一个字符，检查哈希表是否存在， // 不存在表示第一次出现则直接放入并设置成其下标表示只出现一次，若存在则把哈希表设置成-1表示出现过了 // 在获得第一次出现时，遍历哈希表 unordered_map<char, int> mp; int i = 0; //recorder the index of current sign //Insert one char from stringstream void Insert(char ch) { if (mp.find(ch) != mp.end()) { //foun...

class Solution { public: /** 由给出数组求得比其大一位的字典序排列-》大，则前面的小数要和后面的大数交换才能变大-》要变大得尽可能小，那么找到最小应该交换的位-》从后向前找到第 一个比后面的数小的数，与最后一个数交换（后面的数呈向前递增趋势，最后一个数最小）-》因为已经在一位上进行了变大，后面的位就要尽可能的小，即排序-》再把后面的数排序 */ vector<int> nextPermutation(vector<int>& nums) { if(nums.size() == 0 || nums.size() == 1){ retur...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <climits> class Solution { public: /** 判断是不是搜索二叉树，深度优先搜索-》比较左子树要小，右子树要大-》但是不能超过根节点作为子树的性质，左子树不能小于根节点作为右子树的父节点的值，依次类推，甚至更上层的树-》直接在深...

#include <unordered_map> class Solution { public: // question: 数组子集，能否组成字符串 // waht:用dp数组记录s[0]到s[i-1]能不能被组成 // dp[i] = find(s[j-1]-s[i-1]) && dp[j-1]; // why: 回溯，以数组为头遍历，凑一个，继续找下面的，不行就回溯； // 记忆就是，记录回溯，能否组成 bool wordDiv(string s, vector<string>& dic) { vector<int> dp(s....

class Solution { public: /* 有三种情况：偷第一家不偷最后一家；偷最后一家不偷第一家；首末两家都不偷； 动态规划进行， 分两种情况求解， 第三种情况包含 */ int rob(vector<int>& nums) { vector<int> dp(nums.size()+1, 0); int res =nums[0]; dp[1] = nums[0]; //选择偷第一家 for(int i=2; i<nums.size(); i++){ //最后一家不遍历 dp[i] = max( dp[i-1], nums[i-1]+dp[i-...

class Solution { public: /* 滑动窗口： */ int maxValue(string s, int k) { int temp = stoi(s.substr(0, k)); //初始化前k个 int maxval = temp; const int M = pow(10, k-1)+0.5; //k=2,两位，除以10取余，则需要1个10 //pow得到浮点型999.999，+0.5转成1000 for(int right = k; right < s.size(); right++){ temp = temp%M; //去掉首位 temp = temp*1...

#include <unordered_map> class Solution { public: int lengthOfLongestSubstring(string s) { if (s.empty())return 0; unordered_map<char, int> log; //记录窗口中有的字母和下标，便于检测 int left = 0, right = 0; //right是要验证的位置 int maxlen = 0; while (left <= right && right < s.size()) { if (log.f...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { if(arr.empty())return 0; vector<int> log(arr.size(), 1); // 记录以arr[i]结尾的最长上上升子序列的长度 int res=1; for(int i=1; i<ar...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: vector< vector<int>> ans = {}; vector<int> temp; vector<vector<int> > FindPath(TreeNode* r...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** 以每一个节点为起点，前序遍历，吃一个则sum就会改变 sum = sum - root->val; */ int res = 0; void dfs(TreeNode* root, int sum) { if (root ==...

#include <algorithm> class Solution { public: /** n 户人家 → n 个点（顶点） m 条路 → m 条边，每条边有一个权重（修路成本） 要让所有人家连起来（形成连通图），而且总成本最低 → 最小生成树（Minimum Spanning Tree, MST） 生成树:包含所有顶点,且n-1条边,也就是一条线连接所有顶点; 最小生成树:采用的边的代价和最小 Kruskal 的核心思想是一个贪心策略： 每次挑最便宜的路(按边的距离排序)，利用并查集, 如果两个节点还没有连接(不在一个集合里)，就修它(放到一个集合,累计成本)，直到所有村...

#include <queue> #include <utility> class Solution { public: /* 从起点开始，不断选择 当前距离最短且未访问 的节点，把它的邻居的距离更新成更短的值，直到所有节点都确定了最短距离。 创建邻接表->创建最短距离表、是否遍历过表->创建小根堆->初始化小根堆->循环:提取对顶,更新边能到的节点离起点的最近距离;直到堆为空; */ int findShortestPath(int n, int m, vector<vector<int> >& graph) {...

class Solution { public: /* 子序列：不是连续的；子串：连续的 同样都用dp[i][j]分别表示s[i]到s[j]的最长的回文子序列长度（int）、是否是回文子串（bool） 在子序列中： （2）dp[i][i]=1 （3）dp[i][j]=0(j<i) （4）dp[i][j]=dp[i+1][j-1]+2 (if s[i]==s[j]) （5）dp[i][j]=max(dp[i+1,j],dp[i,j-1]) (if s[i]!=s[j]) */ int longestPalindromeSubSeq(string s) { int n = s.size();...

#include <vector> class Solution { public: /** 将数组从小到进行排列，前面的长度一定小于等于后面的长度，从前往后更新长度即可，继承最长的可继承长度 */ int maxLetters(vector<vector<int> >& letters) { sort(letters.begin(), letters.end(), []( vector<int>& a, vector<int>& b) { //传入数组里的元素进行比较 if (a[0] == b[0])ret...