Leetcode 1-50

• 1. 两数之和
• 2. 两数相加
• 3. 无重复字符的最长子串
• 4. 寻找两个正序数组的中位数
• 6. N 字形变换
• 9. 回文数
• 13. 罗马数字转整数
• 23. 合并 K 个升序链表
• 24. 两两交换链表中的节点
• 27. 移除元素
• 32. 最长有效括号
• 34. 在排序数组中查找元素的第一个和最后一个位置
• 41. 缺失的第一个正数
• 46. 全排列
• 49. 字母异位词分组

1. 两数之和

哈希表，暴力可能无法通过，使用哈希表保存值到位置的映射，这样每次只需要测试 target - nums[i] 就能判断是否有符合条件的数字。

暴力法解决时间复杂度为 $\mathcal{O}(n^2)$，哈希表解法时间复杂度为 $\mathcal{O}(n)$。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            if (m.find(target - nums[i]) != m.end()) {
                return {m[target - nums[i]], i};
            }
            m[nums[i]] = i;
        }
        return {};
    }
};

2. 两数相加

链表，遍历时构建数组。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* root = new ListNode(0);
        ListNode* curr = root;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int v1 = l1 != nullptr ? l1->val : 0;
            int v2 = l2 != nullptr ? l2->val : 0;
            int sum = v1 + v2 + carry;
            carry = sum / 10;
            ListNode* newNode = new ListNode(sum % 10);
            curr->next = newNode;
            curr = newNode;

            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        return root->next;
    }
};

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> char_map;
        int res = 0;
        int left = 0, right = 0;
        while (left <= right) {
            if (right < s.size() && char_map.find(s[right]) == char_map.end()) {
                char_map[s[right]] = 1;
                right++;
                res = max(res, right - left);
            } else {
                int old_times = char_map[s[left]];
                if (old_times == 1) {
                    char_map.erase(s[left]);
                } else {
                    char_map[s[left]] = old_times - 1;
                }
                left++;
            }
        }
        return res;
    }
};

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

6. N 字形变换

模拟，只使用模拟的空间复杂为 $\mathcal{O}(n)$。

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> rows(min(numRows, int(s.size())));
        int curRow = 0;
        bool goingDown = false;
        for (char c : s) {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }
        string ret;
        for (string row : rows) ret += row;
        return ret;
    }
};

我们设列数为 $r$，我们注意到循环周期 $T = 2r - 2$，我们只需要每次计算下一次取字符的位置即可按顺序拼接。时间复杂度为 $\mathcal{O}(1)$（不含答案）。

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string res;
        int n = s.length();
        int step = 2 * numRows - 2;
        for (int i = 0; i < numRows; ++i) {
            for (int j = i; j < n; j += step) {
                res += s[j];
                if (i != 0 && i != numRows - 1) {
                    int tmp = j + step - 2 * i;
                    if (tmp < n) res += s[tmp];
                }
            }
        }
        return res;
    }
};

9. 回文数

计算题，最容易使用的方法可能是字符串比较了。

class Solution {
public:
    bool isPalindrome(int x) {
        string str = to_string(x);
        string rev = str;
        reverse(rev.begin(), rev.end());
        return str == rev;
    }
};

还有一种巧妙的数学方法，这种方法的时间复杂度为 $\mathcal{O}(\log n)$：

#define ll long long

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        ll z = x;
        ll y = 0;
        while (z > 0) {
            y = y * 10 + z % 10;
            z /= 10;
        }
        return (ll)x == y;
    }
};

13. 罗马数字转整数

模拟。可以观察到，特殊情况下仅仅在当前位置的值小于下一个位置的时候。而且特殊情况下即减去当前位置表示的值即可。

class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); ++i) {
            char ch = s[i];
            char next_ch = i + 1 < s.size() ? s[i + 1] : ' ';
            if (ch == 'I') {
                if (next_ch == 'V' || next_ch == 'X')
                    res -= 1;
                else
                    res += 1;
            } else if (ch == 'V') {
                res += 5;
            } else if (ch == 'X') {
                if (next_ch == 'L' || next_ch == 'C')
                    res -= 10;
                else
                    res += 10;
            } else if (ch == 'L') {
                res += 50;
            } else if (ch == 'C') {
                if (next_ch == 'D' || next_ch == 'M')
                    res -= 100;
                else
                    res += 100;
            } else if (ch == 'D') {
                res += 500;
            } else if (ch == 'M') {
                res += 1000;
            }
        }
        return res;
    }
};

23. 合并 K 个升序链表

优先级队列，每次将下一个可能的元素放到队列中即可。如果使用多路归并，效率略低于优先级队列。

设链表的所有元素的个数为 $n$，链表的个数为 $k$，使用优先级队列的时间复杂度为 $\mathcal{O}(n\log k)$。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* head = new ListNode(0);
        ListNode* tail = head;
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pqueue(cmp);
        for (auto beg = lists.cbegin(); beg != lists.cend(); ++beg) {
            if (*beg != NULL) pqueue.push(*beg);
        }
        while (!pqueue.empty()) {
            ListNode* node = pqueue.top();
            pqueue.pop();
            tail->next = node;
            tail = tail->next;
            if (node->next != NULL) pqueue.push(node->next);
        }
        return head->next;
    }
};

24. 两两交换链表中的节点

TODO 较复杂，整理思路。

递归法：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* prev = head;
        ListNode* curr = head->next;
        ListNode* next = curr->next;
        curr->next = prev;
        prev->next = swapPairs(next);
        return curr;
    }
};

遍历法：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* new_head = head->next;
        ListNode* pre = head;
        ListNode* cur = head->next;
        ListNode* next = cur->next;
        while (cur != NULL) {
            cur->next = pre;
            if (next == NULL || next->next == NULL) {
                pre->next = next;
                break;
            }
            pre->next = next->next;
            pre = next;
            cur = next->next;
            next = cur->next;
        }
        return new_head;
    }
};

27. 移除元素

数组，经典原地移除算法。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.size(); ++j) {
            if (nums[j] != val) nums[i++] = nums[j];
        }
        return i;
    }
};

32. 最长有效括号

本题基于括号匹配的原则，可以得到一个简单的思路，基于中心扩展的思路和基于动态规划的思路。

用栈来预先计算每个合法的括号位置，然后循环找到最长连续的位置。

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<bool> closed(s.size(), false);
        vector<int> stack;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                stack.push_back(i);
            } else {
                if (stack.empty()) {
                    closed[i] = false;
                } else {
                    closed[i] = true;
                    closed[stack.back()] = true;
                    stack.pop_back();
                }
            }
        }
        int res = 0;
        int curr = 0;
        for (int i = 0; i < closed.size(); ++i) {
            if (closed[i]) {
                ++curr;
            } else {
                res = max(res, curr);
                curr = 0;
            }
        }
        res = max(res, curr);
        return res;
    }
};

动态规划，$\mathrm{dp}[i]$ 表示以 $i$ 结尾的最长有效括号长度。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = (int)s.size();
        if (n == 0) return 0;
        vector<int> dp(n, 0);
        int res = 0;
        for (int i = 1; i < n; ++i) {
            if (s[i] == ')') {
                int pre = i - dp[i - 1] - 1;
                if (pre >= 0 && s[pre] == '(') {
                    dp[i] = dp[i - 1] + 2;
                    if (pre > 0) dp[i] += dp[pre - 1];
                }
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

二分查找，参见 二分查找笔记。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (left == right) return {-1, -1};
        return {left, right - 1};
    }
};

41. 缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = (int)nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) nums[i] = n + 1;
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > n || nums[i] < -n) continue;
            int index = abs(nums[i]) - 1;
            if (nums[index] > 0) nums[index] = -nums[index];
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

46. 全排列

回溯搜索。

class Solution {
public:
    void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path,
             vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums, used, path, result);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        dfs(nums, used, path, result);
        return result;
    }
};

49. 字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<string, vector<string>> map;
        for (auto beg = strs.cbegin(); beg != strs.cend(); ++beg) {
            string key = *beg;
            sort(key.begin(), key.end());
            map[key].push_back(*beg);
        }
        for (auto beg = map.cbegin(); beg != map.cend(); ++beg)
            result.push_back(beg->second);
        return result;
    }
};