Loading... ## 练习 #### 题目1： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 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 。 提示： 0 <= nums.length <= 100 0 <= nums[i] <= 400 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber 题解： ```java class Solution { public int rob(int[] nums) { // 最后一步 要么偷最后一家要么倒数第二家 // 子问题 // 偷最后一家：f[x-1]=max(f[x-2],f[x-3]) // 偷倒数第二家：f[x-1]=max(f[x-3],f[x-4]) // 金额只与当前房屋和前一间有关 // // v1 // int length = nums.length; // int[] f=new int[length]; // int res=Integer.MIN_VALUE; // if(length<=0){ // return 0; // }else { // if(length<=1){ // return nums[0];//长度为 1 时返回第一家 // } // f[0]=nums[0]; // f[1]=Math.max(nums[0],nums[1]);// 两家时，二选一 // res = Math.max(f[0],f[1]); // } // if(length>2){ // f[2]=nums[0]+nums[2]; // res = Math.max(f[2],res);// 三家时 // } // for(int i=3;i<length;i++){ // f[i] = Math.max(f[i-2],f[i-3]);//偷前面第2家 和 前面第3家 // f[i] += nums[i]; // res = Math.max(f[i],res); // } // return res; // v2 空间优化 if(nums==null||nums.length<=0){ return 0; } int length = nums.length; if(length==1){ return nums[0]; } int first = nums[0]; int second = Math.max(first,nums[1]); for(int i=2;i<length;i++){ int tmp = second; second = Math.max(first+nums[i],second); first = tmp; } return second; } } ``` #### 题目2： 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 示例 1: 输入: 2 输出: [0,1,1] 示例 2: 输入: 5 输出: [0,1,1,2,1,2] 进阶: 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？ 要求算法的空间复杂度为O(n)。 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/counting-bits 题解：  ```java public class Solution { public int[] countBits(int num) { int[] ans = new int[num + 1]; for (int i = 1; i <= num; ++i) ans[i] = ans[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1 return ans; } } ``` #### 题目3： 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。  示例 1： 输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。 示例 2： 输入：grid = [[1,2,3],[4,5,6]] 输出：12 提示： m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 100 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-path-sum 题解： ```java class Solution { public int minPathSum(int[][] grid) { // 最后一步 // f[m][n] = max(f[m-1][n],f[m][n-1]) // 边界 m=0 or n=0 ,f[0][0]=grid[0][0] // int x_length=grid.length; // int y_length=grid[0].length; // int[][] f = new int[x_length][y_length]; // f[0][0]=grid[0][0]; // for(int x=0;x<x_length;x++){ // for(int y=0;y<y_length;y++){ // if(x==0&&y==0){ // continue; // } // if(x==0){ // f[x][y]=f[x][y-1]+grid[x][y]; // }else if(y==0){ // f[x][y]=f[x-1][y]+grid[x][y]; // }else{ // f[x][y]=Math.min(f[x-1][y],f[x][y-1])+grid[x][y]; // } // } // } // return f[x_length-1][y_length-1]; // v2 空间优化 int x_length=grid.length; int y_length=grid[0].length; // int[][] f = new int[x_length][y_length]; // f[0][0]=grid[0][0]; for(int x=0;x<x_length;x++){ for(int y=0;y<y_length;y++){ if(x==0&&y==0){ continue; } if(x==0){ grid[x][y]=grid[x][y-1]+grid[x][y]; }else if(y==0){ grid[x][y]=grid[x-1][y]+grid[x][y]; }else{ grid[x][y]=Math.min(grid[x-1][y],grid[x][y-1])+grid[x][y]; } } } return grid[x_length-1][y_length-1]; } } ``` Last modification：December 14th, 2020 at 04:57 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
tql,sdl,ddw,wsl