Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 1315. Sum of Nodes with Even-Valued Grandparent

By zxi on January 11, 2020

Given a binary tree, return the sum of values of nodes with even-valued grandparent.  (A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Constraints:

  • The number of nodes in the tree is between 1 and 10^4.
  • The value of nodes is between 1 and 100.

Solution: Recursion

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

C++

花花酱 LeetCode 1316. Distinct Echo Substrings

By zxi on January 11, 2020

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself.

Example 1:

Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Example 2:

Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".

Constraints:

  • 1 <= text.length <= 2000
  • text has only lowercase English letters.

Solution 1: Brute Force + HashSet

Try all possible substrings

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

花花酱 LeetCode 1310. XOR Queries of a Subarray

By zxi on January 5, 2020

Given the array arr of positive integers and the array queries where queries[i] = [Li, Ri], for each query i compute the XOR of elements from Li to Ri (that is, arr[Li] xor arr[Li+1] xor ... xor arr[Ri] ). Return an array containing the result for the given queries.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 10^9
  • 1 <= queries.length <= 3 * 10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] <= queries[i][1] < arr.length

Solution: Prefix Sum

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

C++

tby

花花酱 LeetCode 1312. Minimum Insertion Steps to Make a String Palindrome

By zxi on January 4, 2020

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:

Input: s = "g"
Output: 0

Example 5:

Input: s = "no"
Output: 1

Constraints:

  • 1 <= s.length <= 500
  • All characters of s are lower case English letters.

Solution: DP

dp[i][j] := min chars to insert
dp[j][j] = dp[i-1][j+1] if s[i] == s[j] else min(dp[i+1][j] , dp[i][j-1]) + 1
base case: dp[i][i] = 0
ans: dp[0][n-1]

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

C++

成为更好的自己，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，我们明年这个时候再来检验一下。