class Solution { public: int kmp(string S, string T) { if(S.empty() || S.size() > T.size()) return 0; //边界处理 int res = 0, next[S.size() + 1]; //结果和next数组，next[x]的意义是长度为x的前子串最长相同前后缀长度 next[0] = -1; //第0位设置成-1表示需要右移被匹配字符指针 for(int pre = -1, cur = 0; cur < S.si...

核心思路：每次扔的位置都是最佳的，i个棋子扔time次，第1次时，如果碎了，向下可以探测“i-1个棋子扔time-1次”层；如果没碎，向上可以探测“i个棋子扔time-1次”层。上下层数加当前1层即为i个棋子扔time次能探测的最大层数 class Solution { public: int solve(int n, int k) { if(n <= 1 || k == 1) return n; //层数小于等于1和棋子数等于1的情况 int best = log2(n) + 1; //棋子足够条件下扔的最小次数 if(k &gt...

class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> res; if(size > num.size()) return res; deque<pair<int, int> > dq; //严格递减队列 for(int cur = 0; cur < num.size(); cur++) ...

class Solution { private: typedef list<vector<int> > vecList; //定义元素为向量的双向链表，向量里为[频次，键，值] unordered_map<int, vecList> freq_map; //建立频次到双向链表的哈希表 unordered_map<int, vecList::iterator> key_map; //建立键到双向链表迭代器的哈希表（迭代器可以简单理解为在双向链表中的指针类，通过它可以得到里面的元素） int least = 0; /...

实际上这就是个dfs，对于每个字符有两种可能，一种是在后面加小数点，一种是不加，通过剪枝和条件判断来获得我们想要的结果 class Solution { public: vector<string> res; //记录最终结果 string str; vector<string> restoreIpAddresses(string s) { str = s; //将s作为全局变量好操作 helper("", 0, 0, 0); return res; } void helper(s...

class Solution { public: int solve(int* a, int aLen) { //a是数组指针，aLen是数组长度 int res = 0; for(int i = 0; i < aLen; i++) res ^= a[i] ^ (i + 1); //本质上是把a中所有数和0~aLen做异或运算，这样相同的数字抵消剩下a中没有的数字（0是res的初始值，所以这里实际上是1~aLen参与异或运算） return res; } };

class Solution { public: string LCS(string s1, string s2) { if(s1.empty() || s2.empty()) return "-1"; int dp[s1.size()+1][s2.size()+1]; for(int i = 0; i <= s1.size(); i++) dp[i][0] = 0; for(int j = 0; j <= s2.size(); j++) dp[0][j] =...

class Solution { public: string LCS(string str1, string str2) { int dp[str1.size()]; //以str1[i]、str2[j]结尾的子序列长度，以下简称sub[i][j] int max = 0, record = -1; //记录最大长度和str1起始位置 for(int i = 0; i < str1.size(); i++) { dp[i] = str1[i] == str2[0] ? 1 : 0; //初始化sub[i][...

class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* res = new ListNode(0); //省去判断链表头重复的情况 res->next = head; ListNode *pre = res, *cur = head; //记录前一个没重复的节点和当前节点 while(cur && cur->next) { //后面元素少于2个则不会重复 bool re...

class Solution { public: int minEditCost(string &str1, string &str2, int &ic, int &dc, int &rc) { int num1 = str1.size(), num2 = str2.size(); int dp[num2 + 1]; //记录每行遍历结果 for(int j = 0; j <= num2; j++) dp[j] = j * ic; //长度0的str1到长度i的str2，全部插入代价最小 ...

将每一个元素视作L左下角的数字，由矩阵性质可知L也是从小到大有序的，所以左下角数比上边所有数大，比右边所有数小。当左下角数大于x时，比左下角数更大的右边的数可以全部舍弃，于是左下角上移一格；当左下角数小于x数，比左下角数小的上边的数可以全部舍弃，于是左下角右移。最多可以舍弃n行m列（找到值的时候不舍弃直接返回了），所以时间复杂度最坏是O（n+m） class Solution { public: vector<int> findElement(vector<vector<int> > &mat, int n, int m, int x) { ...

class Solution { public: int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) { if(arr1.size() == 1) return min(arr1[0], arr2[0]); //若总数为2直接返回较小数即可 int l1 = 0, r1 = arr1.size() - 1, l2 = 0, r2 = arr2.size() - 1; //四个指针分别指向两个数组的首尾 int mid...

struct cmp { bool operator() (pair<string, int> &p1, pair<string, int> &p2) { return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first); //出现次数较高或者出现次数相同字典序小的优先级高（堆顶的元素优先级最低） } }; class Solution { public: vector<vector&lt...

class Solution { public: int solve(string s) { int res = 0; //用于返回当前字符串的计算结果 stack<int> sum; //用于求和 char sign = '+'; //记录前一个符号，初始化为+，因为可以看成当前字符串前先加0 int num = 0; //用于将连续数字字符串转化成数字或者记录递归结果 for(int i = 0; i < s.size(); i++) { //遍历每一个字符 i...