目录

213. 打家劫舍 II House Robber ii  🌟🌟

214. 最短回文串 Shortest Palindrome  🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

213. 打家劫舍 II House Robber ii

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

  相关题目： 198. 打家劫舍 House Robber

  https://hannyang.blog.csdn.net/article/details/130663466#t1

  代码1： 动态规划

  package main
  import "fmt"
  func rob(nums []int) int {
  	if len(nums) == 1 {
  		return nums[0]
  	}
  	// 不偷第一个房屋
  	prevMax := 0
  	currMax := 0
  	for _, num := range nums[1:] {
  		temp := currMax
  		currMax = max(currMax, prevMax+num)
  		prevMax = temp
  	}
  	maxVal1 := currMax
  	// 不偷最后一个房屋
  	prevMax = 0
  	currMax = 0
  	for _, num := range nums[:len(nums)-1] {
  		temp := currMax
  		currMax = max(currMax, prevMax+num)
  		prevMax = temp
  	}
  	maxVal2 := currMax
  	return max(maxVal1, maxVal2)
  }
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  func main() {
  	nums := []int{2, 3, 2}
  	fmt.Println(rob(nums))
  	nums = []int{1, 2, 3, 1}
  	fmt.Println(rob(nums))
  	nums = []int{1, 2, 3}
  	fmt.Println(rob(nums))
  }
  

  代码2： 动态规划

  package main
  import "fmt"
  func rob(nums []int) int {
      if len(nums) == 1 {
          return nums[0]
      }
      return max(robRange(nums, 0, len(nums)-2), robRange(nums, 1, len(nums)-1))
  }
  func robRange(nums []int, start, end int) int {
      prevMax := 0
      currMax := 0
      for i := start; i <= end; i++ {
          temp := currMax
          currMax = max(currMax, prevMax+nums[i])
          prevMax = temp
      }
      return currMax
  }
  func max(a, b int) int {
      if a > b {
          return a
      }
      return b
  }
  func main() {
  	nums := []int{2, 3, 2}
  	fmt.Println(rob(nums))
  	nums = []int{1, 2, 3, 1}
  	fmt.Println(rob(nums))
  	nums = []int{1, 2, 3}
  	fmt.Println(rob(nums))
  }
  

  代码3： 动态规划

  package main
  import "fmt"
  func rob(nums []int) int {
  	if len(nums) == 1 {
  		return nums[0]
  	} else if len(nums) == 2 {
  		return max(nums[0], nums[1])
  	}
  	return max(robRange(nums[1:]), robRange(nums[:len(nums)-1]))
  }
  func robRange(nums []int) int {
  	prevMax := 0
  	currMax := nums[0]
  	for i := 1; i < len(nums); i++ {
  		temp := currMax
  		currMax = max(currMax, prevMax+nums[i])
  		prevMax = temp
  	}
  	return currMax
  }
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  func main() {
  	nums := []int{2, 3, 2}
  	fmt.Println(rob(nums))
  	nums = []int{1, 2, 3, 1}
  	fmt.Println(rob(nums))
  	nums = []int{1, 2, 3}
  	fmt.Println(rob(nums))
  }
  

  输出：

  3

  4

  3

  动态规划过程

  • 状态：dp[i] 表示偷窃前 i 个房屋的最大金额。

  • 转移方程：dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])

    • 若偷窃第 i 个房屋，则不能偷窃第 i-1 个房屋，所以最大值为 dp[i-2]+nums[i-1]。
    • 若不偷窃第 i 个房屋，则最大值为 dp[i-1]。

  • 初始状态：dp[0] = 0 和 dp[1] = nums[0]，因为只有一个房屋时最大金额为 nums[0]。

  • 最终结果：max(dp[len(nums)],dp[len(nums)-1])

    ---

    214. 最短回文串 Shortest Palindrome

    给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

    示例 1：

    输入：s = "aacecaaa"
    输出："aaacecaaa"
    

    示例 2：

    输入：s = "abcd"
    输出："dcbabcd"
    

    提示：

    • 0 <= s.length <= 5 * 10^4
    • s 仅由小写英文字母组成

      代码1：

      package main
      import "fmt"
      func shortestPalindrome(s string) string {
      	n := len(s)
      	for i := n; i >= 1; i-- {
      		if isPalindrome(s[:i]) {
      			rev := reverse(s[i:])
      			return rev + s
      		}
      	}
      	return s
      }
      func isPalindrome(s string) bool {
      	n := len(s)
      	for i := 0; i < n/2; i++ {
      		if s[i] != s[n-i-1] {
      			return false
      		}
      	}
      	return true
      }
      func reverse(s string) string {
      	n := len(s)
      	b := []byte(s)
      	for i := 0; i < n/2; i++ {
      		b[i], b[n-i-1] = b[n-i-1], b[i]
      	}
      	return string(b)
      }
      func main() {
      	s := "aacecaaa"
      	fmt.Println(shortestPalindrome(s))
      	s = "abcd"
      	fmt.Println(shortestPalindrome(s))
      }
      

      代码2：

      package main
      import "fmt"
      func shortestPalindrome(s string) string {
      	rev := reverse(s)
      	ns := s + "#" + rev
      	n := len(ns)
      	f := make([]int, n)
      	for i, j := 1, 0; i < n; i++ {
      		for j > 0 && ns[i] != ns[j] {
      			j = f[j-1]
      		}
      		if ns[i] == ns[j] {
      			j++
      		}
      		f[i] = j
      	}
      	return rev[:len(s)-f[n-1]] + s
      }
      func reverse(s string) string {
      	n := len(s)
      	b := []byte(s)
      	for i := 0; i < n/2; i++ {
      		b[i], b[n-i-1] = b[n-i-1], b[i]
      	}
      	return string(b)
      }
      func main() {
      	s := "aacecaaa"
      	fmt.Println(shortestPalindrome(s))
      	s = "abcd"
      	fmt.Println(shortestPalindrome(s))
      }
      

      输出：

      aaacecaaa

      dcbabcd

      ---

      🌟 每日一练刷题专栏 🌟

      ✨ 持续，努力奋斗做强刷题搬运工！

      👍 点赞，你的认可是我坚持的动力！ 

      🌟 收藏，你的青睐是我努力的方向！ 

      ✎ 评论，你的意见是我进步的财富！  

      ☸ 主页：https://hannyang.blog.csdn.net/ 

      	Rust每日一练 专栏 （2023.5.16~）更新中...
      	Golang每日一练 专栏 （2023.3.11~）更新中...
      	Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更
      	C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更
      	Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更