字数统计: 4.6k字   |   阅读时长: 21分

leetcode-hot-100

2. 两数相加 - 力扣（LeetCode）

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 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
/**
 * Definition for singly-linked list.
 * 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* head1 = l1;
        ListNode* head2 = l2;
        ListNode* result = new ListNode(0);
        ListNode* head = result;
        bool carry = false;
        while(head1 != nullptr || head2 != nullptr) {
            int sum = 0;
            if(head1 != nullptr) {
                sum = sum + head1->val;
                head1 = head1->next;
            }
            if(head2 != nullptr) {
                sum = sum + head2->val;
                head2 = head2->next;
            }
            if(carry) {
                sum = sum + 1;
            }
            head->next = new ListNode(sum % 10);
            head = head->next;
            carry = sum >= 10 ? true : false;
        }
        if(carry) {
            head->next = new ListNode(1);
        }
        return result->next;
    }
};

3. 无重复字符的最长子串 - 力扣（LeetCode）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

双指针的思想，利用set容器的count判断重复元素。

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:
    int lengthOfLongestSubstring(string s) {
        //双指针法
        unordered_set <char> set;
        int slow = 0;
        int fast = 0;
        int result = 0;
        for(int slow = 0; slow  < s.size(); slow ++) {
            if(slow == 0) {
                while(fast < s.size() && !set.count(s[fast])) {	//!set.count(s[fast])说明之前出现过这个字符了，计数不为0
                    set.insert(s[fast]);
                    fast++;
                }
                result = fast - slow;
            }
            else {
                set.erase(s[slow - 1]);
                while(fast < s.size() && !set.count(s[fast])) {
                    set.insert(s[fast]);
                    fast++;
                }
                result = max(result, fast - slow);
            }
        }
        return result;
    }
};

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

1
2
3
输入：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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector <int> result(nums1.size() + nums2.size(), 0);
        int i, j, k = 0;
            while(i < nums1.size() || j < nums2.size()) {
                if(i < nums1.size() && j < nums2.size()) {
                    if(nums1[i] < nums2[j]) {
                        result[k] = nums1[i];
                        i++;
                        k++;
                    }
                    else {
                        result[k] = nums2[j];
                        j++;
                        k++;
                    }
                }
                else if(i < nums1.size()) {
                    result[k] = nums1[i];
                    k++;
                    i++;
                }
                else if(j < nums2.size()) {
                    result[k] = nums2[j];
                    k++;
                    j++;
                }
            } 
        if(result.size() % 2 == 0) {
            return (result[result.size() / 2] + result[k / 2 - 1]) / 2.0;
        }
        else {
            return result[result.size() / 2];
        }
    }
};

5. 最长回文子串 - 力扣（LeetCode）

给你一个字符串 s，找到 s 中最长的回文子串。

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

方法一：双指针法，从中间向两边扩充，直到找到最长的回文串。最长回文串包括奇数个和偶数个两种情况，找到这两种情况中最长的记录下字符的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int left = 0;
    int right = 0;
    int maxLength = 0;
    void extand(const string& s, int i, int j, int n) {
        while(i >= 0 && j < n && s[i] == s[j]) {
            if(j - i >= maxLength) {
                left = i;
                right = j;
                maxLength = j - i + 1;
            }
            i--;
            j++;
        }
    }
    string longestPalindrome(string s) {
        for(int i = 0; i < s.size(); i++) {
            extand(s, i, i, s.size());
            extand(s, i, i + 1, s.size());
        }
        return s.substr(left, maxLength);
    }
};

方法二：动态规划

1.确定dp数组（dp table）以及下标的含义

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2.确定递推公式

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

  • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
  • 情况二：下标i 与 j相差为1，例如aa，也是文子串
  • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

3.dp[i][j]初始化为false。

4.情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。dp[i + 1][j - 1] 在 dp[i][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
class Solution {
public:
    string longestPalindrome(string s) {
        int left = 0;
        int right = 0;
        int maxLength = 0;
        vector <vector <int>> dp(s.size(), vector <int> (s.size(), 0));
        for(int i = s.size() - 1; i >= 0; i--) {
            for(int j = i; j < s.size(); j++) {
                if(s[i] == s[j]) {
                    if(j - i <= 1) {
                        dp[i][j] = true;
                    }
                    else if(dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                }
                if(dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    left = i;
                    right = j;
                }
            }
        }
        return s.substr(left, right - left + 1);
    }
};

6. Z 字形变换 - 力扣（LeetCode）

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

本质上是找规律，找到图形的周期，用一个二维数组进行存储，计算出二维数组的长和宽，然后香气中放入元素，最后通过顺序输出

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
class Solution {
public:
    //周期为2 * numRows - 2, 因此 Z 字形变换的周期 t=r+r-2=2r-2t=r+r−2=2r−2，每个周期会占用矩阵上的 1+r-2=r-11+r−2=r−1 列。
    string convert(string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r * 2 - 2;  //周期
        int c = (n + t - 1) / t * (r - 1);  //n / t向上取整(代表有几个周期), 乘每个周期的列数 r - 1， 这里周期取大点也没关系，因为赋给的初值都是0
        vector<string> mat(r, string(c, 0));
        for (int i = 0, x = 0, y = 0; i < n; ++i) {
            mat[x][y] = s[i];
            if (i % t < r - 1) {
                ++x; // 向下移动
            } else {
                --x;
                ++y; // 向右上移动
            }
        }
        string ans;
        for (auto &row : mat) {
            for (char ch : row) {
                if (ch) {   //如果ch不为0
                    ans += ch;
                }
            }
        }
        return ans;
    }
};

7. 整数反转 - 力扣（LeetCode）

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

1
2
输入：x = 123
输出：321

1.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int reverse(int x) {
        long int result = 0;
        int last = 0;
        while(x!=0) {
            //每次取末尾数字
            int tmp = x%10;
            result = result*10 + tmp;
            if(result > pow(2, 31) - 1 || result < - pow(2, 31)) {
                return 0;
            }
            x /= 10;
        }
        return result;
    }
};

8. 字符串转换整数 (atoi) - 力扣（LeetCode）

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

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:
    int myAtoi(string s) {
        long long int result = 0;
        int tmp = 0;
        bool neg = false;
        int count = 0;
        int start;
        for(int i = 0; i < s.size(); i++) {		//跳过空格
            if(s[i] == ' ') {
                continue;
            }
            else {
                start = i;
                break;
            }
        }
        if(s[start] == '-') {		//判断符号
            neg = true;
            start = start + 1;
        }
        else if(s[start] == '+') {
            neg = false;
            start = start + 1;
        }
        else {
            neg = false;
        }
        for(int i = start; i < s.size(); i++) {
            if(s[start] > '9' || s[start] < '0') {	//第一个字符不是数字，直接返回
                result = 0;
                break;
            }
            if(s[i] >= '0' && s[i] <= '9') {	//是数字，就进行转换
                tmp = s[i] - '0';
                if(neg == true) {
                    tmp = -tmp;
                }
                result = result * 10 + tmp;
                if(result > pow(2, 31) - 1) {	//判断溢出
                    result = pow(2, 31) - 1;
                }
                if(result < -pow(2, 31)) {
                    result = -pow(2, 31);
                }
            }
            else break;
        }
        return result;
    }
};

10. 正则表达式匹配 - 力扣（LeetCode）

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

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:
    bool isMatch(string s, string p) {
        s=" "+s;//防止该案例：""\n"c*"
        p=" "+p;
        int m=s.size(),n=p.size();
        bool dp[m+1][n+1];
        memset(dp,false,(m+1)*(n+1));
        dp[0][0]=true;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s[i-1]==p[j-1] || p[j-1]=='.'){  //如果相等或者j - 1为. 
                    dp[i][j]=dp[i-1][j-1];
                }
                else if(p[j-1]=='*'){
                    if(s[i-1]!=p[j-2] && p[j-2]!='.')
                        dp[i][j]=dp[i][j-2];
                    else{
                        dp[i][j]=dp[i-1][j-2] || dp[i][j-2] || dp[i-1][j];	//对应匹配一次，匹配零次，匹配多次，只有确定了匹配次数是0还是1，才将*和其前面的字符去掉继续递归。

                    }
                }
            }
        }
        return dp[m][n];
    }
};

11. 盛最多水的容器 - 力扣（LeetCode）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

img

双指针的思想：

  • 若向内 移动短板 ，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
  • 若向内 移动长板 ，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int>& height) {
        int slow = 0;
        int fast = height.size() - 1;
        int result = 0;
        while(slow < fast) {
            result = max(result, (fast - slow) * min(height[fast], height[slow]));
            if(height[slow] < height[fast]) {
                slow++;
            }
            else {
                fast--;
            }
        }
        return result;
    }
};

21. 合并两个有序链表 - 力扣（LeetCode）

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

两个指针依次遍历两个链表，取出小的一个放在结果中

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
/**
 * Definition for singly-linked list.
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummyNode = new ListNode(0);
        ListNode* cur = dummyNode;
        while(list1 != NULL || list2 != NULL) {
            if(list1 == NULL) {
                cur->next = list2;
                cur = cur->next;
                list2 = list2->next;
            }
            else if(list2 == NULL) {
                cur->next = list1;
                cur = cur->next;
                list1 = list1->next;
            }
            else if(list1->val < list2->val) {
                cur->next = new ListNode(list1->val);
                cur = cur->next;
                list1 = list1->next;
            }
            else {
                cur->next = new ListNode(list2->val);
                cur = cur->next;
                list2 = list2->next;
            }
        }
        return dummyNode->next;
    }
};

23. 合并K个升序链表 - 力扣（LeetCode）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

这个题是上一个题的升级版，合并多个升序链表，就是在合并两个的基础上完成的。注意为了降低复杂度，用到了归并排序

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
/**
 * Definition for singly-linked list.
 * 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* merge(ListNode* list1, ListNode* list2) {
        ListNode* dummyNode = new ListNode(0);
        ListNode* cur = dummyNode;
        while(list1 != NULL || list2 != NULL) {
            if(list1 == NULL) {
                cur->next = list2;
                cur = cur->next;
                list2 = list2->next;
            }
            else if(list2 == NULL) {
                cur->next = list1;
                cur = cur->next;
                list1 = list1->next;
            }
            else if(list1->val < list2->val) {
                cur->next = new ListNode(list1->val);
                cur = cur->next;
                list1 = list1->next;
            }
            else {
                cur->next = new ListNode(list2->val);
                cur = cur->next;
                list2 = list2->next;
            }
        }
        return dummyNode->next;
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {

        if (lists.empty()) return NULL;
        for (int step = 1; step < lists.size(); step += step)  // 每次合并的两个链表的索引差值
            for (int i = 0; i + step < lists.size(); i += step + step)  // i 代表两个待合并链表中的第一个，复杂度从k降为了logk(k是链表个数)
                lists[i] = merge(lists[i], lists[i + step]);
        return lists[0];
    }
};

31. 下一个排列 - 力扣（LeetCode）

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

模拟的思想：

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for(int i = nums.size() - 1; i >= 0; i--) {
            for(int j = nums.size() - 1; j > i; j--) {
                if(nums[j] > nums[i]) {
                    swap(nums[j], nums[i]);
                    reverse(nums.begin() + i + 1, nums.end());
                    return;
                }
            }
        }
        //到了这里整个数组都是倒序了
        reverse(nums.begin(), nums.end());
    }
};

32. 最长有效括号 - 力扣（LeetCode）

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

动态规划思路详解（c++）——32.最长有效括号 - 最长有效括号 - 力扣（LeetCode）

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:
    int longestValidParentheses(string s) {
        int size = s.length();
        vector<int> dp(size, 0);        //dp[i]表示i之前的最长串的长度

        int maxVal = 0;
        for(int i = 1; i < size; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = 2;      //直接一对匹配
                    if (i - 2 >= 0) {
                        dp[i] = dp[i] + dp[i - 2];
                    }
                } else if (dp[i - 1] > 0) {     //这时候s[i - 1] 是)
                    if ((i - dp[i - 1] - 1) >= 0 && s[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if ((i - dp[i - 1] - 2) >= 0) {
                            dp[i] = dp[i] + dp[i - dp[i - 1] - 2];      //()(())
                        }
                    }
                }
            }
            maxVal = max(maxVal, dp[i]);
        }
        return maxVal;
    }
};

33. 搜索旋转排序数组 - 力扣（LeetCode）

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

核心思路就是排序数组经过一个反转之后有半边一定是有序的,因此可以用二分查找。

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {     //肯定有半边是递增的，如果满足if，左半边递增
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {    //右半边递增
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊