如果感觉无聊就刷一道 LeetCode

hsxfjames

众所周知， LeetCode 是一个题库网站，技术面试经常会遇到上面的原题或者变种题，以至于在国内外都掀起了刷题热潮。然而我的目的比较纯粹，单纯就是颓废久了感觉脑子都不好使了，找几个算法题练练手，不定期更新几个题解，顺便看看大家有没有别的想法可以碰撞一下。当然了我比较头铁，肯定是按顺序开始的，别指望靠我的帖子找工作 : )

hsxfjames

1. Two Sum

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Sample Input

[2,7,11,15]
9

Sample Output

[0,1]

基本题意

给定一组整数，找到两个数，使它们加起来等于目标数，返回这两个数在数组中的下标。并且如果有解的话，总是只有一个解，而同一个数只能使用一次。

解题思路

本题没有给出数据范围，我们可以发散想不同的做法。

暴力

从数组 a_n 中遍历一个数 X ，再从数组遍历一个除 X 以外的数 Y ，测试 X + Y = Target 是否成立，由于只有一个解，只要成立即可返回。由于需要遍历两轮整个数组，最坏时间复杂度 O(N^2) 。

排序 + 二分

对原数组 a_n 进行排序后，先从有序的数组 a'_n 中遍历一个数 X ，再从中查找 Y = Target - X 是否存在，若存在即找到了符合题目要求的数 X 和 Y ，还原它们在原数组中的下标即为答案。由于还要存储它们的原下标，额外的空间复杂度为 O(N) 。
如果给定的数都为正数，我们还可以做一个小优化。显然当 X \leq Y 时总满足 X \leq \frac12Target \leq Y ，因此我们可以从不小于 \frac12Target 的最小下界开始查找数 Y ，在大于 \frac12Target 的最小上界之前查找数 X ，即：
X \in [\min(a_n), \inf\{a_i : a_i \ge \frac12Target\}]
且
Y \in [\sup\{a_i : a_i \ge \frac12Target\}, \max(a_n)]
但由于题目没有特别说明数据范围，那么也可能在数组中存在负数，于是这个优化在极端情况中并没有用，最坏时间复杂度 O(NlogN) 。注意由于有排序、找上下界等操作，常数还是较大的。

哈希表

我们也可以对数组 a_n 中所有元素做一个到下标的映射 a_i \xrightarrow{f} i 。由于只是简单查找某个键是否存在并取出其值，而一个元素在原数组中的下标又是唯一的，我们不需要让哈希表维护键之间的序关系，也不需要允许键名或键值重复。

现在对数组遍历一遍，设当前遍历到数 X ，只要从表中查找 Y = Target - X 是否存在即可。若找到，即可返回它们的下标；若没找到，则将 X \xrightarrow{a_i^{-1}} i 存进表中以供下次查询。

建表 O(N) 每次查询 O(1) ，理论平均时间复杂度 O(N) ，理论空间复杂度 O(N) 。

解答代码

排序 + 二分做法

这种做法怎么写都没什么差别，复杂度就是这么高，常数就是那么大。。

C++ 版本（只排序索引 + 手写二分）

Runtime: 12 ms

Memory Usage: 9.5 MB

enum class BSearchType: int {
    LowerBound,
    UpperBound,
    Match
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int N = nums.size();
        vector<int> indexes = this->transformIndexes(nums, N);
        int lowerHalf = this->bSearchPos(nums, indexes, 0, N, target >> 1, BSearchType::LowerBound);
        int upperHalf = this->bSearchPos(nums, indexes, 0, N, target >> 1, BSearchType::UpperBound);
        for (int i = upperHalf - 1; i < N; ++i) {
            int temp = target - nums[indexes[i]];
            int j = this->bSearchPos(nums, indexes, 0, lowerHalf + 1, temp, BSearchType::Match);
            if (~j && j != i && nums[indexes[j]] == temp) {
                return {indexes[j], indexes[i]};
            }
        }
        return {};
    }

private:
    vector<int> transformIndexes(vector<int>& nums, int size) {
        vector<int> indexes(size);
        for (int i = 0; i < size; ++i) {
            indexes[i] = i;
        }
        sort(
            indexes.begin(),
            indexes.end(),
            [&](int i, int j) -> bool { return nums[i] < nums[j]; }
        );
        return indexes;
    }

    int bSearchPos(vector<int>& nums, vector<int>& indexes, int first, int last, int target, BSearchType type) {
        while (first < last) {
            int mid = (first + last) >> 1;
            int num = nums[indexes[mid]];
            if (target < num) {
                last = mid;
            } else if (target > num) {
                first = mid + 1;
            } else {
                if (type == BSearchType::LowerBound) {
                    last = mid;
                } else if (type == BSearchType::UpperBound) {
                    first = mid + 1;
                } else {
                    return mid;
                }
            }
        }
        return type == BSearchType::Match ? -1 : first;
    }
};

C++ 版本（整体排序 + STL）

Runtime: 8 ms

Memory Usage: 9.7 MB

typedef pair<int, int> NumWithIndex;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        size_t size = nums.size();
        const auto compareFn = [](const NumWithIndex& i, const NumWithIndex& j) { return i.first < j.first; };

        vector<NumWithIndex> orderedNums(size);
        for (size_t i = 0; i < size; ++i) {
            orderedNums[i] = {nums[i], i};
        }
        sort(orderedNums.begin(), orderedNums.end(), compareFn);

        NumWithIndex halfTarget = {target >> 1, -1};
        auto lowerHalf = lower_bound(orderedNums.begin(), orderedNums.end(), halfTarget, compareFn);
        if (lowerHalf->first == halfTarget.first) {
            lowerHalf += 1;
        };
        auto upperHalf = upper_bound(orderedNums.begin(), orderedNums.end(), halfTarget, compareFn) - 1;
        if (upperHalf < lowerHalf) {
            upperHalf += 1;
        };
        
        for (auto i = upperHalf; i != orderedNums.end(); ++i) {
            NumWithIndex temp = {target - i->first, -1};
            auto j = lower_bound(orderedNums.begin(), lowerHalf, temp, compareFn);
            if (j != lowerHalf && j->first == temp.first) {
                return {j->second, i->second};
            }
        }
        return {};
    }
};

哈希表做法

C++ 版本

由于 LeetCode 支持 C++11 ，偷懒就用 unordered_map 了。以前打 ACM 比赛都是必备手写哈希表模板的。

Runtime: 4 ms

Memory Usage: 10.1 MB

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        size_t count = nums.size();
        unordered_map<int, int> numToIndex({{nums[0], 0}}, count);

        for (size_t i = 1; i < count; ++i) {
            int current = nums[i];
            const auto iter = numToIndex.find(target - current);
            if (iter != numToIndex.end()) {
                return {iter->second, i};
            }
            numToIndex.insert({{current, i}});
        }
        
        return {};
    }
};

JavaScript 版本

Runtime: 52 ms

Memory Usage: 34.7 MB

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    const numsToIndex = Object.create(null);
    const count = nums.length;
    
    for (let i = 0; i < count; ++i) {
        const numForTest = target - nums[i];
        if (numForTest in numsToIndex) {
            return [numsToIndex[numForTest], i];
        }
        numsToIndex[nums[i]] = i;
    }
    
    return [];
};

hsxfjames

2. Add Two Numbers

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Sample Input

[2,4,3]
[5,6,4]

Sample Output

[7,0,8]

基本题意

给定两个不为空的链表，分别表示两个不带前导零的非负整数。链表中的每个元素是数位，从首到尾逆序存放了所表示整数的每个数位。求两个链表所表示的整数相加后的结果，以同样链表的形式返回。

解题思路

由于数位存放的顺序是逆序的，我们按链表的顺序从首到尾两两相加即可。溢出位递增到下一个元素即可。易错点在于对两个链表长度不一、最后剩余了溢出位等情况的处理。如果是 Java / JavaScript 这类自带大数类型的语言，其实还可以更暴力一点。。

扩展思考

如果整数的数位在单向链表中的存放是正序的，则考虑必须先将链表翻转或者大数做法。因为单向链表只有一个方向，保持正序方向的话，溢出位难以向前累加。

解答代码

链表相加做法

C++ 版本

Runtime: 32 ms

Memory Usage: 11.8 MB

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *p1 = l1, *p2 = l2;
        ListNode res(0), *pRes = &res;
        int carry = 0;
        while (p1 != NULL || p2 != NULL || carry > 0) {
            int sum = carry;
            if (p1 != NULL) {
                sum += p1->val;
                p1 = p1->next;
            }
            if (p2 != NULL) {
                sum += p2->val;
                p2 = p2->next;
            }
            carry = sum / 10;
            sum = sum % 10;
            ListNode *node = new ListNode(sum);
            pRes->next = node;
            pRes = node;
        }
        return res.next;
    }
};

大数相加暴力做法

JavaScript 版本

Runtime: 120 ms

Memory Usage: 40.5 MB

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
const numListGenerator = function* (list) {
    let iter = list;
    while (iter) {
        yield iter.val;
        iter = iter.next;
    }
};

const numListToStr = function (list) {
    return Array.from(numListGenerator(list))
        .reverse()
        .join('');
};

const addTwoNumStr = function (str1, str2) {
    return (BigInt(str1) + BigInt(str2)).toString();
};

const numStrToList = function (str) {
    let len = str.length;
    const head = new ListNode(0);
    let node = head;
    while (--len > -1) {
        node.next = new ListNode(Number(str[len]));
        node = node.next;
    }
    return head.next;
};

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = function (l1, l2) {
    return numStrToList(
        addTwoNumStr(
            numListToStr(l1),
            numListToStr(l2),
        ),
    );
};

Bintou

被你这么一搞，吓到新生都不敢无聊了！