算法第1天: 缺失的第一个正数

February 24, 2020

字数: 223 · 阅读: 2 分钟 · 访问: -

感触为了坚持学习算法, 每篇算法标题写上坚持多少天,以此鼓励自己坚持学下去. 会把自己理解的都写在代码处, 你在看代码时也方便, 为什么这一行这么写. 也是锻炼自己的文档水平. 题目 LeetCode:41题, 困难给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输入: [7,8,9,11,12] 输出: 1 要求: 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间解法一: 利用map+for-range实现 Time: O(n), Space:O(n)不符合题目要求 //解法一: 利用map+for-range实现.时间复杂度O(n), 空间是常数O(n) // 4 ms 2.8 MB func FirstMissingPositive(nums []int) int { hash := make(map[int]struct{}, len(nums)) for i := 0; i < len(nums); i++ { hash[nums[i]] = struct{}{} } fmt.Println(hash) //1-n之间检查, 如果有缺失则是最小值. for i := 1; i <= len(nums); i++ { //从1循环到n, 包含n if _, ok := hash[i]; !

算法第2天: 盛最多水的容器

February 24, 2020

字数: 180 · 阅读: 1 分钟 · 访问: -

LeetCode:11题, 中等解析题目解析题目: 将数组想象成一个矩形, 寻找这个矩形盛最多水的大小. 决定盛水高度取决于最低的那根木板.也就是数字最小的那个值, 决定盛水最多还得取决于它的长度.也就是数组的头与尾之间的距离. 暴力求解. 对数组从小到大都查看一遍, 取最大容器的那个. //暴力求解 //Time:O(n^2), Space:O(1) func ContainerWithMostWater(height []int) int { if len(height) == 0 { return 0 } //暴力求解, 任何可能都不放过. maxArea := 0 //存放最大面积的变量. for i := 0; i < len(height); i++ { for j := i + 1; j < len(height); j++ { //获取最短板的那个数字,也就是最小值的数字 minHeight := height[i] if height[j] < minHeight { minHeight = height[j] } //获取j与i之间的差距离. distance := j - i //求面积.