Long Luo's Life Notes

[Leetcode][4. 寻找两个正序数组的中位数] 4种方法：合并数组，二分搜索，划分数组

发表于 2021-02-17 更新于 2025-05-03 分类于 Leetcode Waline：阅读次数：本文字数： 5.8k 阅读时长 ≈ 5 分钟

By Long Luo

Leetcode 4. 寻找两个正序数组的中位数，这是一道很经典的题目，非常考察算法功底和逻辑思维能力，下面我们就通过几种解法来吃透这道题吧！

方法一：暴力法（合并数组）

思路与算法：

很直观的解法，先将两个数组按照元素大小合并为一个数组，然后根据新数组长度来决定返回值。

注意在合并数组时，要注意指针边界情况，不要越过数组边界。

代码如下所示：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;

    if (m == 0) {
        if (n % 2 == 0) {
            return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
        } else {
            return nums2[n / 2];
        }
    } else if (n == 0) {
        if (m % 2 == 0) {
            return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
        } else {
            return nums1[m / 2];
        }
    }

    int[] nums = new int[m + n];
    int total = m + n;
    for (int i = 0, j = 0, cnt = 0; cnt < total; ) {
        if (i == m && j < n) {
            nums[cnt++] = nums2[j++];
        } else if (j == n && i < m) {
            nums[cnt++] = nums1[i++];
        } else if (i < m && nums1[i] <= nums2[j]) {
            nums[cnt++] = nums1[i++];
        } else if (i < m && nums1[i] > nums2[j]) {
            nums[cnt++] = nums2[j++];
        }
    }

    if (total % 2 == 0) {
        return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
    } else {
        return nums[total / 2];
    }    
}

其实，在合并数组时，实际上只需要合并到 \(cnt=total/2\) 即可，优化之后如下所示：

public double findMedianSortedArrays_bf_opt(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;

    if (m == 0) {
        if (n % 2 == 0) {
            return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
        } else {
            return nums2[n / 2];
        }
    } else if (n == 0) {
        if (m % 2 == 0) {
            return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
        } else {
            return nums1[m / 2];
        }
    }

    int[] nums = new int[m + n];
    int total = m + n;
    for (int i = 0, j = 0, cnt = 0; cnt <= total / 2; ) {
        if (i == m && j < n) {
            nums[cnt++] = nums2[j++];
        } else if (j == n && i < m) {
            nums[cnt++] = nums1[i++];
        } else if (i < m && nums1[i] <= nums2[j]) {
            nums[cnt++] = nums1[i++];
        } else if (i < m && nums1[i] > nums2[j]) {
            nums[cnt++] = nums2[j++];
        }
    }

    if (total % 2 == 0) {
        return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
    } else {
        return nums[total / 2];
    }
}

复杂度分析：

时间复杂度：\(O(m+n)\)，需要遍历 \(2\) 个数组。
空间复杂度：\(O(m+n)\)，开辟了一个新数组，长度为 \(m+n\)。

阅读全文 »

[LeetCode][18. 四数之和] 4种方法：暴力，双指针，DFS，HashMap

发表于 2021-02-11 更新于 2025-05-02 分类于 Leetcode Waline：阅读次数：本文字数： 8.6k 阅读时长 ≈ 8 分钟

By Long Luo

Leetcode 18. 四数之和题解。

方法一：暴力枚举

思路与算法：

和 15. 三数之和类似，我们先对数组进行排序，然后 \(4\) 层循环即可。

由于结果肯定会出现重复的数字，所以我们使用 \(\texttt{Set}\) 来去重，代码如下所示：

public List<List<Integer>> fourSum(int[] nums, int target) {
	if (nums == null || nums.length < 4) {
		return new ArrayList<>();
	}

	Arrays.sort(nums);
	int n = nums.length;
	Set<List<Integer>> ans = new HashSet<>();
	for (int first = 0; first < n - 3; first++) {
		for (int second = first + 1; second < n - 2; second++) {
			for (int third = second + 1; third < n - 1; third++) {
				for (int fourth = third + 1; fourth < n; fourth++) {
					if (nums[first] + nums[second] + nums[third] + nums[fourth] == target) {
						ans.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth]));
					}
				}
			}
		}
	}

	return new ArrayList<>(ans);
}

我们可以在每次循环中增加判断，防止出现重复四元组，使用 \(\texttt{List}\)：

public List<List<Integer>> fourSum(int[] nums, int target) {
    if (nums == null || nums.length < 4) {
        return new ArrayList<>();
    }

    Arrays.sort(nums);
    int len = nums.length;
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < len - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }

        if ((long)nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target ) {
            continue;
        }

        for (int j = i + 1; j < len - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }

            if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }

            if ((long)nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {
                continue;
            }

            for (int k = j + 1; k < len - 1; k++) {
                if (k > j + 1 && nums[k] == nums[k - 1]) {
                    continue;
                }

                if ((long)nums[i] + nums[j] + nums[k] + nums[k + 1] > target) {
                    break;
                }

                if ((long)nums[i] + nums[j] + nums[k] + nums[len - 1] < target) {
                    continue;
                }

                for (int l = k + 1; l < len; l++) {
                    if (l > k + 1 && nums[l] == nums[l - 1]) {
                        continue;
                    }

                    if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                    }
                }
            }
        }
    }

    return ans;
}

复杂度分析：

时间复杂度：\(O(n^4)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。
空间复杂度：\(O(logn)\)，空间复杂度主要取决于排序额外使用的空间 \(O(logn)\)。

阅读全文 »

[Leetcode][15. 三数之和] 3种方法：暴力，Hash，双指针

发表于 2021-02-05 更新于 2025-05-02 分类于 Leetcode Waline：阅读次数：本文字数： 4.1k 阅读时长 ≈ 4 分钟

By Long Luo

Leetcode 15. 三数之和题解。

方法一：暴力遍历

思路与算法：

首先想到的是暴力枚举\(3\)层循环，但结果肯定会出现重复的数字，我们可以使用HashSet来去除重复元素。

值得注意的是需要先进行排序，如果不排序的话，会返回重复的答案，因为虽然List元素都相同，但顺序不同，还是重复的三元组。

代码如下所示：

public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }

        Set<List<Integer>> ans = new HashSet<>();
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                for (int k = j + 1; k < length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }

        return new ArrayList<>(ans);
	}
}

上述操作会超时，而且使用了Set进行去重，可不可以不用Set呢？

如何才能保证不包含重复的三元组？

保持三重循环的大框架不变，只需要保证：

第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说，我们枚举的三元组 \((a, b, c)\) 满足 \(a \leq b \leq c\) ，保证了只有 \((a, b, c)\) 这个顺序会被枚举到，而\((b, a, c)\) 、\((c, b, a)\) 等等这些不会，这样就减少了重复。

要实现这一点，先将数组中的元素从小到大进行排序，在每次循环中如果判断，防止出现重复的答案。

public List<List<Integer>> threeSum(int[] nums) {
    if (nums == null || nums.length < 3) {
        return new ArrayList<>();
    }

    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);
    int length = nums.length;
    for (int i = 0; i < length - 2; i++) {
        if (nums[i] > 0) {
            break;
        }

        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        for (int j = i + 1; j < length - 1; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }

            for (int k = j + 1; k < length; k++) {
                if (k > j + 1 && nums[k] == nums[k - 1]) {
                    continue;
                }

                if (nums[i] + nums[j] + nums[k] == 0) {
                    ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                }
            }
        }
    }

    return ans;
}

复杂度分析

时间复杂度： \(O(N^3)\) ，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
空间复杂度： \(O(\log N)\)，额外的排序的空间复杂度为\(O(\log N)\) 。

阅读全文 »

TK教主微博精选 --- 值得反复阅读思考的人生智慧

发表于 2021-02-02 更新于 2025-05-03 分类于 Life Waline：阅读次数：本文字数： 167k 阅读时长 ≈ 2:32

@tombkeeper 人称 TK教主，是我很喜欢的一位微博博主，他的很多 Renew微博内容都非常精彩，洞悉人性，值得认真阅读思考。

这里我精选了一些他的微博，内容都非常精彩，值得反复阅读，反复思考。

这篇文章会时不时更新。

2021

正义离不开直觉。比如我问你要不要把医院里躺着的植物人都拿去做器官移植，你第一印象肯定是“这怎么可以”。但你要是去细算经济账：植物人消耗社会资源，不再创造价值，而且也已经没意识了，而这一堆心肝脾肺肾能救很多人……这么一算，好像也有点道理。

对待贫困地区扶植的走偶像路线的代言人是否应比对一般偶像明星在舆论上更加宽容（以免影响相关地区脱贫致富）？

对待贫困地区的家庭暴力是否应比对待发达地区的家庭暴力在舆论上更加宽容（以免影响相关地区脱贫致富）？

这两个问题的答案要么都是肯定，要么都是否定。

如果基金、投行们太过明显地去影响股价，就属于“操纵金融市场”，可以坐牢的。但如果散户们自发组织起来这么干应该怎么办呢？显然法律是没办法的。因为法不责众，也没办法责众。立法者可能也没想过这个问题。在制定相关法律的年代，这种情形根本不可能出现。

大量个体在没有领导者的情况下统一去做某件事，这在有互联网之前很难想象，一定有牵头的。但现在有互联网了，所以原来表示“OK”的手势可以被群氓们变成种族歧视的符号。

但是，散户们真的可能通过互联网组织起来而实现劫富济贫吗？

在美股市场，机构投资者持有市值占比约 95%，散户手上只有 5%。5% 怎么跟 95% 斗？不过这一点并不是核心问题。

核心问题是什么呢？是无中心化的组织形式不可能做到隐匿。

散户们在网上的所有讨论，目标是什么，热度有多高，庄家可以看得清清楚楚。甚至可以 NLP，可以纳入量化交易系统。而庄家在想什么，散户们根本不知道。

有人兴奋地高呼张麻子打倒了黄四郎。他们可能还真说对了，背后肯定会有张麻子——但这些张麻子是散户吗？

乌合之众，意思是一群像凑在一起的乌鸦一样的人。

通过互联网凑在一起的乌合之众是什么？

还是乌合之众。

乌合之众可以有很强的破坏力，无论对什么，包括它们自身。具体到游戏驿站这个事情，只有等最后崩盘的时候，它们才会忽然意识到这一点，努力地挥动翅膀，然后发现上面还有几百米厚的乌鸦。

新冠会像非典一样结束还是会像流感一样长期存在？现在看来更可能是后者。新冠病毒和流感病毒一样容易变异。流感几乎没有长期后遗症，但新冠有。所以，即便有了疫苗，人们对新冠的恐惧也将远大于流感。

那么，新冠对经济和社会的影响可能将是长期的。我们的财务投资和人生投资都要基于这个假设。

“走出舒适圈”和众多常用的说法一样，并不是由精确的概念所组成，因而能以各种不同的方式解读。所以，解读出来的内容和这五个字本身已经没太大关系了，只是反映了解读者的内心而已。

你现在坐在沙发上看电视，很舒适。然后拿起拖鞋抽自己脸。一边抽一边看电视，这就不舒适了。你可以把“走出舒适圈”理解为这种。

现在你能连续做20个俯卧撑。每天就这么练，轻轻松松。但咬咬牙，努努力，费点劲，受点罪，走出舒适圈，可以做 30 个。然而，这么坚持一段时间后，你就又在舒适圈里了。因为这时候 30 个俯卧撑已经变成了你的舒适圈。这样从舒适到不舒适，再从不舒适到舒适，最终有一天 200 个俯卧撑也很舒适。

“走出舒适圈”，不是为了不舒适，而是为了走出，走到另一个地方。“走出舒适圈”是到这个地方所需要付出的代价。不愿意付出这个代价的人，当然也可以按照前一种方式去解读“走出舒适圈”。这样呢，内心会比较舒适。

从基因上看，人类和人类之间自然是不存在生殖隔离的。然而，从基因上看，大丹犬和吉娃娃之间也不存在生殖隔离。

人类对于人类有很多误解。比如，人类认为其他人类和自己至少在一些基本问题上的想法应该差不多。其实人类和人类在思维上的差异比大丹犬和吉娃娃在体型上的差异还要大。

阅读全文 »

如何求解Leetcode中栈(Stack)问题？

发表于 2021-01-29 更新于 2025-05-03 分类于 Data Structures and Algorithms Waline：阅读次数：本文字数： 252 阅读时长 ≈ 1 分钟

By Long Luo

栈(Stack)的数据结构

栈的遍历

LeetCode Stack Problems

Problems	Difficulty	Source Code	Solution
20. 有效的括号	Easy
32. 最长有效括号	Hard
71. 简化路径	Medium
155. 最小栈	Easy
232. 用栈实现队列	Easy
341. 扁平化嵌套列表迭代器	Medium
385. 迷你语法分析器	Medium
726. 原子的数量	Hard
1190. 反转每对括号间的子串	Medium
面试题 03.01. 三合一	Easy
面试题 02.05. 链表求和	Medium