Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 1717. Maximum Score From Removing Substrings

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

  • Remove substring "ab" and gain x points.
    • For example, when removing "ab" from "cabxbae" it becomes "cxbae".
  • Remove substring "ba" and gain y points.
    • For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

Constraints:

  • 1 <= s.length <= 105
  • 1 <= x, y <= 104
  • s consists of lowercase English letters.

Solution: Greedy + Stack

Remove the pattern with the larger score first.

Using a stack to remove all occurrences of a pattern in place in O(n) Time.

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

C++

花花酱 LeetCode 1716. Calculate Money in Leetcode Bank

Hercy wants to save money for his first car. He puts money in the Leetcode bank every day.

He starts by putting in $1 on Monday, the first day. Every day from Tuesday to Sunday, he will put in $1 more than the day before. On every subsequent Monday, he will put in $1 more than the previous Monday.

Given n, return the total amount of money he will have in the Leetcode bank at the end of the nth day.

Example 1:

Input: n = 4
Output: 10
Explanation: After the 4th day, the total is 1 + 2 + 3 + 4 = 10.

Example 2:

Input: n = 10
Output: 37
Explanation: After the 10th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2nd Monday, Hercy only puts in $2.

Example 3:

Input: n = 20
Output: 96
Explanation: After the 20th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.

Constraints:

  • 1 <= n <= 1000

Solution 1: Simulation

Increase the amount by 1 everyday, the decrease 6 after every sunday.

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

C++

Could also be solved using Math in O(1)

告别2020 2021再出发

一定要看到最后!一定要看到最后!一定要看到最后!

看了自己的上一篇微信公众号文章的发表日期已经是大半年前的了,我爸一直在问最近怎么没有看到你的C++(文章)呢?估计不少小伙伴认为花花已经“弃号”了。没有,花花还活着!受疫情影响,从去年三月份开始,花花就开启了在家工作模式至今。什么显示器啊、升降桌啊、屏幕挂灯啊、便携式空调啊、人体工学椅啊,AirPods Pro,鼠标键盘什么的都买了,升级了自己的家庭办公室。但工作效率却没怎么提升(嘘,小声点,别让老板听到)。

升级成4K显示器,用了就回不去了
在家工(chi)作(he)的一天,也算是开启了vlog新技能

随着时间的推移,国内的小伙伴们慢慢地恢复了日常的生活。而美国这边的情况却愈发严重,除了几次短途放风和办证之外,花花这半年都没怎么出门过,更别说坐过飞机和住酒店了。就连以前最喜欢的每周一次的买菜活动也被迫取消了。没有了公司的免费早午晚饭和下午茶,顿顿吃外卖是吃不起的,只能网上买菜自己做了(让Amazon和Weee狠狠赚了一笔!)。面包机、春饼机、空气炸锅、网红章鱼小丸子锅什么的都买上了。虽然开发了一点新菜色,但厨艺却停滞不前,感觉被锁死了!

空气炸锅挺好用的!就是洗起来比较麻烦…
第一次烧蹄膀,有4-5年没吃过了

美国独立日时候去了Big Sur,难得出去透透风,为了复刻macOS Big Sur的桌面壁纸特地去购买了DJI Mavic Air2。没想到第一次飞无人机就拍出了不错的画面(虽然复刻失败了…),然后就吃灰吃到现在,最近倒是被我派去检查房屋的雨水管道是否堵塞…

Bigsur风景还是不错的,想拍macOS同款桌面,没想到失败了…

不能出门在家里能干嘛呢?玩游戏!没错,花花也和大部分男生一样喜欢玩游戏,只是工作之后就不能像以前学生时代那么玩了。现在以Switch游戏为主:塞尔达、异度神剑1/2、风花雪月、健身环等都是我去年玩得比较多的几款游戏,还有动森和宝可梦。全部游戏加起来总共有400多个小时(这么一算好奢侈啊~你也可以说游戏好便宜啊,玩一个小时只要1刀左右)

Switch终于支持和手机“传图”了,原理是开一个wifi热点然后起一个httpserver,手机打开网页再一张张图片保存

过去十多年有无数次可以好好学琴的机会,花花都半途而废了,直到今年终于重新拿起来跟着某app从头开始学。但和玩游戏比起来花花在练琴上花的时间远远不够,还不到100个小时,先立一个1000个小时的小目标吧!

这其实是正式开始学习之前强行背谱弹出来的

在家里还能做什么呢?DIY,乘着感恩节假期把车库全面装修了一番,圣诞节假期又把家里布局调整了一下,也装饰了一下。同时更换了智能开关和插座,现在全家部署了10个智能开关、5个智能插座、4个智能音箱,2个智能屏幕和5个摄像头(其中2个集成了语音助手)。但是语音助手总是把all/on/off听混,同一句话不同的设备听到的结果还不一样,家里的灯开了又关,关了又开…有时候灯开了一个晚上都不知道。可见万物互联也不一定全是好事。

车库大作战
圣诞节装饰和灯展

哈哈,所以说除了码字之外什么都做了!视频一直有在录,LeetCode的题解去年一共制作了89期。我也尝试拓宽自己的“戏路”,挖了不少坑,从《CS大讲堂》、《玩转Linux命令行》、《C++/Python Weekly》、paper讲解、到最近的《系统设计》等,再加上流水账一样的vlog,加在一起2020年也制作了一百多期视频。平均三天一期,算得上是“高产”了,但视频制作的水平还停留在幼儿园阶段。只做自己想做的事情是无法掌握“财富密码”的,但我坚信:赠人玫瑰,手有余香。去年一年大环境不太理想,但还是有将近50位同学向我报告拿到Google/FB/Amazon/Apple/MS/字节等大厂的offer,还有面7拿5的,同学们比我强太多了!年终一总结,顿时感觉自己“伟大”起来了,没有,更多的是责任感和使命感。同时我也要感谢互联网,让我们大家可以在不同的时空中相聚!

同学们收到offer之后的感谢信

2021年已经来了,花花还是会继续给大家带来更多更好的视频!同时也要不断学习新知识,紧跟时代的步伐。最好的学习方法就是把别人讲明白了,您说是不是?

花花

1/4/2020 于离硅谷中心有点距离的家中

花花酱 LeetCode 1713. Minimum Operations to Make a Subsequence

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Example 1:

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: You can add 5 and 1 in such a way that makes arr = [5,9,4,1,2,3,4], then target will be a subsequence of arr.

Example 2:

Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3

Constraints:

  • 1 <= target.length, arr.length <= 105
  • 1 <= target[i], arr[i] <= 109
  • target contains no duplicates.

Solution: Reduce to LIS

The original problem is a LCS (Longest common subsequence) problem that can be solved in O(n*m) time.
Since the elements in the target array is unique, we can convert the numbers into indices that helps to reduce the problem to LIS (Longest increasing subsequence) that can be solved in O(mlogn) time.

e.g.
target: [6,4,8,1,3,2] => [0, 1, 2, 3, 4, 5]
array: [4,7,6,2,3,8,6,1] => [1,-1, 0, 5, 4, 2, 0, 3] => [1, 0, 5, 4, 2, 3]
and the LIS is [0, 2, 3] => [6, 8, 1], we need to insert the rest of the numbers.
Ans = len(target) – len(LIS)

Time complexity: O(nlogm)
Space complexity: O(m)

C++

Python3


花花酱 LeetCode 1712. Ways to Split Array Into Three Subarrays

A split of an integer array is good if:

  • The array is split into three non-empty contiguous subarrays – named leftmidright respectively from left to right.
  • The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10+ 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

  • 3 <= nums.length <= 105
  • 0 <= nums[i] <= 104

Solution 1: Prefix Sum + Binary Search

We split the array into [0 … i] [i + 1… j] [j + 1 … n – 1]
we can use binary search to find the min and max of j for each i.
s.t. sum(0 ~ i) <= sums(i + 1 ~j) <= sums(j + 1 ~ n – 1)
min is lower_bound(2 * sums(0 ~ i))
max is upper_bound(sums(0 ~ i) + (total – sums(0 ~ i)) / 2)

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

C++

Solution 2: Prefix Sum + Two Pointers

The right end of the middle array is in range [j, k – 1] and there are k – j choices.
Time complexity: O(n)
Space complexity: O(1)

C++