前言
T1，T2太简单，不用思考。
T3单调栈蛮有难度
T4如果能想到用图来做就很简单
第一题
6078.重排字符形成目标字符串
6078.重排字符形成目标字符串
题解
题目：给一个字符串s和target，问字符串s中能拼出几个target，用过的字符不能再用
思路：
1.计算s中字符出现的次数，计算target中字符出现的次数 2.遍历target字符，用s中字符出现的次数/target字符出现的次数 3.维护步骤2的最小值
代码
func rearrangeCharacters(s string, target string) int { mp1 := make(map[byte]int) mp2 := make(map[byte]int) for _, v := range s { mp1[byte(v)]++ } for _, v := range target { mp2[byte(v)]++ } ans := len(s) for k2, v2 := range mp2 { v1 := mp1[k2] ans = min(ans, v1/v2) } return ans } func min(a, b int) int { if a > b { return b } return a }
第二题
6079.价格减免
6079.价格减免
题解
题目：给一个空格分隔单词的字符串，和一个discount减免折扣。如果出现$xx，则将该价钱 *（1-discount/100） 保留两位小数，修改原来的字符串
思路：模拟题，很简单。Split函数分隔，然后遍历修改，join合并切片
代码
func discountPrices(sentence string, discount int) string { ss := strings.Split(sentence, " ") for i, v := range ss { if v[0] == '$' { cnt := v[1:] org, err := strconv.ParseFloat(cnt, 64) if err != nil { continue } org *= 1 - float64(discount)/float64(100) news := fmt.Sprintf("$%.2f", org) ss[i] = news } } return strings.Join(ss, " ") }
第三题
6080.使数组按非递减顺序排列
6080.使数组按非递减顺序排列
题解
题目：给一个数组，如果nums[i-1]>nums[i]，则移除nums[i]，问需要几轮才能将数组变成非递减数组（1轮可以移除多个元素）
思路：
1.题目要求数组变成非递减，就是递增，那么肯定与单调栈有关 2.6 3 2 1 4，则需要2轮，3 2 1在第一轮就被删了 3.维护一个单调递减栈，栈里存储元素和被删时间 4.遇到一个不小于栈顶元素的v时，就不断弹出栈顶，并维护弹出元素被删时间的最大值 5.如果len(栈)>1，说明变成了[6 4 ]，此时将最大值加一，入栈 [5,3,4,4,7,3,6,11,8,5,11] [{5 0}] [{5 0} {3 1}] [{5 0} {4 2}] [{5 0} {4 3}] [{7 3}] [{7 3} {3 1}] [{7 3} {6 2}] [{11 3}] [{11 3} {8 1}] [{11 3} {8 1} {5 1}] [{11 3}]
代码
func totalSteps(nums []int) int { type pair struct { val, step int } st := make([]pair, 0) ans := 0 for _, v := range nums { maxStep := 0 for len(st) > 0 && st[len(st)-1].val <= v { maxStep = max(maxStep, st[len(st)-1].step) st = st[:len(st)-1] } if len(st) > 0 { maxStep++ } ans = max(ans, maxStep) st = append(st, pair{v, maxStep}) } return ans } func max(i, j int) int { if i > j { return i } return j }
第四题
6081.到达角落需要移除障碍物的最小数目
6081.到达角落需要移除障碍物的最小数目
题解
题目：给你一个二维数组，其中0表示获得0分，1表示获得1分，求从左上走到右下的最小分数
思路：本来用dfs+回溯写，结果超时。spfa—>O(mn)
1.观察题目，从坐上走到右下，有些地方0分，有些1分 2.其实题目可以转换成图来做 3.用BFS，O(mn)即可，不会超 4.因为二维数组+上下左右就是边了，边其实已经天然的存在了 5.所以开一个二维数组，记录0,0到x,y的距离即可 6.注意：初始化距离要大一点，graph[0][0] = 0 7.缩小条件graph[nx][ny] = graph[x][y] + grid[nx][ny]
代码
func minimumObstacles(grid [][]int) int { dirs := [][2]int{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} type point struct { x, y int } m, n := len(grid), len(grid[0]) graph := make([][]int, m) for i := range graph { graph[i] = make([]int, n) for j := range graph[i] { graph[i][j] = m + n } } graph[0][0] = 0 p := point{0, 0} queue := []point{p} vis := map[point]bool{p: true} for len(queue) > 0 { x, y := queue[0].x, queue[0].y vis[queue[0]] = false queue = queue[1:] for _, v := range dirs { nx, ny := x+v[0], y+v[1] p := point{nx, ny} if nx >= 0 && nx < m && ny >= 0 && ny < n { if graph[nx][ny] > graph[x][y]+grid[nx][ny] { graph[nx][ny] = graph[x][y] + grid[nx][ny] if !vis[p] { vis[p] = true queue = append(queue, p) } } } } } return graph[m-1][n-1] }
