題目
給你一個整數 n 。按下述規則生成一個長度為 n + 1 的數組 nums :
- nums[0] = 0
- nums[1] = 1
- 當 2 <= 2 * i <= n 時,nums[2 * i] = nums[i]
- 當 2 <= 2 * i + 1 <= n 時,nums[2 * i + 1] = nums[i] + nums[i + 1]
傳回生成數組 nums 中的 最大 值。
示例1:
輸入:n = 7
輸出:3
解釋:根據規則:
nums[0] = 0
nums[1] = 1
nums[(1 * 2) = 2] = nums[1] = 1
nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
nums[(2 * 2) = 4] = nums[2] = 1
nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
nums[(3 * 2) = 6] = nums[3] = 2
nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
是以,nums = [0,1,1,2,1,3,2,3],最大值 3
示例2:
輸入:n = 2
輸出:1
解釋:根據規則,nums[0]、nums[1] 和 nums[2]
示例3:
輸入:n = 3
輸出:2
解釋:根據規則,nums[0]、nums[1]、nums[2] 和 nums[3]
解題思路
根據題意,我們可以推斷出如下的規則:
- 當 i 為奇數時,nums[i] = nums[i/2] + nums[i/2+1];
- 當 i 為偶數時,nums[i] = nums[i/2];
倆者都有 nums[i/2],于是我們可以将上述倆種情況合并為:
nums[i] = nums[i/2] + (i%2)*nums[i/2+1],當 i 為偶數時,i%2 就為0,奇數時 i%2 則為 1。
代碼實作
class Solution {
public int getMaximumGenerated(int {
if (n == 0) {
return 0;
}
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
int max = 1;
for (int i = 2; i <= n; i++) {
nums[i] = nums[i/2] + (i%2)*nums[i/2 + 1];
if (nums[i] > max) {
max = nums[i];
}
}
return
最後
- 關注公衆号---HelloWorld傑少