LeetCode刷题-68. 文本左右对齐
题目链接：68. 文本左右对齐
¶题解：
又是一道有点恶心的模拟题，刚开始竟然没有看懂题！
¶题目简述：
给定一堆单词，和一个最大长度，要求在不超过最大长度的条件下尽可能多放单词，并使得单词之间尽可能均匀分布！
¶题解：
题目解释：
假如一行放三个单词长度不超过最大长度，放四个超过了，则当前行只能放三个，还得保证三个单词之间的两个空隙尽可能相等（使用空格填充），如果无法相等，则保证左边的比右边的多一！
举个例子：
该行最多放四个单词，总长为9， 最大长度为20，则剩余空格数为11个，要均匀分布到三个空隙，所以11 / 3 = 3 … 2
所以三个空隙空格数依次为：3 + 1， 3 + 1，4 即可！
分析：
左对齐：
最后一行需要左对齐
某一行只有一个单词需要左对齐
左右对齐：一般情况，不是最后一行和不仅仅只有一个单词**！**
具体做法：
先找到一行能放的最大长度，该长度包括两个单词间的一个空隙
若为一个单词或最后一行，即j == words.size() || j == i + 1，将单词间隔一个空隙，后面的位置填补空格
若为一般情况，需要计算空隙数cnt = ...
LeetCode刷题-67. 二进制求和
题目链接：67. 二进制求和
¶题解：
类似于高精度加法！
¶题目简述：
两个二进制数的加法！
¶题解：
为了方便做加法，现将两个字符串倒序！
模拟加法即可！
循环终止条件：i < a.size() || i < b.size() || t
最终再次倒序，即为答案！
¶AC代码：
12345678910111213141516class Solution {public: string addBinary(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); string res; for(int i = 0, t = 0; i < a.size() || i < b.size() || t; i++){ if(i < a.size()) t += a[i] - '0'; if(i < b.size()) t += b[i] - '0 ...
LeetCode刷题-66. 加一
题目链接：66. 加一
¶题解：
简单题！
¶题目简述：
给定一个数字序列，最后一位加一，满十进一，求加一后的序列！
¶题解：
从最后一位开始，给他加一，然后更新当前位的值为digits[i] %= 10
t更新为digits[i] / 10
最后若进位到最前面，需要进行插入，即在最前面插入t即可!
¶AC代码：
12345678910111213141516171819202122232425262728293031class Solution {public: vector<int> plusOne(vector<int>& digits) { vector<int> res; int t = 1; for(int i = digits.size() - 1; i >= 0; i--){ digits[i] += t; t = digits[i] / 10; digits[i] %= 10; } ...
LeetCode刷题-65. 有效数字
题目链接：65. 有效数字
¶题解：
恶心人的字符串模拟题，边界条件一大堆！
¶题目简述：
判断一个字符串是否可以转化为数字！
¶题解：
步骤：
去掉首尾空格
若只有正负号，返回false
若只有一个.或者.e、.E都不成立，返回false
循环整个字符串：
对于.：若多于一个或者在e或E之后，返回false
对于e 或 E：e 或 E前后为空，或者多于一个，返回false
对于e 或 E：e 或 E后为正负号，且正负号后面没有数字，返回false
不是. e E 0-9：直接返回false
剩下其他情况合法，返回true
老多的边界条件！！！
¶AC代码：
12345678910111213141516171819202122232425262728293031323334353637383940class Solution {public: bool isNumber(string s) { int i = 0, j = s.size() - 1; // 去掉前后空格 while(i < s.size() &a ...
LeetCode刷题-64. 最小路径和
题目链接：64. 最小路径和
¶题解：
和前两道类似，同样使用动态规划！
¶题目简述：
给定一个方格，从左上走到右下，求最小代价！
¶题解：
动态规划：
状态表示： f[i][j]表示到达当前点的最小代价
状态计算： 在不越界的情况下 f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]
初始转态：f[0][0] = gird[0][0]
最终结果：f[n - 1][m - 1]
时间复杂度： $O(n \times m)$
¶AC代码：
12345678910111213141516class Solution {public: int minPathSum(vector<vector<int>>& grid) { int n = grid.size(), m = grid[0].size(); vector<vector<int>> f(n, vector<int>(m, INT_MAX)); f[0][0] ...
LeetCode刷题-63. 不同路径 II
题目链接：63. 不同路径 II
¶题解：
和上一道题相比多了一些障碍物设置，基本类似！
¶题目简述：
仍然是n * m的方格从左上到右下的路径数，路径中可能有障碍物！
¶题解：
动态规划：
状态表示：f[i][j]表示从起点到当前位置的路径数！
状态计算：由于到当前位置只有两条路径，即上和左，所以状态转移方程为，f[i][j] = f[i - 1][j] + f[i][j - 1]
初始状态由path[0][0]决定，若起点有障碍物，则f[0][0]为0，且最终方案数为0
若终点path[n - 1][m - 1]有障碍物，则最终方案数为0
以上两种情况需要特判！
最终结果：f[n - 1][m - 1]
与上一道题不同之处： 当前位置有了障碍物则到达当前位置的方案数为f[i][j] = 0
时间复杂度：$O(n \times m)$
¶AC代码：
1234567891011121314151617181920class Solution {public: int uniquePathsWithObstacles(vector<vector<int>& ...
LeetCode刷题-62. 不同路径
题目链接：62. 不同路径
¶题解：
简单的动态规划题目！
一个方格，算出从左上走到右下的不同方案数！
¶题解一：
直接爆搜，时间会爆炸的！
¶TLE代码：
123456789101112131415161718class Solution {public: int cnt; int n, m; int uniquePaths(int _m, int _n) { n = _n, m = _m; dfs(1, 1); return cnt; } void dfs(int x, int y){ if(x > n || y > m) return; if(x == n && y == m){ cnt ++; } dfs(x, y + 1); dfs(x + 1, y); }};
¶题解二：
使用动态规划：
状态表示：f[i][j]表示从起点到当前位置的路径数！
状态计算：由于到当前位置只有 ...
LeetCode刷题-61. 旋转链表
题目链接：61. 旋转链表
¶题解：
直接移动
¶题目简述：
将一个链表向后移动k个位置！
¶题解一：暴力
傻傻的移动k次即可，每次将倒数第一个节点指向最前面的头结点，倒数第二个节点指向空，完成一个交换即可！
由于k太大，会导致超时，所以请看题解二！
¶TLE代码：
1234567891011121314151617181920212223242526/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* rotateRight(ListNode* head, int k) { auto dummy = new ListNode(-1); dummy->next = head; if(head == NULL) re ...
LeetCode刷题- 60. 第k个排列
题目链接：60. 第k个排列
¶题解：
依次考虑每一位，很是巧妙的做法！
¶题目简述：
求一个序列字典序的第k个排列！
¶题解一：
直接使用全排列函数：next_permutation()
第k个序列，就是要循环k - 1次。
时间复杂度：$O(n! \times k)$
¶AC代码一：
1234567891011class Solution {public: string getPermutation(int n, int k) { string res; for(int i = 1; i <= n; i++) res += i + '0'; for(int i = 0; i < k - 1; i++){ next_permutation(res.begin(), res.end()); } return res; }};
¶题解二：
计数
思路：
从高到低依次考虑每一位
对于每一位，从小到大枚举没有使用过的数，确定当前位
看下方的一个例子： n = 4, ...
LeetCode刷题-59. 螺旋矩阵 II
题目链接：59. 螺旋矩阵 II
¶题解：
螺旋矩阵问题，和上一个基本类似。
¶题目简述：
给定一个数字 n，按照从右、下、左、上的顺序生成一个螺旋矩阵！
¶题解：
和54题-螺旋矩阵类似，同样使用两个方向数组，参考上一篇题解，同样是一个方向走到不能走就换方向。
此处的res数组存储每个位置要填的值！
¶AC代码：
12345678910111213141516171819class Solution {public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n, vector<int>(n)); int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; vector<vector<bool>> vis(n, vector<bool>(n)); for(int i = 1, x = 0, y ...
LeetCode刷题-58. 最后一个单词的长度
题目链接：58. 最后一个单词的长度
¶题解：
简单题！
¶题目简述：
返回最后一个字符串的长度！
¶题解：
思路：
先将末尾多余的空格过滤掉！
再从后往前扫描，进行统计，直到遇到第一个空格为止！
注意：
特判字符串为空的情况！
¶AC代码：
1234567891011121314class Solution {public: int lengthOfLastWord(string s) { if(s.size() == 0) return 0; int res = 0; int n = s.size() - 1; while(n && s[n] == ' ') n--; for(int i = n; i >= 0; i--){ if(s[i] == ' ') return res; res ++; } return res; }};
document.querySelectorAl ...
LeetCode刷题-57. 插入区间
题目链接：57. 插入区间
¶题解：
看似和上一题区间合并类似，实则没什么关系！
¶题目简述：
给一个按照区间左端点排序的列表，给定一个待插入区间，使得插入后，没有重叠元素！
¶题解：
由于已经排好序了，所以我们就不需要排序了！
分三段处理：
找到可以插入待插入区间的上一个区间，即从开始到该区间是不需要参与合并的，即a[k][1] < b[0]
找到可以和待插入区间合并的区间的最后一个区间，即a[k][0] <= b[1]，不断更新待插入区间的右端点，直到无法合并结束，此时区间为待插入区间
最后一段就是剩下的区间了，按顺序插入即可
看一下简图：
注意：
处理第二段不要越界，即k < a.size()
时间复杂度： 扫描一遍，为O(n)
¶AC代码：
123456789101112131415class Solution {public: vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) ...
