Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = “makes”, word2 = “coding”, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
原题地址

感觉自己就跟zz一样。

首先扔出自己的2b解法。O(n) time, and O(n) space.

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

int shortestDistance(vector<string>& words, string word1, string word2) {
    unordered_map<string, vector<int>> hash;
    for (int i = 0; i < words.size(); i++)
        hash[words[i]].push_back(i);
    vector<int> vec1 = hash[word1];
    vector<int> vec2 = hash[word2];
    int diff = INT_MAX, i1 = 0, i2 = 0;
    while (i1 < vec1.size() && i2 < vec2.size()) {
        if (vec1[i1] < vec2[i2]) {
            diff = min(diff, vec2[i2] - vec1[i1]);
            i1++;
        }
        else {
            diff = min(diff, vec1[i1] - vec2[i2]);
            i2++;
        }
    }
    return diff;

然后在网上看到比较标准的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int shortestDistance(vector<string>& words, string word1, string word2) {
    int i1 = -1, i2 = -1, diff = INT_MAX;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == word1) {
            i1 = i;
            if (i2 != -1)   diff = min(diff, i1 - i2);
        }
        if (words[i] == word2) {
            i2 = i;
            if (i1 != -1)   diff = min(diff, i2 - i1);
        }            
    }
    return diff;
}

然后又看到了更为简洁的写法。

1
2
3
4
5
6
7
8
9
10
11

int shortestDistance(vector<string>& words, string word1, string word2) {
    int idx = -1, diff = INT_MAX;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == word1 || words[i] == word2) {
            if (idx != -1 && words[i] != words[idx])
                diff = min(diff, i - idx);
            idx = i;
        }
    }
    return diff;
}

精益求精。

记录一下此刻我复杂的心情。

为什么会再安装呢？因为之前是在本机上装的，现在要在服务器上再装一次。本以为有过一次经验的我会顺风顺水，结果是图样图森破，不过挣扎了一晚上总算是把scrapy给装上了。本来想记录一下出现的问题及解决方法，但是问题太多实在记不住了，而且出现的问题和第一次的也完全不一样。与其记住一次问题的解决答案，不如掌握解决问题的方法（才不是因为脑子不好记不住呢，哼唧）。下一次安装scrapy的时候应该也会出现一万个问题吧，只要不断的把出现的问题丢给google，相信问题一定会解决的😂。

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
原题地址

思路：Two pointers，从两边向中间找。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

vector<int> twoSum(vector<int>& numbers, int target) {
    int begin = 0, end = numbers.size() - 1;
    while (end > begin) {
        int sum = numbers[begin] + numbers[end];
        if (sum < target)
            begin++;
        else if (sum > target)
            end--;
        else
            break;
    }
    vector<int> re = {begin + 1, end + 1};
    return re;

Assume you have an array of length n initialized with all 0’s and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.
原题地址

Google OA题。思路就是先把每一步的操作加、减到开始、结束位，最后累积求和。
不知道为什么速度不是很快，代码如下：

1
2
3
4
5
6
7
8
9
10
11

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    vector<int> re(length + 1, 0);
    for (vector<int> & vec: updates) {
        re[vec[0]] += vec[2];
        re[vec[1] + 1] -= vec[2];
    }
    re.pop_back();
    for (int i = 1; i < length; i++)
        re[i] += re[i - 1];
    return re;        
}

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
原题地址

原理很简单，如果发现有违反规则的就跟前一个交换。一开始理解这道题认为就是一大一小交替排列，跑了一遍发现第一个必须是小。代码如下：

1
2
3
4
5
6
7
8
9
10

void wiggleSort(vector<int>& nums) {
    int diff = -1;
    for (int i = 1; i < nums.size(); i++) {
        int temp = nums[i] - nums[i - 1];
        if (diff * temp > 0)
            swap(nums[i - 1], nums[i]);
        diff = -diff;
    }
    return;
}

看了网上的答案，发现我的脑回路果然跟主流的不一样XD。正常的思路应该是，奇数位的要比前面大，偶数位的要比前面小。代码如下：

1
2
3
4
5
6

void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++)
        if (((i & 1) && nums[i] < nums[i - 1]) || (!(i & 1) && nums[i] > nums[i - 1]))
            swap(nums[i], nums[i - 1]);
}

之前断断续续刷了两波leetcode，最近面试发现又忘了差不多了。今天借到了一个会员账号，开始三刷之旅。借鉴一下其他博主的经验，这里把做过的题的思路都整理下来，方便以后回顾。我们优先从上锁题开始吧！

搞了一天终于能够用crontab自动运行scrapy了。

首先crontab是一款可以实现自动运行的工具，最短每分钟执行一次。由于我们需要不停的爬取网站信息，所以需要软件在后台自动运行scrapy。方法很简单，规定每到什么时间执行什么命令就可以了。

那么开始吧，把命令提交给crontab，等了一分钟、两分钟，什么也没有出现。当时我是懵b的，道理我都懂，但是为什么执行不了XD。我的crontab内容是 sh xxx.sh，xxx.sh里面就是scrapy crawl yyy。当然，xxx.sh肯定是没有执行成功的，那么干脆把crontab的内容换成 echo “Hello”吧。Of course还是什么都没有。这时注意到时不时terminal就来一句：You have new mail. 原来crontab会把每次的执行结果发邮件给我，但至少这说明crontab是好使的。但是sh还是总不成功，在网上看了很多帖子、博客，总是没有get the point. 终于，找到了关键的一句话：

1

$ export PATH=$PATH:/usr/local/bin

原因大概是这样的，crontab执行的时候找不到scrapy这个命令，而这个命令在/usr/local/bin里，所以需要加入这个路径，然后就可以正常执行scrapy了。但是还有一个问题，每分钟一封邮件，一会感觉terminal要炸了XD。这个也找到了答案，可以在 * sh xxx.sh后面加上 >> file 2>&1，输出就会写入这个file里了。最后附上清理mail的方法，不然每过一段时间都会提示有new mail。

1
2
3

$ mail
$ delete *
$ q

写的有些啰嗦，主要是想记录一下今天解决的两个问题。不用把问题交给明天的感觉真好。

昨天本来应该开始学习Scrapy（一款爬虫工具）的，但是卡在Scrapy安装的过程上。究其根本，是因为Mac系统的six安装出了问题，终于在层层Google之后找到了解决办法。

首先，在使用pip install Scrapy的时候，会卡在无法uninstall six上。然后我选择了–ignore-installed six的方法，虽然不会卡住，但在运行Scrapy的时候还是会报错。然后又搜到了这篇文章，第一个答案给出了解决办法，但第二步会提示not permitted。好在在答案的回复给出了解决办法，方法就是重启到recovery mode，然后运行csrutil disable。重启之后就可以删掉six并重新安装了。安全起见，我又重启到recovery mode重新csrutil enable。至此问题基本解决。

这个问题应该只出现在mac OS上，整理一下解决方法方便以后使用。

在命令行直接输入hexo new 中文名称时，生成的md文件会出现乱码，即使在_config.yml修改语言也没有效果。目前没找到完美的解决方法，可替换的选择是hexo new一个英文名称，然后再修改title。

This is actually the first blog I write on this site. From now on, I will keep tracking the things I learn, the thoughts I come up and the world I understand.