题型总结——leetcode 1870 准时到达的列车最小时速
1870. 准时到达的列车最小时速题目
思路思路来自leetcode的题解
1870. 准时到达的列车最小时速 - 力扣（LeetCode）
最直接的收获是浮点数运算的时候会出现误差，下面同样是摘自题解中的解释，
由于双精度浮点数无法准确表示诸如 2.01 这样的小数，我们在计算 2.01×100 时，算出的结果不是 201，而是 200.99999999999997 这样的数。
所以代码不能直接转成整数，而是要 round 一下。
round（）的作用简单来讲就是四舍五入
代码1234567891011121314151617181920212223242526272829303132class Solution {public: int minSpeedOnTime(vector<int>& dist, double hour) { //准时到达的列车时速 int n = dist.size(); long long h100 = round(hour * 100); long long delta = h100 - (n - 1) ...
题型总结——leetcode 6 Z字形变换
6. Z 字形变换题目
题解在进入思考状态后，这个对应的公式转换是可以被求出来的，只是因为代码实践上的差异，自己第一次写的时候没能得出正确答案。
常规的解法还是很简单的使用相应的举着进行模拟即可，只是没有什么挑战可言，并且在时间和空间复杂度上也不是很让人满意。
代码123456789101112131415161718192021222324252627282930class Solution { public: string convert(string s, int numRows) { if (numRows == 1 || numRows >= s.length()) { // 如果numRows为1或者大于字符串长度，则无需转换 return s; } string result = ""; int cycleLen = 2 * numRows - 2; // 一个完整Z ...
题型总结——leetcode 151 反转字符串中的单词
151. 反转字符串中的单词题目
题解最先想到是自己去拆解，这里介绍一种新的方法，stringstream，同时，虽然可以通过对原来的空格进行erase操作来实现，但是频繁的改变这东西会导致stirng频繁重新分配内存，建议少用，看看下面的 拆解 的标准答案。
代码拆解123456789101112131415161718192021222324252627class Solution {public: string reverseWords(string s) { ranges::reverse(s); int n = s.length(); int idx = 0; for (int i = 0; i < s.length(); i++) { if(s[i] != ' ') //跳过空格 { if(idx != 0) s[idx++] = ' '; //除去第一个单词外，剩下的单词都要在首部添加一个空格 int en ...
题型总结——leetcode 43 字符串相乘
43. 字符串相乘题目
题解和字符串模拟加法一样，属于必背题型
代码12345678910111213141516171819202122232425262728293031323334class Solution{public: string multiply(string num1, string num2) { int m = num1.size(), n = num2.size(); // 结果最多为 m + n 位数 vector<int> res(m + n, 0); // 从个位数开始逐位相乘 for (int i = m - 1; i >= 0; i--) for (int j = n - 1; j >= 0; j--) { int mul = (num1[i] - '0') * (num2[j] - '0'); ...
题型总结——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 ...