算法(四)--二分法，动态规划
2021-12-18 本文已影响0人
PurelightMe
二分法
前提：
- 有序
- 上下界
- 可以通过索引访问
模板：
left,right = 0,len(array)-1
while left <= right:
mid = (left+right)/2
if array[mid] == target:
break or return result
elseif array[mid] < target:
left = mid+1
else:
right = mid-1
剑指 Offer II 072. 求平方根
该题也可以用牛顿迭代法解题
func mySqrt(x int) int {
if x == 0 {
return 0
}
left,right := 0,x
for ;left <= right; {
mid := (left+right)/2 //这里怕整形溢出的话，可以用: mid := left + (right-left)/2
rs := mid*mid
if rs == x {
return mid
}else if(rs < x){
left = mid + 1
}else{
right = mid - 1
}
}
return right
}
//牛顿迭代法
367. 有效的完全平方数
func isPerfectSquare(num int) bool {
left,right := 0,num
for ;left <= right; {
mid := (left+right)/2
if mid*mid == num {
return true
}else if mid*mid < num {
left = mid + 1
}else{
right = mid - 1
}
}
return false
}
33. 搜索旋转排序数组
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := (right - left) / 2 + left
if nums[mid] == target {
return mid
}
if nums[mid] >= nums[left] {
if nums[mid] > target && target >= nums[left] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
74. 搜索二维矩阵
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
if m == 0 {
return false
}
n := len(matrix[0])
for i := 0;i < m;i++ {
if target > matrix[i][n-1] {
continue
}
left,right := 0,n-1
for ;left <= right; {
mid := left + (right-left)/2
if matrix[i][mid] == target {
return true
}
if matrix[i][mid] < target {
left = mid + 1
}else{
right = mid - 1
}
}
}
return false
}
动态规划
动态规划和递归，分治没有本质区别
共性：找到重复子问题
区别：是否有最优解
62. 不同路径
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}
//空间优化版本：
func uniquePaths(m int, n int) int {
cur := make([]int,n)
for i :=0;i<n;i++{
cur[i] = 1
}
for x := 1;x < m;x++ {
for y := 1;y < n;y++ {
cur[y] += cur[y-1]
}
}
return cur[n-1]
}
//排列组合解法：
func uniquePaths(m int, n int) int {
return int(new(big.Int).Binomial(int64(m+n-2), int64(n-1)).Int64())
}
63. 不同路径 II
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
n, m := len(obstacleGrid), len(obstacleGrid[0])
f := make([]int, m)
if obstacleGrid[0][0] == 0 {
f[0] = 1
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if obstacleGrid[i][j] == 1 {
f[j] = 0
continue
}
if j - 1 >= 0 && obstacleGrid[i][j-1] == 0 {
f[j] += f[j-1]
}
}
}
return f[len(f)-1]
}
1143. 最长公共子序列
//DP方程
if s1[-1] != s2[-1]
LCS(s1,s2) = MAX(LCS(s1-1,s2),LCS(s1,s2-1))
if s1[-1] == s2[-1]
LCS[s1,s2] = LCS(s1-1,s2-1) + 1
//代码：
func longestCommonSubsequence(text1, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i, c1 := range text1 {
for j, c2 := range text2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j] + 1
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
}
}
}
return dp[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
120. 三角形最小路径和
func minimumTotal(triangle [][]int) int {
dp := triangle
for i := len(triangle)-2;i >= 0;i-- {
for j := len(triangle[i])-1;j >= 0;j-- {
dp[i][j] += Min(dp[i+1][j],dp[i+1][j+1])
}
}
return dp[0][0]
}
func Min(a,b int) int {
if a > b {
return b
}
return a
}
53. 最大子数组和
//DP方程
f(i) = Max(f(i-1),0) + a[i]
func maxSubArray(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
max := nums[0]
for i := 1;i < len(nums);i++ {
nums[i] = Max(nums[i],nums[i]+nums[i-1])
max = Max(nums[i],max)
}
return max
}
func Max(a,b int) int {
if a > b {
return a
}
return b
}
152. 乘积最大子数组
func maxProduct(nums []int) int {
maxF, minF, ans := nums[0], nums[0], nums[0]
for i := 1; i < len(nums); i++ {
mx, mn := maxF, minF
maxF = Max(mx * nums[i], Max(nums[i], mn * nums[i]))
minF = Min(mn * nums[i], Min(nums[i], mx * nums[i]))
ans = Max(maxF, ans)
}
return ans
}
func Max(a,b int) int {
if a > b {
return a
}
return b
}
func Min(a,b int) int {
if a < b {
return a
}
return b
}
322. 零钱兑换
//DP
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
dp[0] = 0
for j := 1; j <= amount; j++ {
dp[j] = math.MaxInt32
for i := 0; i < len(coins); i++ {
if j >= coins[i] && dp[j-coins[i]] != math.MaxInt32 {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
198. 打家劫舍
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
a := make([][]int,n)
for i,_ := range a {
a[i] = make([]int,2)
}
a[0][0] = 0
a[0][1] = nums[0]
for j := 1;j < n;j++ {
a[j][0] = Max(a[j-1][0],a[j-1][1])
a[j][1] = a[j-1][0] + nums[j]
}
return Max(a[n-1][0],a[n-1][1])
}
func Max(a,b int) int {
if a > b {
return a
}
return b
}
