包子大道消息-無人車燒錢榜單-FB開人-我們是東亞病夫? -Leetcode solution 243

  • 2020 年 2 月 25 日
  • 筆記

包子小道消息@02/08/2020

能夠在無人車領域工作可能是很多程式設計師的夢想，極具挑戰的技術問題，業界頂配的薪資以及關於無人駕駛未來無盡的想像空間。那麼問題來了，你應該去哪家無人車公司效力呢？我一個散步小道消息的怎麼會知道? 但是包子君知道錢包不鼓的公司一定都是耍流氓的公司，那麼誰家的爸鼻更有錢呢？

下圖是幾家公司目前為止燒的錢，錢包厚度，一目了然。幾點補充

  • Waymo(Alphabet), Cruise(GM) and Uber 執拗的證明二八理論，大家一共燒了16B美刀，三家燒了 一半多(只要能燒錢的事兒好像Uber都沒有落下，怎麼能這麼牛逼呢）
  • 請注意，燒錢多不一定做出來的效果好，好比地主家的闊少爺如果不異常努力大概率是拼不過佃農家聰明勤奮的泥腿子，一個是競爭，一個是戰爭，不在一個量級。當然，如果地主家的富二代又努力又勤奮，祝賀(s)he! 國之棟樑
  • 你看，谷哥還是你哥，遙遙領先。注意，Nuro和Pony都表現不俗。還有，drive.ai已經被蘋果收了，對，就是你們的最強大腦Ng老師的那個公司 （註：此圖是不需要人工干預可以開的英里數，隨手一引用，並沒有核實，因為還需要給加州dmv發封郵件要數據，包子君懶的同時也不太相信dmv的速度, https://thelastdriverlicenseholder.com/2019/02/13/update-disengagement-reports-2018-final-results/, 就暫且相信他們了）
  • 包子君總結了2019到至今一年多一年的時間內加州DMV收到的無人車出事故數據，印證了了那句古話，人在江湖飄，怎能不挨刀（我想起了曾經有一個很水的印度姐姐同事，說她今年perf應該很牛逼，一個outage都沒弄出來，¿Qué? ，你都沒寫幾行程式碼，當然沒有outage了，不求有功但求無過這種想法在程式設計師身上並不適用）https://www.dmv.ca.gov/portal/dmv/detail/vr/autonomous/autonomousveh_ol316
  • 沒有包括一些小的但是非常有前(錢）途的startup，包括國人領先的Pony.ai, 清一色清華北大哈佛MIT領銜的Nuro，畢竟財務暫不公開，難以得知內幕。
  • 股票成功轉成幣圈趨勢的特斯拉也不算，autopilot program打了個擦邊球
  • 那麼錢都怎麼燒了？主要是工資和期權，同學們，行動起來吧！

寫了太多，有點嚴謹了，不過小道消息也不能造謠你說是不是？你看那個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/

Problem Statement

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

Video Tutorial

You can find the detailed video tutorial here

  • Youtube
  • B站

Thought Process

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.

Solutions

 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 }

Implementation

Time Complexity: O(N) where N is the array size

Space Complexity: O(1) Constant space

References

  • Leetcode official solution

VirMach 便宜 VPS

QNews

QNews