题目描述：

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.

Example 1:

1 2 3 4

Input: "1+1i", "1+1i" Output: "0+2i" Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

1 2 3 4

Input: "1+-1i", "1+-1i" Output: "0+-2i" Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

Note:

1. The input strings will not have extra blank.
2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

比较简单的题，因为不用考虑非法的输入，所以直接用+把字符串分割，然后分别提取实部和虚部进行运算，把结果再转换为字符串即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        auto ap = convert(a), bp = convert(b);
        int ra = ap.first * bp.first + (-1) * ap.second * bp.second;
        int rb = ap.first * bp.second + ap.second * bp.first;
        return to_string(ra) + "+" + to_string(rb) + "i";
    }
    pair<int, int> convert (string s) {
        int a, b;
        int plusIndex;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '+') {
                a = stoi(s.substr(0, i));
                plusIndex = i;
                break;
            }
        }
        b = stoi(s.substr(plusIndex + 1, s.length() - plusIndex - 2));
        return make_pair(a, b);
    }
};

题目描述：

In the video game Fallout 4, the quest “Road to Freedom” requires players to reach a metal dial called the “Freedom Trail Ring”, and use the dial to spell a specific keyword in order to open the door.

Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at 12:00 direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character key[i]:

1. You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring’s characters at the 12:00 direction, where this character must equal to the character key[i].
2. If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you’ve finished all the spelling.

Example:

1 2 3 4 5 6 7

Input: ring = "godding", key = "gd" Output: 4 Explanation: For the first key character 'g', since it is already in place, we just need 1 step to spell this character. For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo". Also, we need 1 more step for spelling. So the final output is 4.

Note:

1. Length of both ring and key will be in range 1 to 100.
2. There are only lowercase letters in both strings and might be some duplcate characters in both strings.
3. It’s guaranteed that string key could always be spelled by rotating the string ring.

LeetCode做得比较多了就很容易发现一个规律，就是LeetCode所能接受的最大总时间复杂度大约在10^6左右，根据观察输入数据的规模就能大致的知道所用算法的时间复杂度上限是多少。比如输入数据是10000或以上，那么O(n^2)一般就是TLE（除非大量剪枝有可能勉强能过），如果输入数据是1000，那么O(n^2)就是可接受的。这道题的输入数据规模只有100，所以O(n^3)的算法也是可以的，我用的DP就是三次方的复杂度。

设一个二维数组dp，dp[i][j]表示输入key[i]字符时位于12点位置的是ring[j]字符时所使用的总的步数。显然ring[j]和key[i]要相同，否则直接不用考虑。

DP的基本思想是对于key[i]，从key[i - 1]时所有可能的ring结束位置的总步数+从该位置转到ring[j]所需要的步数+按按钮中选出最小值，就是dp[i][j]的值。

1

dp[i][j] = min(dp[i - 1][k] + 1 + min(abs(k - j), ringLength - abs(k - j))), 0 <= k < ringLength

最后再从dp[keyLength - 1]的所有元素中找到最小值，就是所求的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    vector<vector<int>> ringChar2Index, dp;
public:
    int findRotateSteps(string ring, string key) {
        if (key.empty()) return 0;
        int keyLen = key.length(), ringLen = ring.length();
        
        dp = vector<vector<int>>(keyLen, vector<int>(ringLen, -1));
        
        for (int i = 0; i < ringLen; i++) {
            if (ring[i] == key[0]) {
                dp[0][i] = min(i, ringLen - i) + 1;
            }
        }
        
        for (int i = 1; i < keyLen; i++) {
            for (int j = 0; j < ringLen; j++) {
                if (ring[j] == key[i]) {
                    int step = INT_MAX;
                    for (int k = 0; k < ringLen; k++) {
                        if (dp[i - 1][k] >= 0) {
                            int t = abs(k - j);
                            step = min(step, min(t, ringLen - t) + 1 + dp[i - 1][k]);
                        }
                    }
                    dp[i][j] = step;
                }
            }
        }
        
        int minStep = INT_MAX;
        for (int i = 0; i < ringLen; i++) {
            if (dp[keyLen - 1][i] >= 0) {
                minStep = min(minStep, dp[keyLen - 1][i]);
            }
        }
        
        return minStep;
    }
};

在终端中用ASCII字符播放视频，不是什么新鲜玩意了，只是今天突然想写来玩一玩。

用法

1
2
3
4
5

$ ./ascii_video.py -h
ascii_video.py -i <inputfile> [-s <speed>]
-i: 指定输入视频文件
-s: 播放速度, 与硬件性能有关, 默认为10, 数值越大越快
运行中按q退出, 按p暂停/恢复

• 不仅对视频，对图片也可以用。
• 调小终端字体可以提高效果，但是性能就呵呵了……
• 自适应终端大小，但是比例默认拉伸为16:9

依赖库

本来想直接用C++和ffmpeg来解码视频，但是太复杂了搞得头大，所以就用Python+OpenCV这个组合了。

• OpenCV
• numpy
• curses
• FFmpeg

系统

我在Ubuntu 16.04上写的，Python版本3.5，默认终端。其他系统和终端模拟器没有测试过，我自己也只拿几个视频跑了一下。

效果

原始	ASCII

今天装Docker，在下载image的时候总是链接被重置，用Proxychain也没法代理。通过Google找到https://stackoverflow.com/questions/23111631/cannot-download-docker-images-behind-a-proxy/28093517#28093517，官方文档地址：https://docs.docker.com/engine/admin/systemd/#http-proxy 。通过配置文件来指定http代理。

具体步骤如下：

1. 在/etc/systemd/system目录下创建docker.service.d目录
2. 在docker.service.d目录中创建文件http-proxy.conf文件
3. 在配置文件中添加：

1
2

[Service]
Environment="HTTP_PROXY=http://proxy.example.com:80/"

4. 可以使用NO_PROXY变量指定不走代理的地址：

1

Environment="NO_PROXY=localhost,127.0.0.0/8,docker-registry.somecorporation.com"

5. 运行sudo systemctl daemon-reload更新设置
6. 使用systemctl show --property=Environment docker来查看设置是否生效

1

Environment=HTTP_PROXY=http://proxy.example.com:80/

7. 重启Docker：sudo systemctl restart docker

我的系统是Ubuntu 16.04，用ss-qt来科学上网，代理服务器的地址填写ss的地址就可以了。要注意ss应设置为http代理而不是socks5。

题目描述：

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Example:

1 2	Input: s = "abcdefg", k = 2 Output: "bacdfeg"

**Restrictions:**The string consists of lower English letters only.Length of the given string and k will in the range [1, 10000]

按照题目要求翻转字符串即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    string reverseStr(string s, int k) {
        int k2 = k << 1;
        int i;
        for (i = 0; i < s.length(); i += k2) {
            if (i + k <= s.length())
                reverseStr(s, i, i + k);
            else
                reverseStr(s, i, s.length());
        }
        return s;
    }
    
    void reverseStr(string &s, int left, int right) {
        for (int i = 0; left + i < right - i - 1; i++) {
            swap(s[left + i], s[right - i - 1]);
        }
    }
};

题目描述：

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

1 2 3

Input: ["23:59","00:00"] Output: 1

Note:

1. The number of time points in the given list is at least 2 and won’t exceed 20000.
2. The input time is legal and ranges from 00:00 to 23:59.

先进行排序，然后依次计算相邻时间的时间差，这个时间差有两个方向，选择较小的一个。最后要注意还要算最后一个时间与第一个时间的时间差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() >= 1440) return 0;
        sort(timePoints.begin(), timePoints.end());
        int minDiff = INT_MAX;
        for (int i = 1; i < timePoints.size(); i++) {
            minDiff = min(minDiff, calcDiff(timePoints[i - 1], timePoints[i]));
        }
        minDiff = min(minDiff, calcDiff(timePoints[0], timePoints.back()));
        return minDiff;
    }
    
    int calcDiff (string &a, string &b) {
        int aH = stoi(a.substr(0, 2)), 
            bH = stoi(b.substr(0, 2)),
            aM = stoi(a.substr(3, 2)),
            bM = stoi(b.substr(3, 2));
            
        int diff;
        
        if (bH == aH) {
            return bM - aM;
        }
        else {
            diff = (60 - aM) + bM + (bH - aH - 1) * 60;
        }
        return min(diff, 1440 - diff);
    }
};

题目描述：

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1: Input:

1 2

"bbbab"

Output:

1 2

4

One possible longest palindromic subsequence is “bbbb”.

Example 2: Input:

1 2

"cbbd"

Output:

1 2

2

One possible longest palindromic subsequence is “bb”.

二维DP。dp[i][j]表示s[i]到s[j]（含两端）的字符串中最长的回文子串。状态转移方程如下：

1. i==j，dp[i][j]=1
2. s[i]==s[j-1]，dp[i][j]=2
3. s[i]==s[j]， dp[i][j]=dp[i+1][j-1]+2
4. s[i]!=s[j]，dp[i][j]=max(dp[i+1][j], dp[i][j-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.length(), vector<int>(s.length(), 0));
        if (s.empty()) return 0;
        int maxLen = 1;
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = 1;
        }
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.length(); j++) {
                if (s[i] == s[j]) {
                    if (i + 1 == j) dp[i][j] = 2;
                    else dp[i][j] = dp[i + 1][j - 1] + 2;
                }
                else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.length() - 1];
    }
};

题目描述：

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

1 2	((2-1)-1) = 0 (2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

1 2 3 4 5

(2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

一开始我以为这是个排列组合问题，实际上也确实是，但是使用分治+递归可以更容易的解决。使用每个运算符把算式分割成两部分，再对两部分分别递归地处理，直到没有运算符，就直接返回数值。两边的字符串分别返回一个结果数组，根据操作符对数组中的元素两两进行运算，将结果放到结果集中返回给上一层函数。

要注意的是这道题并不用去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        return diffWaysToComputeImpl(input, 0, input.length());
    }
    
    vector<int> diffWaysToComputeImpl(string &input, int left, int right) {
        vector<int> ans;
        for (int i = left; i < right; i++) {
            if (isOperation(input[i])) {
                auto leftResult = diffWaysToComputeImpl(input, left, i);
                auto rightResult = diffWaysToComputeImpl(input, i + 1, right);
                for (auto j : leftResult) {
                    for (auto k : rightResult) {
                        ans.push_back(operate(j, k, input[i]));
                    }
                }
            }
        }
        if (ans.empty()) {
            ans.push_back(stoi(input.substr(left, right - left)));
        }
        return ans;
    }
    
    int operate (int a, int b, char op) {
        switch(op){
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
        }
    }
    
    bool isOperation (char c) {
        return (c == '+' || c == '-' || c == '*');
    }
};

题目描述：

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:

1 2 3 4 5

Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

1 2 3 4

Input:[1, 2, 3, 4, 5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

1 2 3 4

Input: [1, 3, 1, 5, 4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won’t exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

寻找有多少组差的绝对值等于k的数。先对数组进行排序，然后用双指针从前向后搜索：

1. 移动右指针，直到左右指针元素之差的绝对值大于等于k；
2. 再移动左指针，直到左右指针元素之差的绝对值小于k；
3. 重复1,2步直到右指针到达数组结尾，记录下出现过的k的次数；

为了去重要跳过已经出现的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int p1 = 0, p2 = 1;
        int len = nums.size();
        if (len < 2) return ans;
        while (p1 < len && p2 < len) {
            int diff = nums[p2] - nums[p1];
            if (diff == k) {
                ans++;
                do {p1++;} while (p1 < len && nums[p1 - 1] == nums[p1]);
                do {p2++;} while (p2 < len && nums[p2 - 1] == nums[p2]);
            }
            else if (diff < k) {
                p2++;
            }
            else {
                p1++;
            }
            if (p1 >= p2) p2 = p1 + 1;
        }
        return ans;
    }
};

题目描述：

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Note: Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.

短链接的维护，但不限制内部如何生成短链接。就是Hash表的问题，我直接使用的unordered_map容器所提供的Hash函数对原链接进行处理，得到一个数值，然后将该数值转换为62进制字符串（10个数字+大小写字母各26个），该字符串作为短链接的后缀部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    string tinyUrlPrefix = "http://tinyurl.com/";
    unordered_map<string, string> urls;
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        auto hashFunc = urls.hash_function();
        size_t key = hashFunc(longUrl);
        string shortUrl = tinyUrlPrefix + convertToSixtyTwoBase(key);
        urls[shortUrl] = longUrl;
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return urls[shortUrl];
    }
    
    string convertToSixtyTwoBase (size_t key) {
        string str;
        while (key > 0) {
            int mod = key % 62;
            if (mod < 10) str.push_back(mod + '0');
            else if (mod < 36) str.push_back(mod - 10 + 'a');
            else str.push_back(mod - 36 + 'A');
            key /= 62;
        }
        return str;
    }
};

// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));