力扣重刷篇–1
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例
1
2
3
| 输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
|
解题思路
- 暴力法(O(n^2))：直接两轮for循环遍历数组，找到符合条件的两个数。
- 哈希表(O(n))：利用哈希表存储数组元素和索引的映射关系，通过一次遍历数组，判断target - nums[i] 是否在哈希表中，如果存在则返回对应的索引。
代码
暴力法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>hash;
for(int i=0;i<nums.size();i++){
if(hash.find(target-nums[i])!=hash.end()){
return {i,hash[target-nums[i]]};
}
hash[nums[i]]=i;
}
return {};
}
};
|
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
1
2
3
| 输入：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
|
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode*head=new ListNode();
ListNode*tail=head;
while(l1||l2){
if(l1==NULL){
ListNode*temp=new ListNode(l2->val);
l2=l2->next;
tail->next=temp;
tail=temp;
}
else if(l2==NULL){
ListNode*temp=new ListNode(l1->val);
l1=l1->next;
tail->next=temp;
tail=temp;
}else{
ListNode*temp=new ListNode(l1->val+l2->val);
l1=l1->next;
l2=l2->next;
tail->next=temp;
tail=temp;
}
}
int carry=0;
tail=head->next;
ListNode*temp=head;
for(;tail;tail=tail->next){
tail->val+=carry;
carry=tail->val/10;
tail->val%=10;
temp=temp->next;
}
if(carry){
ListNode*tempp=new ListNode(carry);
temp->next=tempp;
}
return head->next;
}
};
|
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例
1
2
3
| 输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
解题思路
- 使用滑动窗口的方法，维护一个窗口，窗口内的字符不重复。
- 使用一个哈希表来存储窗口内的字符和对应的索引。
- 遍历字符串，如果当前字符在窗口内已经存在，则将窗口左边界移动到该字符的下一个位置。
- 更新窗口右边界和最长子串长度。
代码
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
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int>hash;
int i=0,j=0;
int n=s.size();
int len=0;
while(j<n&&hash[s[j]]==0){
len++;
hash[s[j]]++;
j++;
}
int ans=len;
while(i<n&&j<n){
hash[s[i]]--;
i++;
len--;
while(j<n&&hash[s[j]]==0){
len++;
hash[s[j]]++;
j++;
}
ans=max(ans,len);
}
return ans;
}
};
|
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例
1
2
3
4
| 输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
|
解题思路
- 将两个数组合并成一个有序数组。
- 如果数组的长度为奇数，则中位数为数组的中间元素。
- 如果数组的长度为偶数，则中位数为数组的中间两个元素的平均值。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int nums1Size = nums1.size();
int nums2Size = nums2.size();
vector<int> nums(nums1Size + nums2Size);
merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), nums.begin());
int mid = nums.size() / 2;
if (nums.size() % 2 == 0) {
return 1.0*(nums[mid - 1] + nums[mid]) / 2.0;
}
return nums[mid];
}
}
|
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例
1
2
3
| 输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
|
解题思路
- 使用动态规划的方法，定义一个二维数组 dp，其中 dp[i][j] 表示 s[i:j+1] 是否为回文子串。
- 初始化 dp 数组，对于长度为 1 的子串，dp[i][i] 都为 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
29
30
| class Solution {
public:
string longestPalindrome(string s) {
int ans=1;
int start=0;
int n=s.size();
vector<vector<int>>dp(n,vector<int>(n,0));
for(int i=1;i<n;i++){
dp[i][i]=1;
dp[i-1][i]=s[i-1]==s[i];
if(dp[i-1][i]){
start=i-1;
ans=2;
}
}
dp[0][0]=1;
for(int j=2;j<n;j++){
for(int i=j-2;i>=0;i--){
if(s[i]==s[j]){
dp[i][j]=dp[i+1][j-1];
if(dp[i][j]&&j-i+1>ans){
ans=j-i+1;
start=i;
}
}
}
}
return s.substr(start,ans);
}
};
|
6. Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
示例
1
2
3
4
5
6
| 输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
解释：
- P A H N
- A P L S I I G
- Y I R
|
解题思路
- 使用一个二维数组来存储 Z 字形排列的字符。
- 遍历字符串，根据当前字符的行数和方向，将其放入二维数组中。
代码
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
| class Solution {
public:
string convert(string s, int numRows) {
if(numRows==1){
return s;
}
int n=s.size();
vector<vector<char>>dp(numRows,vector<char>(n,0));
int i=0,j=0;
int u=0;
while(u<n){
if(i==numRows){
i-=2;
for(;i>0&&u<n;i--,u++){
dp[i][j]=s[u];
}
j++;
}else{
for(;i<numRows&&u<n;i++,u++){
dp[i][j]=s[u];
}
j++;
}
}
string ans="";
for(int k=0;k<numRows;k++){
for(int l=0;l<j;l++){
if(dp[k][l]){
ans+=dp[k][l];
}
}
}
return ans;
}
};
|
7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例
解题思路
- 将整数转换为字符串。
- 反转字符串。
- 将反转后的字符串转换为整数。
代码
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
| class Solution {
public:
int reverse(int x) {
vector<int>nums;
if(x==-2147483648){
return 0;
}
int t=1;
if(x<0){
t=-1;
x=-x;
}
while(x>0){
nums.push_back(x%10);
x/=10;
}
int n=nums.size();
int arr[10]={2,1,4,7,4,8,3,6,4,7};
if(nums.size()==10){
int ans=0;
int a=1;
for(int i=0;i<10;i++){
if(nums[i]>arr[i]&&a){
return 0;
}
if(nums[i]<arr[i]){
a=0;
}
ans=ans*10+nums[i];
}
return ans*t;
}
int ans=0;
for(int i=0;i<nums.size();i++){
ans=ans*10+nums[i];
}
return ans*t;
}
};
|
8. 字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
- 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
- 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
- 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：本题中的空白字符只包括空格字符 ’ ’ 。 不考虑前导空格后剩下的字符串仅由数字和其它字符组成，请根据这个规则返回该字符串可以表示的整数。
示例
解题思路
- 去除字符串开头的空格。
- 判断字符串的第一个字符是否为正号或负号。
- 将字符串转换为整数。
代码
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
| class Solution {
public:
int myAtoi(string s) {
long long ans=0;
int st=1;
int i=0,n=s.size();
while(i<n&&s[i]==' '){
i++;
}
if(s[i]=='-'){
st=-1;
i++;
}
else if(s[i]=='+'){
i++;
}
while(i<n&&s[i]=='0'){
i++;
}
for(;i<n;i++){
if(s[i]<'0'||s[i]>'9'){
break;
}
ans=ans*10+s[i]-'0';
if(st*ans>2147483647){
return 2147483647;
}
if(st*ans<-2147483648){
return -2147483648;
}
}
return ans*st;
}
};
|
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例
解题思路
- 将整数转换为字符串。
- 判断字符串是否为回文。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool isPalindrome(int x) {
vector<int>nums;
if(x<0){
return 0;
}
while(x>0){
nums.push_back(x%10);
x/=10;
}
int i=0,j=nums.size()-1;
while(i<j){
if(nums[i]!=nums[j]){
return 0;
}
i++;
j--;
}
return 1;
}
};
|
10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例
1
2
3
| -- 输入：s = "aa", p = "a"
- - 输出：false
- - 解释："a" 无法匹配 "aa" 整个字符串。
|
解题思路
- 使用动态规划的方法来解决。
- 定义一个二维数组 dp，其中 dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。
- 初始化 dp 数组，dp[0][0] = true，表示空字符串和空模式匹配。
- 遍历 dp 数组，根据 p 的当前字符和前一个字符的不同情况，更新 dp 数组的值。
当 p[j-1] 是 ‘.’ 或 p[j-1]==s[i-1] 时，dp[i][j] = dp[i-1][j-1]
当 p[j-1] == “*” 时，dp[i][j] = dp[i][j-2] , 当 p[j-2]==s[i-1] 或 p[j-2] ==‘.’ 时， dp[i][j] 也可以等于 dp[i-1][j]
代码
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
| class Solution {
public:
bool isMatch(string s, string p) {
int n1=s.size(),n2=p.size();
vector<vector<int>>dp(n1+1,vector<int>(n2+1,0));
dp[0][0]=1;
for(int i=2;i<=n2;i++){
if(p[i-1]=='*'){
dp[0][i]=dp[0][i-2];
}
}
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++){
if(s[i-1]==p[j-1]||p[j-1]=='.'){
dp[i][j]=dp[i-1][j-1];
}
else if(p[j-1]=='*'){
dp[i][j]=dp[i][j-2];
if(s[i-1]==p[j-2]||p[j-2]=='.'){
dp[i][j]|=dp[i-1][j];
}
}
else{
dp[i][j]=0;
}
}
}
return dp[n1][n2];
}
};
|
