Long Luo's Life Notes

每一天都是奇迹

By Long Luo

国庆假期中午吃完饭后给老爸打了个电话,却是姐姐接的。姐姐说,老爸还在山上摘茶籽,都还没有吃饭。姐姐是回家拿蛇皮袋去装茶籽的,等下还要去山上装完茶籽再回家。那到吃饭时都还要一个多小时后了,吃完饭还要去山上摘茶籽。

想到爸爸在家干活时腿不小心受伤了,现在还拖着腿一瘸一拐在山上摘茶籽。在手机上查了下天气,老家现在还是37°的高温,而我在深圳31°时在家里都还要吹空调,心里觉得自己太不孝了。

妈妈说我国庆假期应该回老家去摘茶籽的,不吃点苦都不会体谅父母的辛苦,要不然在家都懒成啥样了。明年国庆一定要回去摘茶籽,吃吃苦,体验下生活。

突然触动起了小时候关于山茶树的一些回忆。

茶籽是什么?很多人是不知道的。但要说到现在大做广告的山茶油,大家就知道了,茶油就是由山茶籽压榨加工而来的,南方80后小时候日常食用的就是山茶油。

茶籽树又叫油茶树,是一种常绿的小乔木。因为它结的果实可以榨油,故叫油茶树。收割完第二季稻子之后,大概霜降时,成熟的茶籽的挂满枝头,像点缀了胭脂的玛瑙一样,沉甸甸的挂在枝头,把树枝都压弯了,煞是好看,看着就令人高兴,或许这就是丰收的喜悦吧!

茶籽树长的很慢,树杆木质十分细密,非常紧实。大多长的不高,茶籽都好摘。够得着的站在地上摘,够不着的爬上树去摘。

早晨是一天采摘中的最佳时辰,天刚亮不久全家一起出发了。采茶籽动作单一,但工作量很大。茶籽数量众多,而且太阳烤背,往往会汗如雨下。一两个小时过后,一家人就摘了几个蛇皮袋,这时到了送袋子回去做饭的时间。刚摘下来的油茶籽重,一般用自行车或者手推车运回家。

送回家之后还要做好饭菜带进山来。在山里吃饭其实是一件很诱惑人的事,吃起来特别的香。

茶籽全部采摘回来以后,就要晒茶籽了。秋天的太阳温度一般没有夏天那么毒,所以茶籽要晒上好几天才行。

晒过几天太阳,茶籽壳便会破裂,露出里面乌黑的茶仁。但只有少数茶籽壳会破裂,其他的都要人工剥开茶籽壳,取出里面一颗颗圆形或扁圆形的茶籽了。

这项工作主要是闲暇时做,印象中小学时吃完饭看电视时,一家人一边看着电视,一边剥茶籽。因为只有晚上才有时间去剥茶籽,所以剥茶籽这项也要做挺久的。读书时也挺讨厌的,因为做完作业没法出去玩了。剥下的茶籽壳可以用作烧柴的燃料,烧火做饭时用,不过大多是冬天放在火笼里。

最后,爸爸会用小推车把茶籽送到附近的油坊去榨油,我也会跟着去。在榨房里,先用机器将茶籽粉碎,入木甑蒸一定时间。出甑后,将原料填入用稻草垫底的圆形铁箍中,制成榨油用的茶籽饼,最后将一块块菜饼整齐地横放进主榨的榨槽内,用木枋挤紧,茶籽饼在巨大压力下从榨河的槽眼流出茶籽油。

茶籽榨油后留下的油饼,也叫“茶枯”,也叫茶麸、茶籽饼,是油茶籽经榨油后的渣饼,我们小时候经常用它敲的粉碎,放在热水里,拿去药鱼。因为这种水呈碱性,而鱼无法忍受,就会因为缺氧而浮出水面。

By Long Luo

The Solutions of LeetCode热题 100 | Top 100 Liked Questions:


No. Problems Difficulty Source Code Solution
001 Two Sum Easy Java 2种方法:暴力 和 HashMap
002 Add Two Numbers Medium Java 2种方法:模拟 和 递归
003 Longest Substring Without Repeating Characters Medium Java
004 Median of Two Sorted Arrays Hard Java 4种方法:合并数组,暴力法,二分搜索,划分数组
005 Longest Palindromic Substring Medium Java
010 Regular Expression Matching Hard Java
011 Container With Most Water Medium Java 2 Approaches: BF and Two Pointers with Image Explaination
015 3Sum Medium Java 3种方法:暴力,Hash,双指针
017 Letter Combinations of a Phone Number Medium Java 4 Approaches: BF 4 Loops, Backtracking, BFS, Queue with Image Explaination
019 Remove Nth Node From End of List Easy Java
020 Valid Parentheses Easy Java
021 Merge Two Sorted Lists Easy Java
022 Generate Parentheses Medium Java 2种方法:暴力法 和 回溯法
023 Merge k Sorted Lists Hard Java
024 Swap Nodes in Pairs Medium Java
025 Reverse Nodes in k-Group Hard Java
031 Next Permutation Medium Java Two Pointers Solution with Detailed Explanation and Code Commented
032 Longest Valid Parentheses Hard Java
033 Search in Rotated Sorted Array Medium Java
034 Search for a Range Medium Java
035 Search Insert Position Medium Java
039 Combination Sum Medium Java
042 Trapping Rain Water Hard Java
045 Jump Game II Medium Java
046 Permutations Medium Java
048 Rotate Image Medium Java
049 Group Anagrams Medium Java
053 Maximum Subarray Medium Java
055 Jump Game Medium Java
056 Merge Intervals Medium Java
062 Unique Paths Medium Java
064 Minimum Path Sum Medium Java
070 Climbing Stairs Easy Java
072 Edit Distance Hard Java
075 Sort Colors Medium Java
076 Minimum Window Substring Hard Java
078 Subsets Medium Java
079 Word Search Medium Java
084 Largest Rectangle in Histogram Hard Java
085 Maximal Rectangle Hard Java
094 Binary Tree Inorder Traversal Medium Java
096 Unique Binary Search Trees Medium Java
098 Validate Binary Search Tree Medium Java
101 Symmetric Tree Easy Java
102 Binary Tree Level Order Traversal Easy Java
104 Maximum Depth of Binary Tree Easy Java
105 Construct Binary Tree from Preorder and Inorder Traversal Medium Java
114 Flatten Binary Tree to Linked List Medium Java
121 Best Time to Buy and Sell Stock Easy Java
128 Longest Consecutive Sequence Hard Java
136 Single Number Easy Java
139 Word Break Medium Java
141 Linked List Cycle Easy Java
142 Linked List Cycle II Medium Java
146 LRU Cache Hard Java
148 Sort List Medium Java
152 Maximum Product Subarray Medium Java
155 Min Stack Easy Java 3种方法:辅助栈,栈,链表
160 Intersection of Two Linked Lists Easy Java
169 Majority Element Easy Java
198 House Robber Easy Java
200 Number of Islands Medium Java
206 Reverse Linked List Easy Java
207 Course Schedule Medium Java
208 Implement Trie (Prefix Tree) Medium Java
210 Course Schedule II Medium Java
215 Kth Largest Element in an Array Medium Java
221 Maximal Square Medium Java
226 Invert Binary Tree Easy Java
230 Kth Smallest Element in a BST Medium Java
234 Palindrome Linked List Easy Java
238 Product of Array Except Self Medium Java
239 Sliding Window Maximum Hard Java
240 Search a 2D Matrix II Medium Java
253 Meeting Rooms II Medium 没权限
279 Perfect Squares Medium Java
283 Move Zeroes Easy Java
287 Find the Duplicate Number Medium Java 9 Approaches: Count, Hash, Sort, Binary Search, Bit, Fast Slow Pointers
297 Serialize and Deserialize Binary Tree Hard Java
300 Longest Increasing Subsequence Medium Java
301 Remove Invalid Parentheses Hard Java
309 Best Time to Buy and Sell Stock with Cooldown Medium Java
312 Burst Balloons Hard Java
322 Coin Change Medium Java
328 Odd Even Linked List Medium Java
337 House Robber III Medium Java
338 Counting Bits Medium Java
347 Top K Frequent Elements Medium Java
394 Decode String Medium Java
399 Evaluate Division Medium Java
406 Queue Reconstruction by Height Medium Java
416 Partition Equal Subset Sum Medium Java
437 Path Sum III Easy Java
438 Find All Anagrams in a String Easy Java 滑动窗口:从HashMap,数组,再到统计字母数量之差
448 Find All Numbers Disappeared in an Array Easy Java
461 Hamming Distance Easy Java
494 Target Sum Medium Java
538 Convert BST to Greater Tree Easy Java
543 Diameter of Binary Tree Easy Java
560 Subarray Sum Equals K Medium Java
572 Subtree of Another Tree Easy Java
581 Shortest Unsorted Continuous Subarray Easy Java
617 Merge Two Binary Trees Easy Java 4 Approaches: Recursion, Iteration, BFS and DFS
621 Task Scheduler Medium Java
647 Palindromic Substrings Medium Java
739 Daily Temperatures Medium Java
763 Partition Labels Medium Java Illustration of the Max Position of the Char in the Partition with Easy Detailed Explanation

By Long Luo

Leetcode中 剑指Offer(专项突击版)


Leetcode题目 难度 解答 Source Code
剑指Offer II 001. 整数除法 Easy Java
剑指Offer II 002. 二进制加法 Easy Java
剑指Offer II 003. 前 n 个数字二进制中 1 的个数 Easy Java
剑指Offer II 004. 只出现一次的数字 Medium Java
剑指Offer II 005. 单词长度的最大乘积 Medium Java
剑指Offer II 006. 排序数组中两个数字之和 Easy Java
剑指Offer II 007. 数组中和为 0 的三个数 Medium Java
剑指Offer II 008. 和大于等于target的最短子数组 Medium Java
剑指Offer II 011. 0 和 1 个数相同的子数组 Medium Java
剑指Offer II 012. 左右两边子数组的和相等 Easy Java
剑指Offer II 081. 允许重复选择元素的组合 Easy Java
剑指Offer II 085. 生成匹配的括号 Medium Java

By Long Luo

最近在做 Leetcode学习计划 中的 2021届秋季校招笔试真题 时,在这道题上 meituan-002. 小美的仓库整理 卡了一点时间,在此记录下自己从困惑到最终解决的全过程,吸取经验教训,提高自己知识水平。

题目

这是一道Medium难度的题目,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
meituan-002. 小美的仓库整理

小美是美团仓库的管理员,她会根据单据的要求按顺序取出仓库中的货物,每取出一件货物后会把剩余货物重新堆放,使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物,则会把货物所在的一堆物品以取出的货物为界分成两堆,这样可以保证货物局部的顺序不变。
已知货物最初是按1~n的顺序堆放的,每件货物的重量为w[i] ,小美会根据单据依次不放回的取出货物。请问根据上述操作,小美每取出一件货物之后,重量和最大的一堆货物重量是多少?

格式:

输入:
- 输入第一行包含一个正整数 n ,表示货物的数量。
- 输入第二行包含n个正整数,表示1~n号货物的重量w[i]。
- 输入第三行有n个数,表示小美按顺序取出的货物的编号,也就是一个1~n的全排列。

输出:
- 输出包含n行,每行一个整数,表示每取出一件货物以后,对于重量和最大的一堆货物,其重量和为多少。

示例:

输入:
5
3 2 4 4 5
4 3 5 2 1

输出:
9
5
5
3
0

解释:
原本的状态是{{3,2,4,4,5}},取出4号货物后,得到{{3,2,4},{5}},第一堆货物的和是9,然后取出3号货物得到{{3,2}{5}},此时第一堆和第二堆的和都是5,以此类推。

提示:
1 <= n <= 50000
1 <= w[i] <= 100

请注意,本题需要自行编写「标准输入」和「标准输出」逻辑,以及自行import/include需要的library。了解书写规则

从题意来看,这道题目并不难,所以当时看到题目之后,马上刷刷开始做题,觉得太简单了!

阅读全文 »

By Long Luo

之前虽然知道 KMP 算法,但是一直无法深入理解其原理,最近看了 2 篇文章:从头到尾彻底理解KMP(2014年8月22日版)KMP算法教程 ,然后再实际写代码,终于对 KMP\textit{KMP} 算法有了一定了解了,下面写一写我个人的学习过程。

这篇文章主要从我个人学习过程来叙述:

为了解决什么问题?

KMP\textit{KMP} 算法是一种字符串匹配算法,可以在 O(n+m)O(n+m) 的时间复杂度内实现两个字符串的匹配。

所谓字符串匹配,是这样一种问题:

  1. 字符串 P\textit{P} 是否为字符串 S\textit{S} 的子串?
  2. 如果是,P\textit{P} 出现在 S\textit{S} 的哪些位置?

其中 S\textit{S} 称为主串P\textit{P} 称为模式串

最常见的就是经常要用的搜索功能,比如要在一大段文字中找到某个句子或者找到出现的全部位置。在这种场景下,要找的句子就是给定的模式 P\textit{P},而大段文字就是目标字符串 S\textit{S}

从暴力法开始

我们先从最直观的地方开始:

  1. 两个字符串 A\textit{A}B\textit{B} 的比较?
  2. 如果 P\textit{P}S\textit{S} 的字串,第一个出现的位置在哪里?

所谓字符串比较,就是问两个字符串是否相等

最朴素的思想,就是从前往后逐字符比较,一旦遇到不相同的字符,就返回 False\textit{False} ;如果两个字符串都结束了,仍然没有出现不对应的字符,则返回 True\textit{True}

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int Search_BruteForce(String targetStr, String patternStr) {
int targetLen = targetStr.length();
int patLen = patternStr.length();

for (int i = 0; i < targetLen; i++) {
if (targetStr.charAt(i) == patternStr.charAt(i)) {
for (int j = 1; j < patLen; j++) {
if (targetStr.charAt(i + j) != patternStr.charAt(j)) {
break;
}

if (j == patLen - 1) {
return i;
}
}

}
}

return -1;
}

或者双指针版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int ViolentMatch(String targetStr, String patternStr) {
int targetLen = targetStr.length();
int patLen = patternStr.length();

int i = 0;
int j = 0;
while (i < targetLen && j < patLen) {
if (targetStr.charAt(i) == patternStr.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}

if (j == patLen) {
return i - j;
} else {
return -1;
}
}

暴力解法复杂度分析

刚才我们成功实现了暴力算法,那么其时间复杂度如何?

nn 为串 S\textit{S} 的长度,mm 为串 P\textit{P} 的长度。

考虑“字符串比较”这个小任务的复杂度。最坏情况发生在:两个字符串唯一的差别在最后一个字符。这种情况下,字符串比较必须走完整个字符串,才能给出结果,因此复杂度是 O(len(str))O(len(str)) 的。

由此,不难想到暴力算法所面对的最坏情况:

主串形如 “AAAAAAAAAAAAA…B” ,而模式串形如 “AAAAA…B” 。每次字符串比较都需要付出 O(m)O(m) 次字符比较的代价,总共需要比较 nn 次,因此总时间复杂度是 O(nm)O(nm)

那么如何改进呢?

信息熵冗余

我们很难降低字符串比较的复杂度(因为比较两个字符串,真的只能逐个比较字符)。因此,我们考虑降低比较的趟数。如果比较的趟数能降到足够低,那么总的复杂度也将会下降很多。

要优化一个算法,首先要回答的问题是“我手上有什么信息?” 我们手上的信息是否足够、是否有效,决定了我们能把算法优化到何种程度。请记住:尽可能利用残余的信息,是 KMP\textit{KMP} 算法的思想所在。

很明显在暴力算法中,模式字符串每次都需要比较,非常复杂,那么这里面有没有优化的时间呢?

阅读全文 »
0%