Huahua's Tech Road

成为更好的自己，2020再出发

By zxi on January 1, 2020

时光飞逝，转眼2019年就过去了，我们迎来了一个崭新的十年，花花在这里祝大家新年快乐！在过去的一年里面，发生了很多事，国际上的、国内的、还是花花自身上的，与其说是多事之秋，我觉得更像是好事多磨。无论是过去的2019年还是已经到来的2020年都会是不平凡的一年，被载入人类的史册。（开头开的太宏大了，我都快写不下去了…）

让我们来看看花花去年年末时候给自己的定的小目标吧：

YouTube订阅9.7K -> 20K，实际24K，2.4x
B站粉丝832 -> 3K，实际11K，12.3x
公众号订阅2.9K -> 5k，实际8.9K，3.1x

没有唬人的标题，没有博眼球的封面，没有大尺度的内容，有的只是便于搜索的题号和题名，万年不变的PPT封面，和枯燥/口齿不清的念白。感谢同学们的不离不弃，全部以指数形式增长（这个时间复杂度有点高啊）。2019年我播种了超过100个视频，收获的是同学们拿到了offer脱离苦海成功上岸的喜悦、感谢信和红包，以及大家的支持与祝福。

除了讲题之外，2019年花花还完成了哪些小目标呢？工作上：晋升，虽然package没涨多少、自己带的实习生也拿到了return offer，感觉很欣慰。生活上：买房，两人合力存了两年多的钱，终于凑够了首付在相当于国内三、四线城市的湾区很偏的地方买了一套小房子。虽然背上了30年的贷款，但总算是敢花钱了：买电视，买家具，智能家居设备，换了新电脑，来了一场说走就走的旅行。相信很多人和我一样，在没买房之前真是喘不过气来，一分钱都不敢乱花。在成为房主之后很快就解锁了很多新技能：水管工、电工、木工、水泥工、油漆工、园艺工。。。以后再和大家慢慢分享经验。2019年也是我的VLOG元年，我原本是一个很快的人。拍摄VLOG让我慢下来，让我能够更仔细地去观察事物，更多地从他人的角度去看待这个世界。

当然2019年也有不少遗憾：三年没有回国了，国内发展日新月异，感觉我已经完全落伍了。长辈们慢慢老去，同龄人聚会结婚生子，这些片段都没有我的存在。跟着我十多年的手机号也由于欠费超过三个月而被注销。连续第三年减肥失败，体重倒是没有增长，但就是减不下来，看来要每天打卡健身环了。在美国待了7年了，英语口语还是没有太大地提高，自己不喜欢说话能怪组里中国人太多吗？没时间读书，通过实践能掌握不少东西，但是理论学习还是不可或缺的，不然你能够达到的高度是有限的。

说了这么多自己的事情是希望打破大家对我的刻板印象，但我相信在下个讲题视频那个一板一眼的花花马上就回来了。

2020年为成为更好的自己再出发，一大波讲题视频正在路上。当然还是要给自己定了几个小目标：每周2个视频，YouTube 40K，B站25K，公众号15K，我们明年这个时候再来检验一下。

花花酱 LeetCode 2. Add Two Numbers

By zxi on December 30, 2019

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution: Simulation

Time complexity: O(max(n,m))
Space complexity: O(max(n,m))

C++

// Author: Huahua

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

int sum = 0;

while (l1 || l2 || sum) {

sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);

l1 = l1 ? l1->next : nullptr;

l2 = l2 ? l2->next : nullptr;

tail->next = new ListNode(sum % 10);

sum /= 10;

tail = tail->next;

}

return dummy.next;

}

};

Java

// Author: Huahua

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode tail = new ListNode(0);

ListNode dummy = tail;

int sum = 0;

while (l1 != null || l2 != null || sum > 0) {

sum += (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val);

tail.next = new ListNode(sum % 10);

tail = tail.next;

if (l1 != null) l1 = l1.next;

if (l2 != null) l2 = l2.next;

sum /= 10;

}

return dummy.next;

}

Python3

# Author: Huahua

class Solution:

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

dummy = tail = ListNode(0)

s = 0

while l1 or l2 or s:

s += (l1.val if l1 else 0) + (l2.val if l2 else 0)

tail.next = ListNode(s % 10)

tail = tail.next

s //= 10

l1 = l1.next if l1 else None

l2 = l2.next if l2 else None

return dummy.next

花花酱 LeetCode 1306. Jump Game III

By zxi on December 29, 2019

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

Solution: BFS / DFS

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool canReach(vector<int>& arr, int start) {

const int n = arr.size();

vector<int> seen(n);

seen[start] = 1;

queue<int> q;

q.push(start);

while (q.size()) {

int cur = q.front();

q.pop();

if (arr[cur] == 0) return true;

for (int i : {-1, 1}) {

int t = cur + i * arr[cur];

if (t < 0 || t >= n || seen[t]) continue;

q.push(t);

seen[t] = 1;

}

return false;

}

};

花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

By zxi on December 29, 2019

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

Each tree has at most 5000 nodes.
Each node’s value is between [-10^5, 10^5].

Solution: Inorder traversal + Merge Sort

Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)

C++

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

int i = 0;

int j = 0;

while (m.size() != t1.size() + t2.size()) {

if (j == t2.size()) m.push_back(t1[i++]);

else if (i == t1.size()) m.push_back(t2[j++]);

else m.push_back(t1[i] < t2[j] ? t1[i++] : t2[j++]);

}

return m;

}

};

C++/STL

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

std::merge(begin(t1), end(t1), begin(t2), end(t2), back_inserter(m));

return m;

}

};

花花酱 LeetCode 1304. Find N Unique Integers Sum up to Zero

By zxi on December 29, 2019

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:

Input: n = 3
Output: [-1,0,1]

Example 3:

Input: n = 1
Output: [0]

Constraints:

1 <= n <= 1000

Solution: Generation

Use numbers from {-n/2, … n/2} + {0 if n is odd}

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> sumZero(int n) {

vector<int> ans;

for (int i = 1; i <= n / 2; ++i) {

ans.push_back(i);

ans.push_back(-i);

}

if (ans.size() != n) ans.push_back(0);

return ans;

}

};