Long Luo's Life Notes

By Long Luo

1. 冒泡排序(Bubble Sort)

思路与算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static int[] bubbleSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = len - 1; i >= 0; i--) {
        boolean isSorted = true;
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                isSorted = false;
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
        if (isSorted) {
            break;
        }
    }

    return nums;
}

复杂度分析：

• 时间复杂度：\(O(N^2)\) ，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
• 空间复杂度：\(O(1)\) 。

2. 选择排序(Select Sort)

思路与算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static int[] selectSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return nums;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[i]) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
    }

    return nums;
}

复杂度分析：

• 时间复杂度：\(O(N^2)\) ，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
• 空间复杂度：\(O(1)\) 。

By Long Luo

一

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

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

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

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

二

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

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

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

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

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

By Long Luo

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

By Long Luo

Leetcode中 剑指Offer（专项突击版）

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。了解书写规则

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