贪心和动态规划Golang

贪心和动态规划

• 共同点：取最优子结构的解，一步一步解决问题

• 不同点：贪心取局部最优作为全局最优，动态规划递推全局最优

• 深层区别：贪心是动态规划在最优子结构评价纬度单一（评价条件单一时）的一种特殊解法

  动态规划：典型应用——背包问题

  贪心适用模板：
  //评价最优条件是什么?
  //循环->未解决的问题&&还有解
  //从可能的解中取最优解
  //执行最优解
  //缩小问题规模->双指针，for循环、减去最优解…

案例：
1.按饥饿度分配饼干，使得不挨饿的人数最多。评价条件：不挨饿

func divideCake(cake, children []int) int {
	// 优先满足饥饿度小的
	sort.Ints(cake)
	sort.Ints(children)
	i, j := 0, 0 //
	for i < len(children) && j < len(cake) {
		if children[i] > cake[j] {
			j++
		} else {
			i++
			j++
		}
	}
	// satisfy 能吃饱的孩子数量 就是 i的值
	return i
}

func main() {
	children := []int{2, 1, 4, 5} //孩子们的饥饿度
	cake := []int{1, 3, 5}        //饼干大小
	fmt.Println("satisfyNum=", divideCake(cake, children))

}

---

2. 一个 二维切片，切片元素为区间，问去掉多少个元素，使得二维切片中的元素区间不重合
   评价条件：二维切片中的元素区间的左端，比前一个元素的右端小，则该元素需要剔除（局部最优），依次递推解决问题

// 移除几个数组，使得 得到的数组区间不重合且最大

type ArrNum [][]int

func (an ArrNum) Len() int {
	return len(an)
}
func (an ArrNum) Less(i, j int) bool {
	return an[i][1] < an[j][1]
}
func (an ArrNum) Swap(i, j int) {
	an[i], an[j] = an[j], an[i]
}

func eraseOverlapIntervals(intervals ArrNum) int {
	//按照区间结尾大小 升序排序
	sort.Sort(intervals)
	fmt.Println("intervals sort:", intervals)

	count := 0          //不满足区间的个数
	pre := intervals[0] //第一个区间默认满足
	// 遍历
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] < pre[1] {
			count++
		} else {
			pre = intervals[i]
		}
	}
	return count

}
func main() {
	// GuessingGame()
	intervals := make(ArrNum, 3)
	intervals[0] = []int{1, 2}
	intervals[1] = []int{2, 4}
	intervals[2] = []int{1, 3}

	fmt.Printf("移除%d个区间，区间不重复\n", eraseOverlapIntervals(intervals))
}

---

切片元素表示第i天股票的价格，买卖股票（一天内只能买卖一次操作）

// 切片元素表示第i天股票的价格，买卖股票
// 贪心思想：当天买入第二天能赚钱就卖出

func maxProfit(PriceSlice []int) int {
	profit := 0
	for i := 0; i < len(PriceSlice)-1; i++ {
		if PriceSlice[i] < PriceSlice[i+1] {
			profit += (PriceSlice[i+1] - PriceSlice[i])
			i++
		}
	}
	return profit
}

func main() {
	PriceSlice := []int{7, 1, 5, 3, 6, 4}
	fmt.Println("maxProfit=", maxProfit(PriceSlice))
}

---

LeeCode

1.救生艇问题（LeeCode 881）

func numRescueBoats(people []int, limit int) int {
    //评价条件为两人载重量不超过limit
    // 故可以可以使用贪心
    // 先将people数组 升序排序
    sort.Ints(people)
    //首尾指针，最重和最轻的在一条船，实现所需最小船
    l,r:=0,len(people)-1
    minNum:=0
    for l<=r{
        if people[l]+people[r]<=limit{
            l++
        }
        r--
        minNum++
    }
    return minNum
}

2. 最大容器面积（LeeCode 10）
   给定一个长度为n的数组，其元素表示为第i条垂线的高度·height·
   找出两条线，使得面积最大

func maxArea(height []int) int {

	// 使用双指针的方法
	l, r := 0, len(height)-1
	res := 0
	for l < r {
		area := min(height[l], height[r]) * (r - l)
		res = max(res, area)
		if height[l] < height[r] {
			l++
		} else {
			r--
		}

	}
	return res

}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}
func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

3. 分糖果问题（LeeCode 135）
   n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
   你需要按照以下要求，给这些孩子分发糖果：
   每个孩子至少分配到 1 个糖果。
   相邻两个孩子评分更高的孩子会获得更多的糖果。
   请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

方法1：双遍历

func candy(ratings []int) (ans int) {
	n := len(ratings)
	left := make([]int, n)
	for i, r := range ratings {
		if i > 0 && r > ratings[i-1] {
			left[i] = left[i-1] + 1
		} else {
			left[i] = 1
		}
	}
	right := 0
	for i := n - 1; i >= 0; i-- {
		if i < n-1 && ratings[i] > ratings[i+1] {
			right++
		} else {
			right = 1
		}
		ans += max(left[i], right)
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

方法2：常数空间遍历

func candy(ratings []int) int {
    n:=len(ratings)
    res:=0
    leftReular:=make([]int,n)
    // 左规:ratings[i]>ratings[i-1] 则i 多分配
    for i,v:=range ratings{ //左规则遍历
        if i>0 && v>ratings[i-1]{
           leftReular[i] = leftReular[i-1]+1
        }else{
            leftReular[i] = 1
        }
    }

    // 右规:ratings[i]>ratings[i+1] 则i多分配
    right:=0 
    for i:=n-1;i>=0;i--{
        if i<n-1&& ratings[i]>ratings[i+1]{
            right++
        }else{
            right = 1
        }

        // 最终结果此时就可以逐步获得
        res +=  max(leftReular[i],right)
    }
    return res

}

func max (a,b int) int{
    if a >b {
        return a
    }
    return b
}

---

4. 跳空格问题：
   // 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
   // 数组中的每个元素代表你在该位置可以跳跃的最大长度。
   // 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
   // 假设你总是可以到达数组的最后一个位置。

方法一：
可以记录每次的跳跃点：

func jump(nums []int) int {
	res := 0
	maxStep := 0   //最大跳跃步数后的下标
	nextindex := 0 //跳跃后的下标
	if len(nums) < 2 {
		return 0
	}
	for i := 0; i < len(nums)-1; {
		res++

		if maxStep >= len(nums)-1 {
			break
		}

		a := nums[i]
		for j := 0; j < a && i < len(nums)-1; j++ {
			i++
			if i == len(nums)-1 {
				nextindex = i
				break
			}
			Step := nums[i]

			maxStep = max(maxStep, Step+i)
			if maxStep == Step+i {
				nextindex = i
			}

		}
		i = nextindex
	}
	return res

}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

方法2：反向查找，最后点为终点，倒序依次找到跳跃点(O(n^2))

func jump(nums []int) int {
	position := len(nums) - 1
	steps := 0
	for position > 0 {
		for i := 0; i < position; i++ {
			if i+nums[i] >= position {
				position = i
				steps++
				break
			}
		}
	}
	return steps
}

方法三：
正向查找：

func jump(nums []int) int {
    length := len(nums) //
    end := 0 //每次跳跃后的 最大跳跃点的位置
    maxPosition := 0
    steps := 0
    for i := 0; i < length - 1; i++ {
        maxPosition = max(maxPosition, i + nums[i])
        if i == end { //到达跳跃点的终端后开始 新的跳跃 新的终端为当前最大位置点
            end = maxPosition
            steps++
        }
    }
    return steps
}
func max(a,b int) int{
    if a>b {
        return a
    }
    return b    
}

5. 加油站（LeeCode 134）
   能否完成绕圈

只要加油量大于消耗量即有解

func canCompleteCircuit(gas []int, cost []int) int {
	Sumgas, Sumcost := 0, 0
	for _, v := range gas {
		Sumgas += v
	}
	for _, v := range cost {
		Sumcost += v
	}
	if Sumcost > Sumgas {
		return -1
	}
	// 其余都会有解
	start := 0
	Sum := 0
	n := len(gas)
	for i := 0; i < n; i++ {
		Sum += gas[i] - cost[i]
		if Sum < 0 { //从到 不到的点开始循环
			Sum = 0
			start = i + 1
		}
	}
	return start

}

// 官方方法：

func canCompleteCircuit(gas []int, cost []int) int {
    for i, n := 0, len(gas); i < n; {
        sumOfGas, sumOfCost, cnt := 0, 0, 0
        for cnt < n {
            j := (i + cnt) % n
            sumOfGas += gas[j]
            sumOfCost += cost[j]
            if sumOfCost > sumOfGas {
                break
            }
            cnt++
        }
        if cnt == n {
            return i
        } else {
            i += cnt + 1
        }
    }
    return -1
}