一些算法举例
分糖果
LeetCode 455，有孩子序列和糖果序列，每个孩子需求一定数量的糖果，如果他得到了满足，则满足他的糖果会被消耗。求最多能满足的孩子数量。
- 示例
孩子序列：[3,10,10,6,16,11] 糖果序列：[9,4,2,7,21] 最大能满足孩子的数量：3 - 思路
首先将孩子和糖果都排好序，从小到大，然后用最小的糖果堆依次去尝试满足孩子序列，如果满足则消耗孩子当前节点和当前糖果堆，依次去尝试下一个孩子和糖果堆；如果当前糖果堆不能满足当前孩子，则尝试下一个糖果堆。
由于已经排好序，如果当前糖果堆不能满足当前孩子，则它一定不能满足后续孩子
- 实现
func allocationCandies(children: inout [Int], candies: inout [Int]) {
var count=0
quickSort(src: &children, left: 0, right: children.count-1)
quickSort(src: &candies, left: 0, right: candies.count-1)
var i=0,j=0
while i<children.count && j<candies.count {
if candies[j]<children[i] {
j+=1
} else {
count+=1
i+=1
j+=1
}
}
print("allocationCandies: \(count) children can be satisfied")
}
- 结果
var children=[3,10,10,6,16,11], candies=[9,4,2,7,21]
allocationCandies(children: &children, candies: &candies)
oallocationCandies: 3 children can be satisfied