题型总结——leetcode 12 整数转罗马数字
12. 整数转罗马数字题目
题解这道题目难点在堆三个条件的理解上，其余的就是常规的将一个int数按照位数拆开后对照
代码12345678910111213141516class Solution { //罗马数对照表 static constexpr string R[4][10] = { {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}, // 个位 {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXX ...
题型总结——leetcode 5 最长回文子串
5. 最长回文子串题目
题解代码暴力解决12345678910111213141516171819202122232425262728293031323334353637383940bool isPalindrome(string& s, int left, int right){ while (left < right) { if (s[left++] != s[right--]) return false; } return true;} string StringTopic::longestPalindrome(string s){ int n = s.length(); //长度不够的时候，默认是回文串 if (n < 2) return s; //求解最长回文子串 //滑动窗口 int left = 0, maxLen = 1, right = 1; string res(1, s[0]); for (; left < n - 1; ++left) { right = left ...
题型总结——leetcode 304 二维区域和检索-举着不可变
304. 二维区域和检索 - 矩阵不可变题目
解法很容易就能看出来这道题是二维的前缀和，但是之前缺少类似的经验，再加上情况比较特殊，直接看的标准答案。
主要核心是使用+1来表示当前点位上从0 0 到i j位置区间内的和
代码123456789101112131415161718192021class NumMatrix { vector<vector<int>> sum;public: NumMatrix(vector<vector<int>>& matrix) { int m = matrix.size(),n = matrix[0].size(); sum.resize(m+1,vector<int>(n+1)); for(int i =0;i<m ;i++) { for(int j = 0;j<n;j++) { // ...
题型总结——leetcode 73 矩阵置零
73. 矩阵置零题目
解法常规的解法常见，在不考虑空间复杂度的情况下，可以重新开一个同等大小的矩阵保存数据集，之后替换即可，也可以在遍历的过程中使用两个数组预先保存本来就是0 的位置，在本地置零操作完成后再去处理数组中的内容，空间复杂度得到一定优化。
如果矩阵中的元素没有包括一个int所能表示的所有范围的话，还是可以用标志变量去标记原本的0和新变的0。时间和空间复杂度分别是Om*n，O1
代码这个方法是将全局的0都映射到数组上。
1234567891011121314151617181920212223void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector<int> row(m), col(n); //全局的0映射 for (int i = 0; i < m; i++) { ...
题型总结——leetcode 289 生命游戏
289. 生命游戏题目
解法很简单的一道题目，很容易想到重新开辟一个相同大小的二维数组进行结果替换，但是这样就存在一个相对较大的额外空间复杂度，
建议使用新的变量来替代表示同时又不干扰别的内容运行。例如之前是1，下一个状态是0，就可以用4来表示，同理，0变成1 可以用3表示，最后再遍历一次将所有的变成 0 就可以了。因为简单，这里不给出代码
这段代码主要演示的是在一个二维数组中该如何对给定点位周围的点进行探查，使用数组预先处理好要变化的距离，判断越界情况后正常处理即可。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667pair<int, int> arr[8] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1} ...
题型总结——leetcode 306 累加数
306. 累加数题目
解法这道题目其实不难，纯粹的步骤多点，一开始自己写的时候没有好好审题，做了一些无用功从而导致解题的精力被浪费掉一部分。
解题的关键就在1 和 2 的数据上，穷尽前两个的排序才能继续进行下去
都是常用的代码，字符串模拟运算，斐波那契数列的检验
提醒一下，不要被 回溯 给干扰自己对穷举的判断
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990bool StringTopic::isAdditiveNumber(string num){ //穷举1和2 位置上的所有组合 int n = num.length(); //穷举second的所有可能性 for (int secondStart = 1; secondStart < n-1; ++secon ...
题型总结——leetcode 54 螺旋矩阵
54. 螺旋矩阵题目
解法这道题目的解法其实并不是很难，自己最开始写的时候是想着一个循环中只是处理数据，对于下个要添加进去的数据则是需要有很多辅助if去判断，问题就出在这里，正确的、容易理解发解法就是下面这个
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748vector<int> Array::spiralOrder(vector<vector<int>>& matrix){ int m = matrix.size(); int n = matrix[0].size(); if (m == 0 || n == 0) return {}; vector<int> res; int left = 0, right = n - 1, top = 0, buttom = m - 1; while (left <= right && top <= but ...
题型总结——leetcode 2555 两个线段获得的最多奖品
2555. 两个线段获得的最多奖品题目
解法实际这道题目是动态规划的思想，最开始自己写的思路是找出一个线段的最大值再去在剩下的不重合区间内寻找下一个线段的最大值，但是这种情况下二者的 和 （最终的结果）不一定是最大的，前期的思路准备很重要
代码123456789101112131415161718192021222324252627282930int Array::maximizeWin(vector<int>& prizePositions, int k){ int n = prizePositions.size(); //对解雇是整个数组长度的情况提前进行解决 //使用 k *2 + 1 是考虑到数组长度是偶数的时候，,同时> 的使用也把原本的奇数包括进去 if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) { return n; } int ans = 0, mx = 0, left = 0, right = 0; ...
题型总结——leetcode 448 找到数组中消失的数字
448. 找到所有数组中消失的数字题目
解法根据题目给出的要求，正确数组应该是所有数字各不相同，即意味着所有所有数据都可以看做是该数组的有效索引+1，
在第一个for循环中处理的就这这个内容，将数据转换为索引并在对应的位置上+n， %n的操作是防止该位置上的值已经被+n过从而导致索引越界。
123456789101112131415161718192021222324vector<int> Array::findDisappearedNumbers(vector<int>& nums){ int n = nums.size(); //索引处理 for (int& x : nums) { int i = (x - 1) % n; nums[i] += n; } //最后的结果是根据索引来处理，那个值没有变动，就代表这个位置的索引+1的数没有出现 vector<int> res; for (int i = 0; i < n; i++) { cout << ...
题型总结——leetcode 414 第三大的数
414. 第三大的数题目
解法三种解法
排序
有序集合
一次遍历
排序非常常规且容易想到的解法，只不过在时间复杂度上不是很友好
123456789int thirdMax(vector<int> &nums) { sort(nums.begin(), nums.end(), greater<>()); for (int i = 1, diff = 1; i < nums.size(); ++i) { if (nums[i] != nums[i - 1] && ++diff == 3) { // 此时 nums[i] 就是第三大的数 return nums[i]; } } return nums[0]; }
有序集合长时间没有使用Set，甚至忘记了有这东西，第一时间先到的是双端队列这种东西，set会对插入的内容进行一个排序处理，beg ...