Let's go to play Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) Total Submission(s) : 773 Accepted Submission(s) : 213 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description Mr.Lin would like to hold a party and invite his friends to this party. He has n friends and each of them can come in a sp...阅读全文
Golang: 前言：这题我为了省时间空间，用了递归和map，但是没想到，还不如别人直接数组来的快，不想优化了，下次会直接用上数组。代码不推荐使用，就这样。 思路：这题是不能用贪心的，因为贪心的思路不能证明可以解这题。是的，如果确定要求最优解，除非能证明贪心可行，不然不推荐使用贪心。这题举个例子，有1元、5元，11元，f(n)表示换n元零钱需要的最小硬币数量，贪心的思路是，如果n>11，应该先用最大的，但在这个例子里，15元=11元+1元*4，贪心需要五个硬币，实际上呢，15=5元*3。动态规划的思路呢，就是f(15)=min(f(14)，f(10)，f(4))+1，注意为什么是14，10，4。因为14=15-1，10=15-5，4=15-11。 代码如下： func coinChange(...阅读全文
```go package main import ( "fmt" ) const MAX_SIZE int = 5 const MAX_VALUE int = 9999 func main() { fmt.Println("Dijkstra") var gg Graph var vexs = []string{"A", "B", "C", "D", "E"} gg.vexnum = 5 gg.vexs = vexs initGG(&gg, vexs) PrintG(gg, 5) Dijkstra(&gg, 1) } type Graph struct { vexs []string /...阅读全文
Golang: 思路：还是照抄我的题解。 这题题意很明显是贪心了，那么以什么作为尺度呢？ 毫无疑问的，应该是一个人去A点和去B点的花费之差 简单来说，我们看[1,1000]，那么这个人应该去A点，因为会便宜999元 再来看[10,20],[1,1000],那么第二个人应该去A点，第一个人去B点。因为第一个人去A去B最多便宜10元，第二个人去A去B则可能便宜999元，这就是贪心在这一题的尺度了。 代码如下： type intS [][]int func (s intS) Len() int { return len(s) } func (s intS) Less(i, j int) bool { return s[i][2] > s[j][2] } func (s intS) Swap(i, ...阅读全文
Golang: 思路：贪心加跳跃 代码如下： func canPlaceFlowers(flowerbed []int, n int) bool { if n==0{ return true } pt1:=0 for pt1
Golang: 思路：注意这里并不可以把所有钱都收上来然后依次找掉，所以必须要一个人一个人的解决。这里用了一点贪心，即在处理20美元上，优先选择10+5的处理方法，其次是5+5+5。 闲话：写完这题我的简单题就完成了170道了，后面会转去挑一些中等题做。 代码如下： func lemonadeChange(bills []int) bool { if len(bills)==0{ return true } m5,m10:=0,0 for i:=0;i
Golang: 思路：这题贪心解法其实很好想，不过我最终实现了O(n)的时间复杂度解法，执行效果上在时间复杂度上超过100%。 代码如下： func partitionLabels(S string) []int { var res []int arr:=make([][]int,26) used:=make([]int,26) for i:=0;i
Golang: 思路：贪心，首先，我们需要知道每个数字在数组中出现的数目，然后将这些数目做个排序，每次都删去出现最多次数的数目，直到这些删除的数目之和超过了数组长度的一半。 代码如下： func minSetSize(arr []int) int { mp:=make(map[int]int) for _,v:=range arr{ mp[v]++ } var val []int for _,v:=range mp{ val=append(val,v) } sort.Ints(val) temp:=0 for i:=len(val)-1;i>=0;i--{ temp+=val[i] if temp>=len(arr)/2{ return len(val)-i } } return 0 ...阅读全文
Golang: 思路：这题依旧是贪心解法，还是很简单。。。 代码如下： func minAddToMakeValid(S string) int { res,state:=0,0 for i:=0;i
