leetcode hot 100
####1.
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出
和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例：
输入：
nums = [2,7,11,15], target = 9
输出：
[0,1]
解释：因为nums[0] + nuts[1] == 9
思路：
方法一：暴力
方法二：用哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>mp;
vector<int>res(2,-1);
for(int i=0;i<nums.size();i++){
if(mp.count(target-nums[i])>0){
res[0]=mp[target-nums[i]];
res[1]=i;
break;
}
mp[nums[i]]=i;
}
return res;
}
};
|
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序
的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
思路：
模拟即可，需要注意进位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* res = new ListNode();
int carry = 0;
ListNode* cur = res;
while(l1 != nullptr || l2 != nullptr){
int x = l1 != nullptr ? l1->val : 0;
int y = l2 != nullptr ? l2->val : 0;
int sum = x + y + carry;
carry = sum/10;
sum = sum % 10;
cur->next = new ListNode(sum);
cur = cur->next;
if(l1!=nullptr){
l1 = l1->next;
}
if(l2!=nullptr){
l2 = l2->next;
}
}
if(carry){
cur->next = new ListNode(carry);
}
return res->next;
}
};
|
给定一个字符串 s ，请你找出其中不含有重复字符的
最长子串 的长度。
示例：
输入：s="abcabcbb"
输出：3
输入：s = "bbbbb"
输出：1
输入：s = "pwwkew"
输出：3
思路：
标签：滑动窗口
暴力解法时间复杂度较高，会达到O(n^2)，故而采取滑动窗口的方法降低时间复杂度
定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value
值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复
我们定义不重复子串的开始位置为 start，结束位置为 end
随着 end 不断遍历向后，会遇到与 [start, end]
区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新
start，此时 [start, end] 区间内不存在重复字符
无论是否更新 start，都会更新其 map 数据结构和结果 ans = end - start +
1。
时间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size(),ans=0;
map<char,int> mp;
for(int start=0,end=0;end<n;end++){
char tmp = s[end];
if(mp.count(tmp)>0){
start = max(mp[tmp],start);
}
ans = max(ans,end-start+1);
mp[tmp] = end+1;
}
return ans;
}
};
|
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列
，请你从数组中找出满足相加之和等于目标数 target
的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1
<= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标
index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以
重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7
之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
思路：
采用双指针，l=0,r=numners.size()-1,sum = numbers[l]+numbers[r]
我们可以得出如果sum > target,那么我们可以排除这一列，因为往后和越大，我们只需要r--
如果sum<target，我们可以排除这一行，l++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l=0,r=numbers.size()-1;
while(l<r){
int sum = numbers[l]+numbers[r];
if(sum < target) l++;
else if(sum > target) r--;
else return {l+1,r+1};
}
return {-1,-1};
}
};
|
####20.
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s
，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例：
输入：s = "()" 输出：true
思路：
方法一：使用哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (char ch: s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
|
方法二：不使用哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
bool isValid(string s) {
if(s.size() == 0) return true;
if(s.size()&1) return false;
stack<char> st;
for(char c:s){
if(c == '(' || c=='[' || c=='{') st.push(c);
if(c == ')'){
if(!st.empty() && st.top()=='(') st.pop();
else return false;
}
if(c==']'){
if(!st.empty() && st.top()=='[') st.pop();
else return false;
}
if(c=='}'){
if(!st.empty() && st.top()=='{') st.pop();
else return false;
}
}
if(st.empty()) return true;
return false;
}
};
|
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转
90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要
使用另一个矩阵来旋转图像。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
思路：
顺时针旋转90度
算法流程：
1，先对角线反转
2，再中间对称反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void rotate(vector<vector<int> >& matrix) {
int n = matrix.size();
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i = 0; i < n; i++){
reverse(matrix[i]);
}
}
void reverse(vector<int>& row){
int i = 0, j = row.size() - 1;
while(j > i){
swap(row[i++],row[j--]);
}
}
};
|
给你一个 m 行 n 列的矩阵
matrix ，请按照 顺时针螺旋顺序
，返回矩阵中的所有元素。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public:
vector<int> spiralOrder(vector<vector<int> >& matrix) {
vector<int> res;
int m = matrix.size(),n = matrix[0].size();
if(m == 0 || n == 0) return {};
int upper_bound = 0;
int lower_bound = m - 1;
int left_bound = 0;
int right_bound = n - 1;
while(res.size() <= m*n ){
for(int i = left_bound; i <= right_bound; i++){
res.push_back(matrix[upper_bound][i]);
}
upper_bound++;
if(upper_bound > lower_bound) break;
for(int j = upper_bound; j <= lower_bound; j++){
res.push_back(matrix[j][right_bound]);
}
right_bound--;
if(right_bound < left_bound) break;
for(int i = right_bound; i >= left_bound; i--){
res.push_back(matrix[lower_bound][i]);
}
lower_bound--;
if(lower_bound < upper_bound) break;
for(int j = lower_bound; j >= upper_bound; j--){
res.push_back(matrix[j][left_bound]);
}
left_bound++;
if(left_bound > right_bound) break;
}
return res;
}
};
|
给你一个正整数 n ，生成一个包含 1 到
n2 所有元素，且元素按顺时针顺序螺旋排列的
n x n 正方形矩阵 matrix 。
示例:
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public:
vector<vector<int> > generateMatrix(int n) {
vector<vector<int> > res(n,vector<int>(n));
int upper_bound = 0;
int lower_bound = n - 1;
int left_bound = 0;
int right_bound = n - 1;
int num = 1;
while(num <= n * n ){
for(int i = left_bound; i <= right_bound; i++){
res[upper_bound][i] = num++;
}
upper_bound++;
if(upper_bound > lower_bound) break;
for(int j = upper_bound; j <= lower_bound; j++){
res[j][right_bound] = num++;
}
right_bound--;
if(right_bound < left_bound) break;
for(int i = right_bound; i >= left_bound; i--){
res[lower_bound][i] = num++;
}
lower_bound--;
if(lower_bound < upper_bound) break;
for(int j = lower_bound; j >= upper_bound; j--){
res[j][left_bound] = num++;
}
left_bound++;
if(left_bound > right_bound) break;
}
return res;
}
};
|