经典算法题解析

发布时间：2024-12-12 14:40

阅读经典编程书籍，如《算法导论》理解算法原理 #生活知识# #科技生活# #编程学习#

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入： 2 输出： 2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：输入： 3 输出： 3 解释：有三种方法可以爬到楼顶。 3. 1 阶 + 1 阶 + 1 阶 4. 1 阶 + 2 阶 5. 2 阶 + 1 阶

123456789101112131415161718

class Solution { public int climbStairs(int n) { if(n<=2) return n; else { int res = 0; int i = 1,j = 2; int k = 3; while(k<=n){ res = i + j; i = j; j = res; k++; } return res; } } }

1234567891011121314151617

class Solution { public int climbStairs(int n) { int[] dp = new int[n+1]; if(n<=2) return n; else { dp[0] = 0; dp[1] = 1; dp[2] = 2; for(int i=3;i<=n;i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } } } 123456789101112131415

斐波那契数列：设跳n个台阶有f(n)种方法，爬1个：1种爬2个：2种爬n个：面临两种选择：（1）第一次爬1个，此时剩余n-1个台阶，有f(n-1)种方法（2）第一次爬2个，此时剩余n-2个台阶，有f(n-2)种方法所以f(n) = f(n-1) + f(n-2) 12345678

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 12345678

class Solution { public int maxProfit(int[] prices) { if(prices.length <= 1){ return 0; } int min = prices[0],max = 0; for(int i = 1;i < prices.length;i++){ max = Math.max(max,prices[i] - min); min = Math.min(min,prices[i]); } return max; } } 12345678910111213

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 说明:你可以认为每种硬币的数量是无限的。 123456789

比较典型的动态规划问题: 假设 f(n) 代表要凑齐金额为 n 所要用的最少硬币数量，那么有： f(n) = min(f(n - c1), f(n - c2), ... f(n - cn)) + 1 其中 c1 ~ cn 为硬币的所有面额。 1234

在这里插入代码片 1

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 123456

class Solution { public int maxSubArray(int[] nums) { int res = nums[0]; int sum = 0; for(int num:nums){ if(sum>0){ sum += num; } else { sum = num; } res = Math.max(res,sum); } return res; } } //假设sum<=0，那么后面的子序列肯定不包含目前的子序列，所以令sum = num； //如果sum > 0对于后面的子序列是有好处的。res = Math.max(res, sum)保证可以找到最大的子序和。

123456789101112131415161718

class Solution { public int maxSubArray(int[] nums) { int Maxsum=nums[0],sum=0; for (int i = 0; i < nums.length; i++) { sum+=nums[i]; if(sum>Maxsum) Maxsum=sum; if(sum<0) sum=0; } return Maxsum; } } 1234567891011

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。示例 1: 输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。 123456789

class Solution { public int rob(int[] nums) { int n = nums.length; if(n <= 1) return n == 0 ? 0 : nums[0]; int[] dp = new int[n]; dp[0] = nums[0]; dp[1] = Math.max(nums[0],nums[1]); for(int i = 2;i < n;i++){ dp[i] = Math.max(dp[i-1],nums[i]+dp[i-2]); } return dp[n-1]; } } 12345678910111213

class Solution { public int rob(int[] nums) { int res1 = 0,res2=0; for(int i = 0;i<nums.length;i++){ if(i%2==0){ res1 += nums[i]; res1 = Math.max(res2,res1); }else{ res2 += nums[i]; res2 = Math.max(res2,res1); } } return Math.max(res1,res2); } } 123456789101112131415

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。示例：给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange() sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 12345678

class NumArray { private int[] sums; public NumArray(int[] nums) { sums = new int[nums.length]; if(nums.length == 0){ return; } sums[0] = nums[0]; for(int i = 1;i < nums.length; i++){ sums[i] += sums[i-1] + nums[i]; } } public int sumRange(int i, int j) { if (i == 0) { return sums[j]; } else { return sums[j] - sums[i - 1]; } } }

12345678910111213141516171819202122

你知道的越多，你不知道的越多。
有道无术，术尚可求，有术无道，止于术。
如有其它问题，欢迎大家留言，我们一起讨论，一起学习，一起进步

网址：经典算法题解析 https://www.yuejiaxmz.com/news/view/453627

上一篇：须臾APP规划工作生活怎么使用？

下一篇：大学生日常生活安排与规划