力扣每日四题
- 202. 快乐数-简单
- 20. 有效的括号-简单
- 1706. 球会落何处-中等
- 931. 下降路径最小和-中等
- 总结
202. 快乐数-简单
题目描述:
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ;不是,则返回 false 。
题解:
这个是我刚开始刷力扣没做出来的题,现在看来其实很简单,快慢双指针或者哈希表都可以,当时代码还不熟练
代码(Go):
func isHappy(n int) bool {slow, fast := n, step(n)for fast != 1 && slow != fast {slow = step(slow)fast = step(step(fast))}return fast == 1
}func step(n int) int {sum := 0for n > 0 {sum += (n%10) * (n%10)n = n/10}return sum
}
20. 有效的括号-简单
题目描述:
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
题解:
一样是一开始没做出来的题,因为当时map和切片都不熟练,虽然知道是用栈匹配但是不知道怎么实现
代码(Go):
func isValid(s string) bool {n := len(s)if n % 2 == 1 {return false}dict := map[byte]byte{')': '(',']': '[','}': '{',}stack := []byte{}for i := 0; i < n; i++ {if dict[s[i]] > 0 {if len(stack) == 0 || stack[len(stack)-1] != dict[s[i]] {return false}stack = stack[:len(stack)-1]}else{stack = append(stack, s[i])}}return len(stack) == 0
}
1706. 球会落何处-中等
题目描述:
用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将球导向左侧或者右侧。
将球导向右侧的挡板跨过左上角和右下角,在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角,在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 “V” 形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。
返回一个大小为 n 的数组 answer ,其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标,如果球卡在盒子里,则返回 -1 。
题解:
模拟,如果板子是1则右边板子必须也是1,如果板子是-1则左边板子也必须是-1,如果满足条件则下落,如果是1就向右下落否则向左下落。不知道这题为啥会放在动态规划专栏里,官方题解也没有用动态规划,一样是模拟
代码(Go):
func findBall(grid [][]int) []int {re := make([]int,len(grid[0]))for i := 0;i < len(grid[0]);i++{temp := 0j := ifor {if temp == len(grid){re[i] = jbreak}if j == 0 && grid[temp][j] == -1{re[i] = -1break}else if j == len(grid[0]) - 1 && grid[temp][j] == 1{re[i] = -1break}else if grid[temp][j] == 1 && grid[temp][j + 1] == -1{re[i] = -1break}else if grid[temp][j] == -1 && grid[temp][j - 1] == 1{re[i] = -1break}else if grid[temp][j] == 1 && grid[temp][j + 1] == 1{temp++j++}else{temp++j--}}}return re
}
931. 下降路径最小和-中等
题目描述:
给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
题解:
这个题和前不久做过的一个题很类似,每一个元素都从它上面的三个或两个元素中选择最小的加在自己身上得到到该元素的最小路径,最后只需要在矩阵的最后一行找到最小值即可
代码(Go):
func minFallingPathSum(matrix [][]int) int {for i := 1;i < len(matrix);i++{for j := 0;j < len(matrix[0]);j++{if j == 0{matrix[i][j] += min(matrix[i - 1][j],matrix[i - 1][j + 1])}else if j == len(matrix[0]) - 1{matrix[i][j] += min(matrix[i - 1][j],matrix[i - 1][j - 1])}else{matrix[i][j] += min(matrix[i - 1][j],min(matrix[i - 1][j - 1],matrix[i - 1][j + 1]))}}}re := matrix[len(matrix) - 1][0]for k := 0;k < len(matrix[0]);k++{if matrix[len(matrix) - 1][k] < re{re = matrix[len(matrix) - 1][k]}}return re
}func min(x int,y int) int {if x < y{return x}else{return y}
}
总结
动态规划好难啊啊啊,很多不会的题看别人题解都要看半天才能看懂