LeetCode刷题-12.整数转罗马数字
题目链接：12.整数转罗马数字
¶题解：
嗯，，这题挺简单，字符串处理，我使用了具有对应关系的哈希表！
¶题目简述：
给定了一个正数，转化成罗马数字。
例如：1994---------> “MCMXCIV”
¶题解：
罗马数字就是下面十三种字母的组合，首先使用一种数据结构将对应的数字与罗马数字对应起来！
这里我使用了unordered_map哈希表存储！
和每次将一个数取余取除类似，可以搞到每一位！
所以：思路就是将普通数字，一直对高位取除，即从1000、900、500…1，取除：
如果等于0，则说明剩余部分比该数字要小，直接跳过；
不等于0，则进行处理，将str 累加一下对应的字符t次，即可
每次进行取余计算剩下的即可！
¶AC代码：
1234567891011121314151617181920212223242526272829303132class Solution {public: string intToRoman(int num) { unordered_map<int, string> hash; int ...
LeetCode刷题-11.盛最多水的容器
题目链接：11.盛最多水的容器
¶题解：
双指针使用，巧妙的思路！
也是不太好理解！多看看！
¶题目简述：
给了一堆柱子及其高度，要求选出两个柱子，使得凹槽内的面积达到最大，当然两根柱子要选较低的一根作为高，否则会发生漏水！
¶题解一：
本题可以使用暴力，直接两层循环，但是会超时！
所以可以使用双指针算法：
先给出具体思路：两个指针（i 和 j）一个从左走，一个从右走，若左边的比右边的高，则高的一边往内靠，即左面的往后走，右面的往前走，i++，j--，直到i == j结束。
给出证明一：
假设最优解对应的下标为i', j'（i' < j'），在两指针（i, j）移动的过程中不断靠近最优解，先假设i 先走到 i'，且此时j' < j。
反证：假设此时 a[i] <= a[j]，用s表示i,j盛水的面积，s'表示i',j'盛水的面积，则：
s = min(a[i], a[j]) * (j - i) = a[i] * (j - i)
s' = min(a[i'], a[j']) * (j' - i') = min(a[i], a[j']) * (j' - i) ...
LeetCode刷题-10.正则表达式匹配
题目链接：10.正则表达式匹配
¶题解：
又是一道很难的动态规划题，或许他不难，只是我遇到动态规划的题太少了罢了！
历时很久才将其看懂：还是 y 总牛逼！
¶题目简述：
正则匹配：处理两个字符* 和 .
*：表示0个或多个
.：任意一个字符
给一个字符串，给一个正则，检查能否匹配。
¶题解：
使用闫式Dp分析法：（集合的方式）
再字符串前面加一个空格，使子符串从1开始！
分为状态表示和状态计算：
转态表示：两个字符串，则使用两维数组f[i][j] ，来表示原串和正则串的 [1, i] 个 和 [1, j] 个是否匹配，存储的是bool值（表示是否存在一个合法方案，由于*的原因导致方案不唯一）。
状态计算：（分为两种情况）
p[j] != '*'：则f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == .)
p[j] == '*'：则f[i][j] = f[i][j-2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')
...
LeetCode刷题-9.回文数
题目链接：9. 回文数
¶题解：
虽然简单，但是还是有可以优化的地方！
¶题目简述：
给一个 int 类型的数，判断是不是回文数！
注意：-121 反转后 为 121- 不是回文数。
¶题解一：循环
嗯，太简单了，不写解释了！
注意一点：int 正序可能没溢出，但是反转过来就不一定没有溢出，所以，要用 long long 来存储一下！
¶AC代码：
123456789101112class Solution {public: bool isPalindrome(int x) { if(x < 0) return false; long long t = 0, r = x; while(r){ t = t * 10 + r % 10; r /= 10; } return t == x; }};
¶题解二：循环优化
由于是回文串，那么如果是的话，他的前半部分和后半部分是完全一样的，所以我们可以只处理一半即可得到答案。
如果为负数和末尾有0一定不是回 ...
LeetCode刷题-8.字符串转换整数(atoi)
题目链接：8.字符串转换整数(atoi)
¶题解：
细节特别多，水题！
¶题目简述：
将字符串开头是数字的抠出来！
¶题解：
大致有一下这五种情况：
<空格>123：返回123
+123：返回123
-123：返回-123
+-123或-+123：返回 0
w123： 返回 0
注意：如果转换后的数字大于INT_MAX 或小于INT_MIN，返回INT_MAX 或INT_MIN。
注意：long long也不一定能存下，所以只要超过INT_MAX 或INT_MIN就返回INT_MAX 或INT_MIN。
具体解释：查看代码中注释。
¶AC代码：
12345678910111213141516171819202122232425class Solution {public: int myAtoi(string str) { int i = 0, t = 1; long long res = 0; // 处理开头空格 while(str[i] == ' ') i++; // 处理++ -- ...
LeetCode刷题-7.整数反转
题目链接：7.整数反转
¶题解：
水题一个！
¶题目简述：
正负数都倒序输出即可，负数处理完还是负数。
¶题解：
正负数的原因，应该分开处理，但是C++取余不区分正负，和数学不一样，会区分正负。
题目有 2 ^ 31的限制，即 int的最大最小值，使用INT_MAX 和 INTMIN即可，头文件位于climits中。res定义为long long防止溢出。
注意：不要使用 2 << 31，会溢出的，结果为 0。
¶AC代码：
123456789101112class Solution {public: int reverse(int x) { long long res = 0; while(x){ res = res * 10 + x % 10; x /= 10; } if(res > INT_MAX || res < INT_MIN) return 0; return res; }};
document.qu ...
LeetCode刷题-6.Z字形变换
题目链接：6.Z字形变换
¶题解：
完全就是找规律，找到每行下标的规律即可，为一个等差数列！
¶题目简述：
将字符串按倒Z型排列，然后按行读取完整字符，输出对应字符串！
¶题解：
以一个容易发现规律的例子来解释：
以四行为例：
12340 6 121 5 7 11 13 ..2 4 8 10 14 163 9 15
第一行和最后一行公差相同，为 2 * n - 2，即从0 - 6 中间隔了1-3 和 4 - 6 即两个 n - 1.
中间其他行，看做两个等差序列的混合，分别去处理，竖线上的同样是以2 * n - 2为公差的等差数列，不在竖线上的是以2 * n - 2 - i为首项，以2 * n - 2为公差的等差数列！
2 * n - 2 - i：会发现 1 + 5 = 6 2 + 4 = 6，即 i + x = 2 * n - 2，x = 2 * n - 2 - i
注意： n = 1时，2 * n - 2为零，循环为死循环，所以进行特判，返回原串 s。
¶AC代码：
123456789101112131 ...
LeetCode刷题-5.最长回文子串
题目链接：5.最长回文子串
¶题解：
本题有一个将时间复杂度降到O(N)的算法：马拉车算法 Manacher‘s Algorithm
此算法专门由于求解最长回文子串问题！但是 y总说不太常用！
还有一个O(NlogN)的算法：哈希 + 二分
有点困难，能力强了再去玩玩！
本次：使用枚举暴力做法！时间复杂度 O(n^2)
¶题目简述：
求解最长回文子串！若不止一个最长，随便输出一个！
¶题解：
使用暴力枚举即可：
使用两个指针 l, r, 从中间往两边扩即可！
奇数：另 l = i - 1, r = i + 1
偶数：另 l = i, r = i + 1
条件：
l >= 0 && r < s.size() && s[l] == s[r]：即可以往两边移
str.size() < r - l -1：即当前回文子串更长，则更新 str
时间复杂度：O(n^2)
¶AC代码：
12345678910111213141516class Solution {public: string longestPalindrome(s ...
LeetCode刷题-4.寻找两个正序数组的中位数
¶首先来首歌曲来放松一下吧！
题目链接：4.寻找两个正序数组的中位数
¶题解：
此题 y总 的链接！
此题据 y总 说是LeetCode最难题目之一！
这个题目或许又可以称为 求解第k小数问题
¶题目简述：
两个有序序列，求中位数！
有一个很 优秀的要求：时间复杂度要控制在 O(log(m + n))
¶题解一：
先不看题目时间复杂度的要求：使用二路归并进行，时间复杂度O(n + m)
由于时间也不算太慢，还是可以AC的。题解二将使用更优秀的算法解决。
二路归并：思路，每次两两比较，将较小值放到新的容器。若某一个遍历完毕，则将没有遍历完的另一个一次放到新的容器。
本题奇偶两种情况处理，奇数位的中位数为 len > 1， 偶数位的中位数为 len > 1 和 (len > 1) - 1 和的均值！
注意点：返回值为double，所以记得乘以 1. 0 或除以 2.0
¶AC代码1：
12345678910111213141516class Solution {public: double findMedianSortedArrays(vect ...
LeetCode刷题-3.无重复字符的最长子串
题目链接：3.无重复字符的最长子串
¶题解：
双指针形成的滑动窗口实现！双指针被形象表示为滑动窗口！
¶题目简述：
两个概念：
子串：连续的
子序列：不一定连续，下标递增
找出一个字符串中最长不重复的子串，返回最大长度！
¶题解：
使用两个指针i, j，（j < i）, 区间[j, i]表示以 i 为尾的子串的区间。
使用 unordered_map<char, int> hash来表示 字符出现的次数。
双指针扫描时来维护该区间[j, i]，使得该区间为以 i 为底的，保证不重复的最大区间。
初始[j, i]无重复，i往后走，将其加入哈希表
若加入后，hash[s[i]] > 1说明 i位置出现了和前面重复的字符，由于前面是不重复的，所以只有可能是i位置的字符重复，接下来，j开始后移，同时进行hash[s[j++]]--来j将哈希表前面的字符清零，直到找到一个新的 j使的 hash[s[i]] > 1不成立，即当前 j 的位置为与 i重复字符的下一个字符，当前[j, i]为以 i为尾的最长子串。
画一个简图如下：
时间复杂度：每个点最多 ...
LeetCode刷题-2.两数相加
题目链接：2.两数相加
¶题解：
链表的简单操作！模拟数字相加。
¶题目简述：
两个倒序链表：例如：234的链表为 4 -> 3 -> 2，给定两个倒序链表，返回两个链表正序相加后的倒序链表！
¶题解：
由于给出的顺序是倒序，可以直接像普通加法从个位开始加起，进位即可。
初始化时可以设置一个虚节点：ListNode* l3 = new ListNode(-1);，返回时直接返回l3->next即可。
用 t表示进位，while退出后若仍有进位，则链表末尾补 1 ；
¶AC代码1：
1234567891011121314151617181920212223242526272829303132/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* a ...
LeetCode刷题-1.两数之和
题目链接：1.两数之和
¶题解：
¶1、暴力
由于答案的解唯一，可以使用两层循环，找到直接返回！
假如：最后为{i, j}， i < j，两层循环如下方代码。
时间复杂度：O(N^2)
¶AC代码：
1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i < nums.size(); i++) { for(int j = i + 1; j < nums.size(); j++) { if(nums[i] + nums[j] == target) return {i, j}; } } return {}; }};
¶2、使用哈希表
本题的目标就是找一个数，target - ...
