邢台123网站模板,广州市工商注册查询系统,免费的wordpress能用吗,珠海自适应网站建设509. 斐波那契数
斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1
F(n) F(n - 1) F(n - 2)#xff0c;其中 …509. 斐波那契数
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。
示例 1
输入n 2
输出1
解释F(2) F(1) F(0) 1 0 1示例 2
输入n 3
输出2
解释F(3) F(2) F(1) 1 1 2示例 3
输入n 4
输出3
解释F(4) F(3) F(2) 2 1 3提示
0 n 30
class Solution {public int fib(int n) {if(n1){return n;}int a0,b1,ans0;for(int i2;in;i){ansab;ab;bans;}return ans;}
}70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1 输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶示例 2 输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示 1 n 45
class Solution {public int climbStairs(int n) {int a1,b2;if(n1)return a;if(n2)return b;int ans0;for(int i3;in;i){ansab;ab;bans;}return ans;}
}就是在一些最优子结构的基础上跳跃。 n3时 有三种爬法 因为一次可以爬一阶或者两阶所以在dp[1]的基础上跳两阶加上dp[2]跳一阶就是两个最优子结构相加。 1 阶 2 阶1 阶 1 阶 1 阶2 阶 1 阶 55. 跳跃游戏
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。提示
1 nums.length 1040 nums[i] 105
class Solution {public boolean canJump(int[] nums) {int maxStep0,lennums.length;for(int i0;ilen;i){if(imaxStep){return false;}maxStepMath.max(maxStep,inums[i]);if(maxSteplen-1){return true;}}return false;}
}遍历数组更新最远距离如果i超过了最远距离说明跳不到 i 索引即跳不到终点。 45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i]i j n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums [2,3,0,1,4]
输出: 2class Solution {public int jump(int[] nums) {int lennums.length;int maxStep0;int end0;int ans0;for(int i0;ilen-1;i){maxStepMath.max(maxStep,inums[i]);if(iend){ans;endmaxStep;}}return ans;}
}338. 比特位计数
给你一个整数 n 对于 0 i n 中的每个 i 计算其二进制表示中 1 的个数 返回一个长度为 n 1 的数组 ans 作为答案。
示例 1
输入n 2
输出[0,1,1]
解释
0 -- 0
1 -- 1
2 -- 10示例 2
输入n 5
输出[0,1,1,2,1,2]
解释
0 -- 0
1 -- 1
2 -- 10
3 -- 11
4 -- 100
5 -- 101class Solution {public int[] countBits(int n) {int[] ansnew int[n1];int temp0;for(int i0;in;i){ans[i]countOnes(i);}return ans;}public int countOnes(int x){int count0;while(x!0){x (x-1);count;}return count;}
}三种计算二进制中1的个数 利用位运算 public static int countOnes(int n) {int count 0;while (n ! 0) {count n 1; // 检查最低位是否为 1n 1; // 无符号右移 1 位}return count;}利用内置方法 public class CountOnes {public static void main(String[] args) {int number 29; // 例如29 的二进制是 11101int count Integer.bitCount(number);System.out.println(1 的个数: count);}
}利用Brian Kernighan 算法 public static int countOnes(int n) {int count 0;while (n ! 0) {n (n - 1); // 将最低位的 1 清零count;}return count;}大佬的解法也不错 198. 打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 1
输入[1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。示例 2
输入[2,7,9,3,1]
输出12
解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。偷窃到的最高金额 2 9 1 12 。解法一
class Solution {public int rob(int[] nums) {int lennums.length;int[] dpnew int[len];if(len0)return 0;if(len1)return nums[0];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(int i2;ilen;i){dp[i]Math.max(dp[i-1],dp[i-2]nums[i]);}return dp[len-1];}
}
解法二
class Solution {public int rob(int[] nums) {if (nums null || nums.length 0) {return 0;}int length nums.length;int first0,second0;for (int i 0; i length; i) {int temp second;second Math.max(first nums[i], second);first temp;}return second;}
}解法二因为每个最优子结构只与连两个房子有关。不需要考虑溢出问题而且可以从0开始遍历且空间复杂度为O(1)。 这个解法对于打家劫舍2有很大的优势。 213. 打家劫舍 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]
输出3class Solution {public int rob(int[] nums) {if(nums.length 0) return 0;if(nums.length 1) return nums[0];return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), myRob(Arrays.copyOfRange(nums, 1, nums.length)));}private int myRob(int[] nums) {int pre 0, cur 0, tmp;for(int num : nums) {tmp cur;cur Math.max(pre num, cur);pre tmp;}return cur;}
}这个解法简单优雅不用考虑溢出问题。 class Solution {public int rob(int[] nums) {int lennums.length;if(len0)return 0;if(len1)return nums[0];return Math.max(myRob(Arrays.copyOfRange(nums,0,len-1)),myRob(Arrays.copyOfRange(nums,1,len)));}public int myRob(int[] nums){int lennums.length;int[] dpnew int[len];if(len0)return 0;if(len1)return nums[0];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(int i2;ilen;i){dp[i]Math.max(dp[i-1],dp[i-2]nums[i]);}return dp[len-1];}
}两个方法考虑溢出因为如果len2的话myRob会出现溢出问题烦死人了如果时OI赛制我已经死了。
