Back

/ 9 min read

从头学习LeetCode

开始

LeetCode 1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2：

输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3：

输入：nums = [3,3], target = 6 输出：[0,1] 提示：

2 <= nums.length <= 104
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

只会存在一个有效答案

思考过程

首先，每一个数组元素都需要和数组空间中的其他元素全部做一次加法后比较。这样的时间复杂度是O(n^2)。有思路，先写出代码进行一个验证。

#include <vector>
using namespace std;
class Solution {
  public:
        vector<int> twoSum(vector<int> &nums, int target) {
        unsigned short i = 0, j = 1;
        unsigned int size = nums.size();
        while (true) {
            if (nums[i] + nums[j] == target)
                return vector<int>{i, j};
            else [[likely]] {
                j++;
                if (j >= size) [[unlikely]] {
                    i++;
                    j = i + 1;
                }
            }
        }
    }
};

思路是，定义初始下标i,搜索i+1一直到nums.size()之间的元素，也就是nums[j]。通过i + nums[j]来判断是否和target相等，如果是，那么就返回{i, j}。这样可以不重不漏的搜索完整个结果树。 暴力解决

内存占用低，但是时间复杂度高。考虑降低时间复杂度，使用哈希表可以省略内部的循环，导致时间复杂度降低到O(n)，但是哈希表会导致内存占用增高，观察一下输入的特征。

特征:

  • 2 <= nums.length <= 10^4。数组最多有10000个元素。每个int占用4个字节，所以数组最多占用40KB的内存，所以映射到哈希表中，最多占用40KB的内存。

将数组映射到hash表，因为我们主要查找的是元素的值，所以key=nums[i]，value=i。这样就可以通过hash[nums[i]]来查找i的值。

假设我们在遍历到index下标的值为val，那么我们需要从hash表中搜索有没有target-val的键，如果有，此时需要返回的就是{index, hash[target-val]}。

class Solution {
  public:
    // 哈希表优化型
    vector<int> twoSum(vector<int> &nums, int target) {
        // 用hash表存储已经搜索过的元素
        unordered_map<int, int> hash;
        int index = 0, diff = 0;
        unordered_map<int, int>::iterator it;
        for (const auto &num : nums) {
            diff = target - num;
            it = hash.find(diff);
            if (it != hash.end()) {
                return {it->second, index};
            }
            hash[num] = index;
            index++;
        }
        return {};
    }
};

上面代码中做了一个小优化，首先不要将nums的所有元素映射到hash表中，而是一个一个进行过比较之后再映射到hash表中。这样最好的情况下只需要2次比较，最坏的情况下需要n-1次比较。这样的时间复杂度是O(n)。 最终优化

LeetCode 2. 两数相加

题目描述

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

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

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. 示例 2：

输入：l1 = [0], l2 = [0] 输出：[0] 示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零

思考过程

此题较为直接，只需要按照一般链表遍历的逻辑进行顺序相加即可。但需要注意注意：

  • 每次增加之后，需要判断是否需要进位
  • 跳出条件应为：1. 两个链表都遍历完毕 2. 有一个链表遍历完毕，另一个链表还有剩余 3. 两个链表都遍历完毕，但是还有进位
#include <cstdint>
#include <stdio.h>
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 *dummy = new ListNode(0);
        ListNode *current = dummy;
        int carry = 0;
        while (l1 || l2 || carry) {
            int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            carry = sum >= 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }
        return dummy->next;
    }
};

LeetCode 3. 无重复字符的最长子串

题目描述

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

示例 1:

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

输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:

输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示： 0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

思考过程

从左向右不断读入字符，每次读入字符后，需要判断当前字符是否在之前的子串中出现过。如果出现过，那么需要将左边界移动到重复字符的下一个位置。如果没有出现过，那么就继续向右移动右边界。

class Solution {
  public:
    int64_t isSubChar(char ch, const string &str, size_t left, size_t right) {
        for (; left <= right; left++) {
            if (str[left] == ch)
                return left;
        }
        return -1;
    }


    int lengthOfLongestSubstring(string s) {
        size_t maxLen = 1;
        size_t left = 0, right = 0;
        size_t len = s.length();
        if (len <= 1)
            return len;
        while (right < len - 1) {
            int64_t index = isSubChar(s[right + 1], s, left, right);
            if (index >= 0) {
                // 出现
                left = index + 1;
                right++;
            } else {
                right++;
            }
            maxLen = std::max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

LeetCode 4. 寻找两个正序数组的中位数

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


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






示例 1：


输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：


输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5








提示：


nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

思考过程