/ * *
198. Robbery
The title
You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night.
Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.
Example 1:
Input: [1,2,3,1] Output: 4 Explanation: Steal House # 1 (amount = 1), then steal House # 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4. Example 2:
Input: [2,7,9,3,1] Output: 12 Explanation: Steal House 1 (amount = 2), House 3 (amount = 9), then House 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.
Tip:
0 <= nums.length <= 100
0 <= nums[i] <= 400
Source: LeetCode link: leetcode-cn.com/problems/ho… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
Print (rob (,2,3,1 [1]))
notes
So this is kind of the classic dynamic programming idea of making sure that each one is the maximum return that you can get at the moment and then figuring out the maximum return that you can get at the moment
Note that adjacency does not mean +2, e.g. [2,1,1,2] is at most 2+2=4
The code address
Github.com/zmfflying/Z… * /
The problem solving code
Import Foundation func rob(_ nums: If count == 0 {return 0} if count == 1 {return nums.last! Var dp: [Int] = nums for I in 2.. <count {var temp = 0 var j = 2 while i-j >= 0 {var j = 0 var j = 2 while i-j >= 0 Nums [I] + dp[i-j]) j += 1} dp[I] = temp} return Max (dp[coun-1], dp[coun-2])} If nums = [2,1], dp[1] = 2 (_ nums: If count == 0 {return 0} if count == 1 {return Var dp: [Int] = [Int]. Init (repeating: 0, count: Dp [1] = Max (nums[0], nums[1]) for I in 2.. dp[1] = Max (nums[0], nums[1]) <count { dp[i] = max(dp[i-1], dp[i-2] + nums[i]) } return dp[count-1] }Copy the code/ * *
337. House robbery III
The title
After robbing a street and a circle of houses, the thieves found a new area to burgle. There is only one entrance to this area, which we call the Root. In addition to the root, each house has one and only one parent house attached to it. After some sleuthing, the clever thief realized that “all the houses in this place are arranged like a binary tree.” If two directly connected houses are robbed on the same night, the house will automatically alarm the police.
Calculate the maximum amount of money a thief could steal in one night without setting off the alarm.
Example 1:
Input: [3, 2, 3, null, 3, null, 1)
3
/ \
2 3
\ \
3 1
Copy the codeExplanation: Maximum amount of money a thief can steal in one night = 3 + 3 + 1 = 7. Example 2:
Input: [3,4,5,1,3, null, 1)
3 / \ 4 5 / \ 1 3 1Copy the codeExplanation: The maximum amount a thief can steal in one night = 4 + 5 = 9.
Source: LeetCode link: leetcode-cn.com/problems/ho… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
let tree5 = TreeNode.init(1, nil, nil)
let tree4 = TreeNode.init(3, nil, nil)
let tree3 = TreeNode.init(3, nil, tree5)
let tree2 = TreeNode.init(2, nil, tree4)
let tree1 = TreeNode.init(3, tree2, tree3)
print(rob(tree1))
notes
There are two core points in this problem: first, backward traversal should be used, so that the root node will be the last node to be traversed, and the maximum value of the root node is the maximum amount of money that can be stolen
Second, this tree, at each node from the bottom up, has two possible amounts: Maximum amount stolen from this node = maximum amount stolen from this node + Maximum amount not stolen from the left child node + Maximum amount not stolen from the right child node Maximum amount not stolen from this node = Maximum amount stolen from the left child node + Maximum amount stolen from the right child node
Just use an array to record and pass in the amount each node can harvest
The code address
Github.com/zmfflying/Z… * /
The problem solving code
import Foundation func rob(_ root: TreeNode?) -> Int { func help(_ root: TreeNode?) -> [Int] {if root = nil {return [0,0]} let money = root! Val // let left: [Int] = help(root? .left) let right: [Int] = help(root? Let noRobCurMoney = Max (left[0], left[1]) + Max (right[0], Right [1]) let robCurMoney = money + left[0] + right[0] return [noRobCurMoney, robCurMoney] } let res = help(root) return max(res[0], res[1]) }Copy the code/ * *
279. Perfect squares
The title
Given a positive integer n, find several perfect squares (e.g. 1, 4, 9, 16…). So that their sum is equal to n. You want to minimize the number of perfect squares that make up the sum.
Given an integer n, return the minimum number of perfect squares that sum to n.
A perfect square is an integer whose value equals the square of another integer; In other words, its value is equal to the product of an integer. For example, 1, 4, 9, and 16 are perfect squares, but 3 and 11 are not.
Example 1:
Input: n = 12 Output: 3 Description: 12 = 4 + 4 + 4 Example 2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9 Hint:
1 <= n <= 104
Source: LeetCode link: leetcode-cn.com/problems/pe… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
print(numSquares(12))
notes
This is actually a dynamic programming idea, from small to large the least perfect square of this number is equal to the least square of that number plus 1
The code address
Github.com/zmfflying/Z… * /
The problem solving code
Import Foundation // MARK: -2.2 Dynamic Programming func numSquares(_ n: Int) -> Int { if n == 1 { return 1 } var arr = Array(repeating: 0, count: n + 1) arr[1] = 1 for i in 2... N {// Record the corresponding value of I. // Temp is initially set to I because 2 = 1 + 1 and 3 = 1 + 1 + 1,,,, Var j = 1 while j*j <= I {arr[i-j *j] is the smallest number of perfect squares of i-j *j Arr [i-j *j] + 1 temp = min(temp, arr[i-j *j] + 1) j += 1} arr[I] = temp} return arr. } // MARK: -1.1 recursion func numSquares1(_ n: Int) -> Int {var arr: [Int] = [Int]. Init (repeating: -1, count: n+1) var nums: [Int] = [Int]() for i in 1... n { let num = i * i if num > n { break } nums.append(num) arr[num] = 1 } func help(_ n: Int) -> Int { if arr[n] ! = -1 { return arr[n] } var minLen = n for num in nums { if n < num { break } minLen = min(minLen, help(n - num) + 1) } arr[n] = minLen return minLen } return help(n) }Copy the code