2024-04-15 22:38 东北大学 golang
关注
虾皮笔试4.15
关于买英雄的那道笔试题，我的代码如下
func solution(costs []int, coins int) []int {
var temp []int
temp = append(temp, costs...)
sort.Slice(temp, func(i, j int) bool { return temp[i] < temp[j] })
var index []int
var ans []int
var hash map[int]int
hash = make(map[int]int)
for k, v := range costs {
hash[v] = k
}
for _, v := range temp {
if v <= coins {
index = append(index, hash[v]) //保存下标
coins = coins - v
}
}
sort.Slice(index, func(i, j int) bool { return index[i] < index[j] })
for i := 0; i < len(index); i++ {
ans = append(ans, costs[index[i]])
}
return ans
}
主要思路就是，根据题意肯定是买最便宜的，这里用的是按照升序排序，然后比较从小的比较coin，因为这里需要按照原来的顺序输出，用了hash来存储值与下标的对应关系，最后将下标进行排序，按照顺序写入切片中就是题解，但是卡52%，不知道是超时问题还是有其他的情况没有考虑到，请各位大佬指教
func solution(costs []int, coins int) []int {
var temp []int
temp = append(temp, costs...)
sort.Slice(temp, func(i, j int) bool { return temp[i] < temp[j] })
var index []int
var ans []int
var hash map[int]int
hash = make(map[int]int)
for k, v := range costs {
hash[v] = k
}
for _, v := range temp {
if v <= coins {
index = append(index, hash[v]) //保存下标
coins = coins - v
}
}
sort.Slice(index, func(i, j int) bool { return index[i] < index[j] })
for i := 0; i < len(index); i++ {
ans = append(ans, costs[index[i]])
}
return ans
}
主要思路就是，根据题意肯定是买最便宜的，这里用的是按照升序排序，然后比较从小的比较coin，因为这里需要按照原来的顺序输出，用了hash来存储值与下标的对应关系，最后将下标进行排序，按照顺序写入切片中就是题解，但是卡52%，不知道是超时问题还是有其他的情况没有考虑到，请各位大佬指教
全部评论
牛客515756430号
门头沟学院 Java
我觉得应该是这种情况，输入[2，1，3，5，4]，coins=11的时候，用贪心的结果是2 1 3 4，但是人家要的答案可能是2 1 3 5😂
相关推荐
查看11道真题和解析 03-17 13:56
湖南大学 Java 点赞 评论 收藏
分享
