能够在无人车领域工作可能是很多程序员的梦想,极具挑战的技术问题,业界顶配的薪资以及关于无人驾驶未来无尽的想象空间。那么问题来了,你应该去哪家无人车公司效力呢?我一个散步小道消息的怎么会知道? 但是包子君知道钱包不鼓的公司一定都是耍流氓的公司,那么谁家的爸鼻更有钱呢?
下图是几家公司目前为止烧的钱,钱包厚度,一目了然。几点补充
写了太多,有点严谨了,不过小道消息也不能造谣你说是不是?你看那个FB的那个“小铮在硅谷”不就是发了个造谣的视频被脸书fire了嘛
还有个沙雕在华盛顿邮报上面说中国人都是东亚病夫,我希望您老能be respectful而且基于事实,在一个国家莅临磨难的时候为了吸引眼球, 也别怪我去骂你丫的 https://twitter.com/wrmead/status/1224483408807546882
Leetcode solution 243: Shortest Word Distance
Blogger:https://blog.baozitraining.org/2020/02/leetcode-solution-243-shortest-word.html
Youtube: https://youtu.be/0BvmC_JXySg
博客园: https://www.cnblogs.com/baozitraining/p/12100071.html
B站: https://www.bilibili.com/video/av80686932/
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"]
.
Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Problem link
You can find the detailed video tutorial here
It is a bit confusing at first to be confused with the "Edit Distance" problem. However, there are duplicate words in the array, it's just a matter of finding the minimum distance between two words, where words could be found in multiple places in the array.
Brute force way (for each word, find the closest distance with the other word) would give you O(N^2) time complexity where N is the array size. An O(N) optimization would be having two indices for each word and keep updating the minimum distance. It is greedy because the closer the two elements are, the smaller the distance would be.
You can refer to Leetcode official solution for a detailed explanation.
1 public int shortestDistance(String[] words, String word1, String word2) {
2 if (words == null || words.length == 0 || word1 == null || word2 == null || word1.equals(word2)) {
3 return -1;
4 }
5 int minDistance = words.length;
6
7 int wordIndex1 = -1;
8 int wordIndex2 = -1;
9
10 for (int i = 0; i < words.length; i++) {
11 if (words[i].equals(word1)) {
12 wordIndex1 = i;
13 if (wordIndex2 != -1) {
14 minDistance = Math.min(minDistance, Math.abs(wordIndex1 - wordIndex2));
15 }
16 }
17 if (words[i].equals(word2)) {
18 wordIndex2 = i;
19 if (wordIndex1 != -1) {
20 minDistance = Math.min(minDistance, Math.abs(wordIndex1 - wordIndex2));
21 }
22 }
23 }
24
25 return minDistance;
26 }
Time Complexity: O(N) where N is the array size
Space Complexity: O(1) Constant space
References