Floyd 判圈算法
2017-12-01
判断一个单链表中是否存在环，并找出环的入口： https://leetcode.com/problems/linked-list-cycle-ii/ Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? 不知道 LeetCode 难度评级的标准是什么，有的 hard 题看完题目就有思路，像这种 medium 题我琢磨半天也想不出空间复杂度为 $O(1)$ 的解法。后来了解到这一题已经有著名的解法了，即 Floyd 判圈算法，没错，就是求最短路径的弗洛伊德算法的那个 Floyd。 …
Single Number II
2017-11-27
LeetCode 的一道题，在一个 int 数组中，其余数值均出现了 3 次，只有一个数值出现了 1 次，求这个数： https://leetcode.com/problems/single-number-ii/description/ Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? …
Gas Station
2017-10-14
加油站问题，LeetCode 链接： https://leetcode.com/problems/gas-station/description/ There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. …
求两个有序数组的中位数 Median of Two Sorted Arrays
2017-07-24
这是 LeetCode 上的一道题，求两个有序数组的中位数： https://leetcode.com/problems/median-of-two-sorted-arrays/description/ Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. Follow up: The overall run time complexity should be O(log (m+n)). Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2: …