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^4s仅由小写英文字母组成
代码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
