循环里面套循环，注意循环条件和终止条件即可： // // Created by jt on 2020/8/21. // #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int> > vec(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < ...

通过DFS实现回溯，关键在于两点：  去重（好好理解一下） 剪枝（不剪枝会超时）  class Solution { public: vector<vector<int> > combinationSum2(vector<int> &num, int target) { vector<vector<int> > res; vector<int> tmp; if (num.empty()) return res; sort(num.begin(), num.end()); dfs(num, target, res, ...

先排序，然后以第一个值为基准开始遍历，用双指针求第二个值和第三个值。 class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { sort(num.begin(), num.end()); vector<vector<int> > res; if (num.size() < 3) return res; for (int i = 0; i < num.size() - 2; ++i) { int j = i + 1; int ...

C++中优先队列的用法和普通队列无异，注意比较方式的写法： //升序队列 priority_queue <int,vector<int>,greater<int> > q; //降序队列 priority_queue <int,vector<int>,less<int> >q; //greater和less是std实现的两个仿函数在这里我们需要自定义比较，代码如下： struct comp{ // 自定义比较 bool operator()(ListNode *a, ListNode *b) { return a->...

这道题目玄之又玄，大家记住步骤就好啦：  处理空字符串 忽略前置空格 保存符号 处理非法输入 处理溢出  多想无益，就住就行了。 class Solution { public: int atoi(const char *str) { int idx = 0, sign = 1, val = 0; // 1. 空字符串 if (strlen(str) == 0) return 0; // 2. 忽略前置0 while (str[idx] == ' ') ++idx; // 3. 记录符号 if (str[idx] == '-') {sign = -1; ++idx;} if (str[idx]...

简单的进位和链表构造，只需要一个循环即可。 class Solution { public: /** * * @param l1 ListNode类 * @param l2 ListNode类 * @return ListNode类 */ ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { // write code here int value = 0; ListNode dummyHead(0); ListNode *p = &dummyHead; while (l1 || l2 || value != 0) { if (l1...

借助map辅助，用map记录每一个字符的最大的下标，用left记录没有重复字符子串的起始位置，空间复杂度和时间复杂度均为O(n)。 class Solution { public: /** * * @param s string字符串 * @return int整型 */ int lengthOfLongestSubstring(string s) { // write code here int size = s.size(); if (size < 1) return 0; unordered_map<char, int> um; int maxLen = 0, left...

时间复杂度为O(log(m+n))，直接想到二分法。 求两个排序数组的中位数，即求两个排序数组中：  第k个数（k=(m+n+1)/2，如果m+n为奇数） 第k个数与第k+1个数的平均值（k=(m+n)/2,k+1=1+(m+n)/2，如果m+n为偶数）  问题转化为求两个数组中的第k个数，分情况讨论：  如果一个数组为空，另一个数组不为空，直接返回另一个数组第k个值 如果两个数组都不为空，且k==1，返回两个数组起始值中较小的那一个 如果两个数组都不为空，且k!=1，那么采取类似二分法的思想，每次从其中一个数组中排除一部分值，具体见代码  // // Created by jt on 202...

借助map辅助： class Solution { public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ vector twoSum(vector &numbers, int target) { // write code here unordered_map m; // 1. 存储下标到map for (int i = 0; i < numbers.size(); ++i) m[numbers[i]] = i + 1; // 2. 再次扫描序列 for ...

KMP算法，关键在于求next数组，求next数组搞了好久都没搞懂，干脆记住算了。。。吧 // // Created by jt on 2020/8/14. // #include <string> using namespace std; class Solution { public: char *strStr(char *haystack, char *needle) { int size1 = strlen(haystack), size2 = strlen(needle); if (size2 == 0) return haystack; int next[size2],...

基本思想是自底向上，但是又可以细分为两种方法：  空间复杂度O(n)，优点是无需修改输入 空间复杂度O(1)，优点是无需辅助空间  方法一 // // Created by jt on 2020/8/14. // #include <vector> using namespace std; class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { vector<int> dp(triangle[triangle.size() - 1]); for...

两种方法：  辗转相减法（普通版，耗时684ms） 辗转相减法（升级版，耗时2ms，引入乘法，提高了相减的效率）  基本步骤如下：  保存符号 对两数取绝对值 辗转相减，记录次数 加上符号，得出结果  基本思想还是用位运算进行/模拟以下运算：求符号；求相反数；求加法/减法（本题可直接使用加法减法，但是升级版代码里我也实现了加法减法）。 辗转相减法（普通版） // // Created by jt on 2020/8/14. // using namespace std; class Solution { public: /** * * @param dividend int整型 * @para...

基础不牢，地动山摇，刚一开始误以为可以一次输入整行，呜呜～ #include #include using namespace std; int main() { string in; int size = 0; while (cin >> in) size = in.size(); cout << size << endl; return 0; }

这个动态规划有点难，因为f(i)不仅与f(i-1)有关，和f(i-2)也有关系，能想明白这一层关系着实不容易0.0 设当前的解法有f(i)种，由于s[i]和s[i - 1]的搭配方式有多种，下面分情况讨论：  非法的情况，即不论怎么搭配都decode不了，返回0 合法的情况，如果只能搭配成一种，那么f(i)=f(i-1)，如果能搭配成两种，那么f(i)=f(i-1)+f(i-2)  class Solution { public: /** * * @param s string字符串 * @return int整型 */ int numDecodings(string s) { // writ...