1. 两数之和
思路：
暴力遍历
代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int lenNums = nums.size();
int a, b;
for(int i = 0; i < lenNums; i ++){
for(int j = i + 1; j < lenNums; j ++){
if(nums[i] + nums[j] == target){
vector<int> res;
res.push_back(i);
res.push_back(j);
return res;
}
}
}
vector<int> res;
return res;
}
};
2. 两数相加
思路:
遍历链表
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode * res = new ListNode();
ListNode * h = res;
int c = 0;
while(l1 || l2){
int x = 0;
if(l1) x += l1->val;
if(l2) x += l2->val;
x += c;
//cout << " x= " << x << endl;
h->next = new ListNode(x % 10);
c = x / 10;
h = h->next;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
}
if(c){
h->next = new ListNode(1);
}
return res->next;
}
};
3. 无重复字符的最长子串
思路：
暴力：
枚举每一个字符，当做当前子串的头，依次遍历下去，直到不合格。
那么显然是要超时的，在暴力的基础做一个小优化即可：
当我们枚举s[i]为头部的时候，遍历到s[j]发现，s[j]在[i, j]之间出现过，我们用一个map来记录字符最新的位置，那么显然在 [m[s[j]] + 1, j]这之中是没有重复字符出现的，利用这个技巧可以在线性时间内解决。
代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, cur = 0, idx = 0;
int lenS = s.size();
map<char, int> mp;
for(int i = 0; i < lenS; i ++){
if(mp[s[i]] && mp[s[i]] > idx){
res = max(res, cur);
cur = i - mp[s[i]] + 1;
idx = mp[s[i]];
mp[s[i]] = i + 1;
} else{
mp[s[i]] = i + 1;
cur ++;
}
}
return max(res, cur);
}
};
4. 寻找两个正序数组的中位数
思路：
二分。
分奇偶来讨论，每次寻找两个数组中第（k / 2 - 1） 个元素，很明显小的那个不符合要求，所以他前面的包括他都可以删去，用指针来实现。特判特殊情况即可。
代码：
class Solution {
public:
int find(vector<int> a, vector<int> b, int k){
int la = a.size();
int lb = b.size();
int idxA = 0, idxB = 0;
while(1){
if(idxA == la) return b[idxB + k - 1];
if(idxB == lb) return a[idxA + k - 1];
if(k == 1) return min(a[idxA], b[idxB]);
int newIdxA = min(idxA + k / 2 - 1, la - 1);
int newIdxB = min(idxB + k / 2 - 1, lb - 1);
if(a[newIdxA] <= b[newIdxB]){
k -= newIdxA - idxA + 1;
idxA = newIdxA + 1;
} else{
k -= newIdxB - idxB + 1;
idxB = newIdxB + 1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int all = nums1.size() + nums2.size();
double res;
if(all & 1) res = find(nums1, nums2, all / 2 + 1);
else res = (find(nums1, nums2, all / 2) + find(nums1, nums2, all / 2 + 1)) / 2.0;
return res;
}
};
5. 最长回文子串
思路：
用Manacher算法求出最长回文串的长度和其中心的下标即可。
代码：
class Solution {
public:
pair<int, int> Manacher(char * s, int len){
int p[2010];
int maxLen = 0, maxId;
int mx = 0, id = 1;
for(int i = 1; i <= len; i ++){
if(mx > i) p[i] = min(p[2 * id - i], mx - i);
else p[i] = 1;
while(i + p[i] <= len && s[i + p[i]] == s[i - p[i]]) p[i] ++;
if(p[i] >= mx) { mx = p[i]; id = i; }
if(maxLen < p[i] - 1){
maxLen = p[i] - 1;
maxId = i;
}
}
return {maxLen, maxId};
}
string longestPalindrome(string s) {
char str[2010];
int lenStr = 0;
for(int i = 0; i < s.size(); i ++){
str[ ++ lenStr] = '~';
str[ ++ lenStr] = s[i];
}
str[ ++ lenStr] = '~';
pair<int, int> ans = Manacher(str, lenStr);
int a = ans.first;
int b = ans.second;
cout << a << " " << b << endl;
string res = "";
for(int i = b - a + 1; i < b + a; i ++){
if(str[i] == '~') continue;
res += str[i];
}
return res;
}
};
6. Z 字形变换
思路：
找规律。
设 m = 2 * numRows - 2;
那么遍历去 % m 很容易发现规律
代码：
class Solution {
public:
string convert(string s, int numRows) {
if(numRows == 1) return s;
int len = s.size();
vector<string> tmp(numRows);
string res = "";
int m = 2 * numRows - 2;
for(int i = 0; i < len; i ++){
int t = i % m;
if(t < numRows) tmp[t].push_back(s[i]);
else tmp[m - t].push_back(s[i]);
}
for(int i = 0; i < tmp.size(); i ++)
res += tmp[i];
return res;
}
};
7. 整数反转
思路：
注意溢出
代码：
class Solution {
public:
int reverse(int x) {
long long res = 0;
long long mx = (1ll << 31) - 1;
long long mn = - (1ll << 31);
int mark = 0;
if(x < 0){
mark = 1;
if(x == mn) x = 0;
else x *= -1;
}
while(x){
res = res * 10 + x % 10;
x /= 10;
}
if(mark) res *= -1;
if(res > mx || res < mn) res = 0;
return int(res);
}
};
8. 字符串转换整数 (atoi)
思路：
模拟即可
代码：
class Solution {
public:
int myAtoi(string str) {
int lenStr = str.size();
string s = "";
int symbol = 0; // 记录符号
int flag = 0;
for(int i = 0; i < lenStr; i ++){
if(!flag && str[i] == ' ') continue;
else{
if(str[i] >= '0' && str[i] <= '9')
s += str[i];
else if(!flag && str[i] == '-')
symbol = -1;
else if(!flag && str[i] == '+')
symbol = 1;
else break;
flag = 1;
}
}
if(s.empty()) return 0;
long long num = 0;
for(int i = 0; i < s.size(); i ++) {
num = num * 10 + (s[i] - '0');
if(num > INT_MAX) break;
}
if(symbol == -1) num *= -1;
if(num > INT_MAX) num = INT_MAX;
if(num < INT_MIN) num = INT_MIN;
return int(num);
return 0;
}
};
9. 回文数
思路：
暴力
代码：
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
long long y = 0;
int tmp = x;
while(x){
y = y * 10 + x % 10;
x /= 10;
}
return y == tmp;
}
};
10. 正则表达式匹配
思路：
二维DP
设f[i][j]: s中前i个字符与p中前j个字符是否合法匹配
1. p[j] = '*':
f[i][j] |= f[i][j - 2] // 将j-1删去
if(p[j - 1] == s[i]) f[i][j] |= f[i - 1][j]
2. p[j] != '*':
if(p[j] == '.' || p[j] == s[i]) f[i][j] |= f[i - 1][j - 1]
return f[size(s)][size(p)]
代码：
class Solution {
public:
bool isMatch(string s, string p) {
int ls = s.size();
int lp = p.size();
auto check = [&](int i, int j){
if(i == 0) return false;
if(p[j - 1] == '.' || p[j - 1] == s[i - 1]) return true;
return false;
};
int f[ls + 10][lp + 10];
memset(f, 0, sizeof f);
f[0][0] = true;
for(int i = 0; i <= ls; i ++)
for(int j = 1; j <= lp; j ++){
if(p[j - 1] == '*'){
if(j >= 2) f[i][j] |= f[i][j - 2];
if(check(i, j - 1)) f[i][j] |= f[i - 1][j];
} else{
if(check(i, j)) f[i][j] |= f[i - 1][j - 1];
}
}
return f[ls][lp];
}
};
11. 盛最多水的容器
思路：
双指针
很显然的一个事实是：高度取决于短的板子
我们可以逐渐缩小宽度来获得更高的高度
// 当h[i] < h[j]时，i++, 那么高度是有可能变大的，如果是j--，那么高度只可能更小，并且由于宽度还变小了，那么j--一定不会是最优解。
if h[i] < h[j]：
i ++;
else j --;
代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int res = 0;
int i = 0, j = n - 1;
while(i < j){
int v = (j - i) * min(height[i], height[j]);
res = max(res, v);
if(height[i] < height[j]) i ++;
else j --;
}
return res;
}
};
12. 整数转罗马数字
思路：
把罗马字符可以代表的字符都手动预处理下来，共计13项，然后从大到小遍历即可。
代码：
string rome[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int val[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
class Solution {
public:
string intToRoman(int num) {
string res = "";
for(int i = 0; i < 13; i ++){
while(num >= val[i]){
res += rome[i];
num -= val[i];
}
}
return res;
}
};
13. 罗马数字转整数
思路：
用hash映射出罗马字母对应的数，然后从左往右遍历一遍，如果当前值小于左边就减，反之就加。（注意处理边界）
代码：
class Solution {
public:
int romanToInt(string s) {
map<char, int> mp;
mp['I'] = 1;
mp['V'] = 5;
mp['X'] = 10;
mp['L'] = 50;
mp['C'] = 100;
mp['D'] = 500;
mp['M'] = 1000;
int n = s.length();
int res = 0;
for(int i = 0; i < n - 1; i ++){
if(mp[s[i]] >= mp[s[i + 1]])
res += mp[s[i]];
else res -= mp[s[i]];
}
res += mp[s[n - 1]];
return res;
}
};
14. 最长公共前缀
思路：
暴力
代码：
class Solution {
public:
int min(int a, int b){
return a <= b ? a : b;
}
string longestCommonPrefix(vector<string>& strs) {
string res = "";
int n = strs.size();
if(n == 0) return "";
int mn = 1e9;
for(int i = 0; i < n; i ++) mn = min(mn, strs[i].size());
for(int i = 0; i < mn; i ++){
char c = strs[0][i];
int mark = 1;
for(int j = 1; j < n; j ++)
if(strs[j][i] != c){
mark = 0;
break;
}
if(mark) res += c;
else break;
}
return res;
}
};
51. N 皇后
思路：
dfs枚举
代码：
class Solution {
public:
bool check(int i, int pos[]){
for(int j = 1; j < i; j ++)
if(pos[i] == pos[j] || abs(i - j) == abs(pos[i] - pos[j])) return false;
return true;
}
vector<string> record(int pos[], int n){
vector<string> res;
for(int i = 1; i <= n; i ++){
string tmp = "";
for(int j = 1; j <= n; j ++)
if(pos[i] == j) tmp += 'Q';
else tmp += '.';
res.push_back(tmp);
}
return res;
}
void queen(int i, int *pos, int n, vector<vector<string>> & res){
if(i > n) res.push_back(record(pos, n));
else{
for(int j = i; j <= n; j ++){
swap(pos[i], pos[j]);
if(check(i, pos)) queen(i + 1, pos, n, res);
swap(pos[i], pos[j]);
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
int pos[n + 1];
for(int i = 1; i <= n; i ++) pos[i] = i;
queen(1, pos, n res);
return res;
}
};
216. 组合总和 III
思路：
dfs 暴力枚举
代码：
class Solution {
public:
vector<vector<int>> res;
int a, b;
void dfs (int sum, int num, int cnt, vector<int> vec){
if(cnt == a && sum == b){
res.push_back(vec);
return;
}
if(num > 9 || sum > b || cnt > a) return;
for(int i = num; i <= 9; i ++){
vec.push_back(i);
dfs(sum + i, i + 1, cnt + 1, vec);
vec.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
a = k, b = n;
vector<int> vec;
dfs(0, 1, 0, vec);
return res;
}
};