划水 leetcode：1&2

前言

今年以来工作比较稳定 —— 重复枯燥的 UI 堆砌以及实现十分匪夷所思的产品逻辑 —— 长期诸如此类的的业务迭代，导致自己严重怀疑自己的存在价值。所以，同样是虚度光阴划水摸鱼，不如做点可以提升自己的事，比如刷算法题。_由于笔者不喜社交、抗拒组队、讨厌应试，因而大学时没有报名参加 ACM ，但现在回想很遗憾，不过现在开始学也不晚。_

闲言少叙，开始刷题。笔者用的是 https://leetcode.com/problems 上面的题目，暂时不考虑根据难易程度和题型分类做题，因为，目前（笔者写作时）的程度分不分难易或题型都一样。

1.Two Sum

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.

审题&思路

这道题的题意大致是，给出一组整数数组，返回一组两数之和是给定目标数字的下标的数组。

思路误区

• 本题有一个暗藏的要求是，如果有数组中存在多组符合要求的数据，直接返回一组即可。我一开始由于审题有误，做的时候就误解题意，以为需要返回所有的结果，浪费了不少时间，所以审题是首要的。
• 这个题目中给的测试数组可能存在重复的元素，这就会引起相同元素下标取值不同的问题。

解题

本题难度为简单。
解题思路：本题比较简单粗暴的方法是双重循环遍历，找到一组解直接返回。由于刚开始刷算法，所以先用比较熟悉的 Swift 做一遍试水。

两轮遍历

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var i = 0
        while i < nums.count {
            var j = nums.count - 1
            while j > 0 {
                if nums[i] + nums[j] == target && i != j {
                    return [i, j]
                }
                j -= 1
            }
            
            i += 1
        }
        return []
    }
}

简单粗暴的方法可以通过 Easy 的时间复杂度要求 O(n^2)。但若要降低时间复杂度，可以采用牺牲空间复杂度的办法实现。第二遍优化我选择 C++ 实现，毕竟 C++ 做算法题有优势。

一轮遍历 Hash Map

这道题其实主要考察 Map，因为，Map 这个数据类型可以记录数组元素的 Key 值，从而减少一边循环带来的时间损耗。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::vector<int> result;
        std::map<int, int> temp;
        for (std::vector<int>::iterator i = nums.begin(); i != nums.end(); ++i)
        {
            int diff = target - *i;
            cout << "diff:" << diff << " = " << target << "-" << *i << endl;
            
            int index = i - nums.begin();

            if (temp.find(diff) != temp.end()) {
                int key = temp[diff];
                cout << "Found:" << " nums[" << index << "] = " << *i << " + " << nums[key]  << "=" << target << endl;
                
                if (nums[key] + *i == target)
                {
                    result.push_back(key);
                    result.push_back(index);
                    return result;
                } else {
                    continue;
                }
            }

            temp[*i] = index;
            cout << "*i" << ":" << *i << " temp["<< diff <<"]:" << temp[diff] << " index:" << index << endl;
        }
        return result;
    }
    
};

解题总结

• C++ Vector 中获得当前迭代器的下标用 i - nums.begin(); 即可获得。
• 在 Map 中找到当前元素对应的差值，仍然需要判断数组对应下标的元素与当前元素的和，因为不同元素，可能存在相同的差值。
• 解算法题最重要的是时间复杂度，有时候为了达到更佳的时间复杂度可以牺牲空间复杂度。比如，Tow Sum 中用一轮遍历就要牺牲物理存储用于记录下标减少循环的时间消耗。

2.Add Two Numbers

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.

审题&思路

这道题的题意大致是，给定两个非空链表表示两个非负整数，并且是逆向存储，每个链表的节点的值仅存储一个数字，用一个链表表示两数之和。

思路误区

• 不要试图先把链表转成整数相加计算结果，再把数字结果转成链表，那样更麻烦。应该每个节点（逐位）相加，满十进一，合成新链表。

解题

本题难度为适中。由于题目中已经明确指定用链表，所以优先选择 C++。

解题思路： 每个节点（逐位）相加，满十进一，合成新链表。此外，每位相加的和最大值为 9+9=18，所以不用考虑进 2 的情况。

逐位相加，构造链表

/**
 * 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 *p = l1;
        ListNode *q = p;
        ListNode *k = l2;
        ListNode *j = k;
        ListNode *l = NULL;
        ListNode *h = l;
        ListNode *w = h;
        int upNum = 0;
        while(p != NULL || k != NULL || upNum > 0) {
            int sum = 0;
            sum += upNum;
            upNum = 0;
            if (p != NULL) {
                sum += p->val;
                q = p;
                p = p->next;
            }
   
            if (k != NULL) {
                sum += k->val;
                j = k;
                k = k->next;
            }

            int value = sum;
            if (sum >= 10) {
                upNum = sum / 10;
                int left = sum - upNum * 10;
                left = abs(left);
                value = left;
            }

            ListNode *n = new ListNode(value);

            if (l == NULL) {
                l = n;
                h = l;
                w = h;
            } else {
                h->next = n;
                w = h;
                h = h -> next;
            }
        }

        return l;
    }
};

Solution 更优解

以上算法代码虽然通过了 leetcode 的最低时间复杂度，但并不是最优解，所以，参考官方的 Solution 进行思考并重新编写算法代码。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummyHead = new ListNode(0);
        ListNode *p = l1; 
        ListNode *q = l2; 
        ListNode *current = dummyHead;
        int carry = 0;
        while (p != NULL || q != NULL) {
            int x = (p != NULL) ? p->val : 0;
            int y = (q != NULL) ? q->val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
            if (p != NULL)
            {
                p = p->next;
            }

            if (q != NULL)
            {
                q = q->next;
            }
        }

        if (carry > 0)
        {
            current->next = new ListNode(carry);
        }
        return dummyHead->next;
    }
};

解题思路：看了官方的题解，基本和自己想的一致，但官方比较出彩的是，用更简洁的代码得到链表。先判断节点是否为空，如果当前节点为空，那么表明当前列表的这一位为 0，简洁明了。

但比较奇怪的是，提交官方算法之后，竟然和我自己的算法性能一致，我伙呆。原来官方给的答案也并不一定是最优解，还是要以所用语言的总提交结果来比较相同语言的性能。所以 Solution 下面才会有 comments，各种秀代码。但与此同时，不同语言的性能还是有差距的，我的代码执行时间 28ms 只比 28% 快一点，但评论里的 Python3 102ms 有 181 个🌟。所以，C++ 还是最适合做算法优化的语言。

解题总结

• 在做题时可以在稿纸上画链表辅助算法编写。
• 原来官方提供的解也并不能打败 70% 的存在。

总结

这一篇先总结两道题目，我会继续努力做题，争取早日和那些算法大神们一起玩耍。前几道题都是用来熟悉算法做题技巧的，我准备先做二十道左右，然后系统开始练算法，正好双十一快到了，买买买，加满购物车 😂。当然，钱买不来知识，还是要自己做题。