爬楼梯 问题陈述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ **注意：**给定 n 是一个正整数。 思路分析 可考虑动态规划进行解决，每次只能爬一阶或两阶，也就是当前位置只能由前一个位置或前两个位置得到，于是列出转移方程dp[i]=dp[i-1]+dp[i-2]，即两种情况加和。继续判断起始情况，当台阶数为0，定义可能爬楼梯的情况为1，只有只有后面计算才符合转移方程；当台阶数为1，可能爬楼梯的情况为1。最后爬完楼梯，可能的情况就是dp[n]。 代码实现 12345678910111213class Solution{ public int climbStairs(int n){ if(n<=1) return 1; int[] dp=new int[n+1]; dp[0]=1; dp[1]=1; for(int i=2;i<=n;i++){ dp[i]=(dp[i ...

单词搜索 问题陈述 给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例： 12345678910board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]给定 word = "ABCCED", 返回 true给定 word = "SEE", 返回 true给定 word = "ABCB", 返回 false 代码实现 DFS 123456789101112131415161718192021222324252627282930313233343536373 ...

不同路径 问题陈述 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 思路分析 分析题意可知，机器人只能往下或右移动，也就是说当前格等于其左与其上的和。 转换为起点到终点的路径的话，则很明显，第一行和第一列的格子值都为1，也就是到达该格的路径只有一条，从左边来或从上边来。而对于中间的格子，可从左或上，格子值也就是可能的路径数等于左边加上边之和。 问题求解 代码一： 12345678910111213class Solution{ public int uniquePaths(int m,int n){ int[][] mn=new int[m][n]; for(int i=0;i<n;i++) mn[0][i]=1; for(int j=0;j<m;j++) mn[j][0]=1; for(int i=0;i<m ...

最大子序和 问题陈述 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例： 123输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 思路分析 如何判断最大呢？可定义一个sum=0，result=nums[0]。遍历数组元素，如果sum<=0，则表明对最大无益，直接跳到sum=nums[i]；若sum>0，说明对最大有益，则sum+=nums[i]；如何每轮循环取最大值result=max(sum，result)。 代码实现 1234567891011121314class Solution{ public int getMaxValue(int[] nums){ int sum=0,res=nums[0]; for(int c:nums){ if(sum<=0){ sum=c; & ...

跳跃游戏 问题陈述 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例： 123输入: [2,3,1,1,4]输出: true解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 思路分析 贪心思路 设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums[x]，这个值大于等于 y，即x+nums[x]≥y，那么位置 y 也可以到达。 换句话说，对于每一个可以到达的位置 x，它使得 x+1,x+2,⋯,x+nums[x] 这些连续的位置都可以到达。 这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用x+nums[x] 更新 最远可以到达的位置。 在遍历的过程中，如果 最远可以到达的位置 大 ...

合并区间 问题陈述 给出一个区间的集合，请合并所有重叠的区间。 示例： 123输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 代码实现 123456789101112131415161718class Solution{ public int[][] merge(int[][] intervals){ //先按区间起始数排序 Arrays.sort(intervals,(v1,v2)->v1[0]-v2[0]); int[][] res=new int[intervals.length][2]; int idx=-1; for(int[] c:intervals){ if(idx==-1||c[0]>res[idx][1]){ res[++idx]=c; ...

加一 问题陈述 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 代码实现 123456789101112class Solution{ public int[] plusOne(int[] nums){ for(int i=nums.length-1;i>=0;i--){//从尾部开始，判断每位是否进位 nums[i]++; nums[i]=nums[i]%10; if(nums[i]!=0) return nums;//若无进位，直接返回尾数+1后的结果，否则把进位加到前一位（nums[i]++)。 } nums=new int[nums.length+1];//直到遍历完还没有返回值的话，说明第一位还存在进位，需要扩充数组长度，并且第一位为1. nums[0]=1; ...

字母异位词分组 问题陈述 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 示例： 1234567输入: ["eat", "tea", "tan", "ate", "nat", "bat"]输出:[ ["ate","eat","tea"], ["nat","tan"], ["bat"]] 思路分析 可以考虑使用HashMap来实现。键为字母异位词的排序结果，值为可能出现的各种组合。 代码实现 123456789101112131415161718192021public List<List<String>> groupAnagrams(String[] strs) { HashMap<String, List<String>> hash ...

接雨水 问题陈述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 如图，可接下6个单位的雨水。 思路分析 利用单调栈，单调栈就是永远保证栈内元素单调递增或递减。 代码实现 1234567891011121314151617181920212223242526272829class Solution{ public int trap(int[] height){ if(height==null){ return 0; } Stack<Integer> stack=new Stack<>(); int ans=0; for(int i=0;i<height.length;i++){ //当栈不空，判断当前指向height[i]是否大于上一个已入栈元素的高 while(!stack.isEmpty()&& ...

全排列 问题陈述 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 1234567891011121314示例：输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 思路分析 回溯 代码实现 123456789101112131415161718192021222324252627class Solution{ public List<List<Integer>> permute(int[] nums){ int len=nums.length; List<Integer> path=new ArrayList<>(); List<List<Integer>> res=new ArrayList<>(); boolean[] visited=new boolean[len]; if(len==0 ...