Divide and conquer!
Add a leading 0 or 1 bit to your existing results so here comes two sub-results: 0{xxxxx} and 1{xxxxx}. How to merge them? Just keep the first sub group and append the second group items reversely so that there is only a 1-bit difference between the end of group 0 and “start” of group 2.

class Solution {
public:
    vector<int> grayCode(int n) {
        if (n == 0)
            return { 0 };
        vector<int> results = { 0, 1 };
        for (size_t i = 1; i < n; ++i)
        {
            for (int j = results.size() - 1; j >= 0; --j)
            {
                results.push_back(results[j] + (1 << i));
            }
        }
        return results;
    }
};

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
Output:"wertf"

[
  "z",
  "x"
]
>Output: "zx"

[
  "z",
  "x",
  "z"
]
Output:""

Solution:

The solution is to build a directed map and find the topological ordering of the characters. Once the map is built, we can always find the “terminal” character which has no succeeding, i.e. the out-degree of that node would be zero. The we remove the character (the node and its edges) from the map and try to find the next such character, so on so forth.

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

For example,  the map built will be:

t: {f}
w: {e}
r: {t}
e: {r}
f: {}

class Solution {
private:
    map<char, set<char>> ch_map;
    void build(const string& w1, const string& w2)
    {
        const int len = std::min(w1.size(), w2.size());
        int i = 0;
        for (i = 0; i < len; ++i)
        {
            if (ch_map.count(w1[i]) == 0)
                ch_map[w1[i]] = set<char>();
            if (ch_map.count(w2[i]) == 0)
                ch_map[w2[i]] = set<char>();
            if (w1[i] != w2[i])
            {
                ch_map[w1[i]].insert(w2[i]);
                break;
            }
        }
        for (; i < w1.size() || i < w2.size(); ++i)
        {
            if (i < w1.size() && ch_map.count(w1[i]) == 0)
                ch_map[w1[i]] = set<char>();
            if (i < w2.size() && ch_map.count(w2[i]) == 0)
                ch_map[w2[i]] = set<char>();
        }
    }
public:
    string alienOrder(vector<string>& words) {
        if (words.empty()) return string();
        if (words.size() == 1) return words[0];
        for (int i = 0; i < words.size() - 1; ++i)
        {
            build(words[i], words[i+1]);
        }
        string result;
        result.reserve(26);
        while (!ch_map.empty())
        {
            bool found = false;
            for (auto it : ch_map)
            {
                if (it.second.empty())
                {
                    found = true;
                    result = it.first + result;
                    break;
                }
            }
            ch_map.erase(result[0]);
            if (!found) return string();  //not found
            for (auto& it : ch_map)
            {
                it.second.erase(result[0]);
            }
        }
        return result;
    }
};

https://leetcode.com/problems/valid-triangle-number/description/
有点类似3Sum的题目。形成三角形的充要条件是最小两边之和大于第三边。可以先给数组排序，然后确定一个最大边，然后在它左边找另外两边。
时间复杂度是O(n*log(n) + n^2) = O(n^2)

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int i = nums.size() - 1; i >= 0; --i)
        {
            // two sum (x + y) > nums[i]
            int j = 0;
            int k = i - 1;
            while (j < k)
            {
                if (nums[j] + nums[k] <= nums[i])
                {
                    j++;
                    continue;
                }
                count += (k - j);
                k--;
            }
        }
        return count;
    }
};

https://leetcode.com/problems/continuous-subarray-sum/description/
这道题跟https://leetcode.com/problems/subarray-sum-equals-k/description/ 其实是很像的，但本题的特点就是corner case非常多…

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if (k < 0)
            k = -1 * k;
        else if (k == 0)
        {
            // check if there's continuous zeroes
            bool has_zero = false;
            for (int num : nums)
            {
                if (num == 0)
                {
                    if (has_zero == true)
                        return true;
                    has_zero = true;
                }
                else
                    has_zero = false;
            }
            return false;
        }
        if (k == 1 && nums.size() > 1)  // tricky but...
            return true;
        int sum = 0;
        unordered_set<int> sum_records;
        vector<int> targets = {k};
        int last_num = INT32_MAX;
        sum_records.insert(0);
        for (int num : nums)
        {
            sum += num;
            sum_records.insert(sum);
            if (last_num == 0 && num == 0)
                return true;    // n = 0
            while (targets.back() + k <= sum)
                targets.push_back(targets.back() + k);  // prvents calculating dup multiplies
            for (int target : targets)
            {
                if (num != target && sum_records.count(sum - target) > 0)
                    return true;
            }
            last_num = num;
        }
        return false;
    }
};