要找到缺失的第一个正数，就可以把数组范围内的 nums[i] 放到 nums[i]-1 的位置上去，比如 2 放到 1， 3 放到 2，那么最后交换好的数组从头到尾遍历的第一个 nums[i] != i+1 的位置即为缺失的第一个正数。因为这样做最多只产生 n 次 swap，所以最终时间复杂度仍然是 O(n)func firstMissingPositive(nums []int) int ...
Articles in the category of 编程技术杂谈与总结
- Home
- 编程技术杂谈与总结
这个其实就是模拟竖式计算，我们可以开一个 n+m 大小的数组用来保存结果，因为$num1 < 10^n且num2 < 10^m$，所以 $nu...
打家劫舍定义 dp[i] 为前 i 个房子抢到的最大金额，那么有 $dp[i] = max(dp[i-1], dp[i-2] + nums[i])$func rob(nums []int) int { n := len(nums) if n == 1 { return nums[0] } dp := make([]int, n) dp[...
// 堆排 func heapSort(nums []int) { n := len(nums) if n < 2 { ...
这个题目总共能买卖两次，且必须要先卖掉第一次才能买第二次的，所以可以从左往右扫描获得 [0, i] 的最大盈利，从右往左扫描 [i, n-1] 的最大盈利，然后 left[i] + right[i] 的最大值就是两次购买的最大盈利了。func maxProfit(prices []int) int { n := len(prices) minLeft := prices[0]...