既然开始刷题了，就要刷个明白！所以..！一边做，一边记录 Python 和 C++ 的语法/算法技巧吧 ~

总结一下LeetCode里得到的经验！( ´ ▽ ` )

首先加上 from typing import List

2. Add Two Numbers

# Linklist / Pointer

    class Solution:
        def addTwoNumbers(self, l1, l2):
            carry = 0
            res = n = ListNode(0)
            while l1 or l2 or carry:
                if l1:
                    carry += l1.val
                    l1 = l1.next
                if l2:
                    carry += l2.val
                    l2 = l2.next
                carry, val = divmod(carry, 10)
                n.next = n = ListNode(val)
            return res.next

4. Median of Two Sorted Arrays

Python里求均值、中位数和众数的方法：

    import numpy as np
    # AVG
    np.mean(nums)

    # Median
    np.median(nums)

    # Mode
    counts = np.bincount(nums)
    np.argmax(counts)

I used a silly method at first, with pretty slow speed.

Check out this O(log(min(m,n))) solution then!

6. ZigZag Conversion

# String

To convert list into string in Python. Simply use "".join(str). This will make '' between every single chars.

for val in hashlist.values():
result += "".join(val)

9. Palindrome Number

# String

C++11 introduces std::stoi (and variants for each numeric type) and std::to_string, the counterparts of the C atoi and itoa but expressed in term of std::string.

When choosing convert int to string in C++, simply #include <string> and call it to handle variant length string!

    std::string str = std::to_string(x);
    string ss = to_string(x);
    int len = ss.length();
    for(int i=0, j=len-1; i<j; i++, j--) if(ss[i] != ss[j]) return false;

A pure math implementation is:

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0 || (x != 0 && x % 10 == 0))
            return false;
        long int sum = 0;
        long int temp = x;
        while(temp > 0){
                sum = 10 * sum + temp % 10;
                temp /= 10;
        }
        if(x == sum){
            //printf("True");
            return true;
        }
        else{
            //printf("False");
            return false;
        }
    }
};

12. Integer to Roman

C++ 里的map底层是用类似红黑树的方式存的，默认按照key排序，而且不能直接调用sort函数对value排序。

如果一定要按value排序，该怎么做呢！

// 先定义好重载运算符的struct
typedef pair<string, int> PAIR;

struct CmpByValue {
    bool operator()(const PAIR& lhs, const PAIR& rhs) {
    return lhs.second > rhs.second;
    }
};

// 然后把map中元素转存到vector中按Value排序！
vector<PAIR> vec(ref.begin(), ref.end());
sort(vec.begin(), vec.end(), CmpByValue());

Besides, use for(auto & it : vec) to traverse the vector elegantly.

1

Dynamic Programming

Intuition

As the problem has an optimal substructure, it is natural to cache intermediate results. We ask the question \text{dp(i, j)}dp(i, j): does \text{text[i:]}text[i:] and \text{pattern[j:]}pattern[j:] match? We can describe our answer in terms of answers to questions involving smaller strings.

Longest Common Substring

For completeness, difflib in the standard-library provides loads of sequence-comparison utilities.

For instance find_longest_match which finds the longest common substring when used on strings.

Example use:

from difflib import SequenceMatcher

string1 = "apple pie available"
string2 = "come have some apple pies"

match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))

print(match)  # -> Match(a=0, b=15, size=9)
print(string1[match.a: match.a + match.size])  # -> apple pie
print(string2[match.b: match.b + match.size])  # -> apple pie

12. Integer to Roman

The only pratical way to convert queue to vector:

std::vector<int> v;
while (!q.empty()) {
    v.push_back(q.front());
    q.pop();
}

15. 3Sum

Classic! Fix 1 pointer then move the rest 2 pointers.

2 Pointers

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int pivot, low, high;
    vector<vector<int>> result;
    // If the current value is greater than zero, break from the loop. Remaining values cannot sum to zero.
    for (pivot = 0; pivot < nums.size() && nums[pivot] <= 0; ++pivot) {
        if (pivot == 0 || nums[pivot-1] != nums[pivot]) {
            low = pivot + 1;
            high = nums.size() - 1;
            while (low < high) {
                int sum = nums[low] + nums[high] + nums[pivot];
                if (sum == 0) {
                    result.push_back({nums[pivot], nums[low++], nums[high--]});
                    // Increment lo while the next value is the same as before to avoid duplicates in the result.
                    while (low < high && nums[low] == nums[low-1])
                        low++;
                } else if (sum < 0)
                    low++;
                else
                    high--;
                }
            }
        }
        return result;
    }
};

23. Merge k Sorted Lists

Linked List / Priority Queue

Definition: priority_queue<Type, Container, Functional>

e.g.

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

The usage of priority queue in C++:

// Write a struct with bool operator()() to customize the comparing function.
struct cmp {
    bool operator()(ListNode* a, ListNode* b){
    // Small -> Large
    return a->val > b->val;
    }
};

// When comparing pair, first cmp 1st elem, then 2nd one.
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
// Pop order: d->c->b

empty - Test whether container is empty (public member function )
size - Return size (public member function )
top - Access top element (public member function )
push - Insert element (public member function )
emplace - Construct and insert element (public member function )
pop - Remove top element (public member function )
swap - Swap contents (public member function )

128. Longest Consecutive Sequence

Union Find / Hash Set

Use s.find() to search elem in set.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // Convert vector to set
        set<int> s(nums.begin(), nums.end());
        int max_streak = 0;

        if (s.size() == 1)
            return 1;
        for (auto it : s) {
            if (s.find(it-1) == s.end()){
                int curt =  it;
                int streak = 1;
                while (s.find(++curt) != s.end()){
                    ++streak;
                }
                max_streak = max(max_streak, streak);
            }
        }
        return max_streak;
    }
};

136. Single Number

Bit Manipulation / Hash Map

A XOR trick to solve this:

If we take XOR of zero and some bit, it will return that bit

a⊕0=a

If we take XOR of two same bits, it will return 0

a⊕a=0

And

a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

So we can XOR(^in Python) all bits together to find the unique number.

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a

338. Counting Bits

Bit Manipulation

Bitwise operator has the same priority with math ones.

for i in range(1, n+1):
    ans[i] = ans[i >> 1] + (i & 1)

So () between (i & 1) is necessary.

215. Kth Largest Element in an Array

Heap / Sort

C++'s sort() has a avg O(NlogN) TC.

e.g. Remember to add () behind greater/lesser

Binary Search

def lower_bound(array, first, last, value):  # 求非降序范围[first, last)内第一个不小于value的值的位置
    while first < last: # 搜索区间[first, last)不为空
        mid = first + (last - first) // 2  # 防溢出
        if array[mid] < value:
            first = mid + 1
        else:
            last = mid
    return first  # last也行，因为[first, last)为空的时候它们重合