xiaolei565

70. 爬楼梯(简单)假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。 示例 1：输入： 2输出：2解释： 有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2：输入： 3输出： 3解释： 有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/climbing-stairs 思路：这里用回溯其实是可以的，但是很明显可以看到动态规划的影子，每一阶的台阶的走法，都等于前面一个台阶的走法和再往前面一个的走法，f(n)=f(n-1)+f(n-2),也就是变相的斐波那契数列，不对，其实就是fib问题 回看记录200518递归用公式，要判断0和1，直接求得话就是dp，f3=f1+f2，f1=f2，f2=f3，要从i=2开始 回看记录200622也是要考虑大数，和leetcode中不是很一致 代码：123456789101112131 ...

66. 加一(简单)给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 示例 1:输入: [1,2,3]输出: [1,2,4]解释: 输入数组表示数字 123。 示例 2:输入: [4,3,2,1]输出: [4,3,2,2]解释: 输入数组表示数字 4321。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/plus-one 思路：这里需要判断的就是进位，有个特殊点，就是每一位都需要进位如999，那么后面补0，前面第一位变成1即可，将数组变长1位 代码：12345678910111213141516171819202122class Solution {public: vector<int> plusOne(vector<int>& digits) { for (int i = digits.size()-1; i >=0 ...

65. 有效数字/面试题20. 表示数值的字符串(困难)验证给定的字符串是否可以解释为十进制数字。 例如: "0" => true" 0.1 " => true"abc" => false"1 a" => false"2e10" => true" -90e3 " => true" 1e" => false"e3" => false" 6e-1" => true" 99e2.5 " => false"53.5e93" => true" --6 " => false"-+3" => false"95a54e53" => false 说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可 ...

64. 最小路径和(一般)给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例:12345678输入:[ [1,3,1], [1,5,1], [4,2,1]]输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimum-path-sum 思路：创建二维数组 dp，与原始网格的大小相同，dp[i] [j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然，dp[0] [0]=grid[0] [0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。 当 i>0 且 j=0 时，dp[i] [0]=dp[i−1] [0]+grid[i] [0]。 当 i=0 且 j>0 时，dp[0] [j]=dp[0] [j−1]+grid[0] [j]。 当 i>0 且 j>0 时，dp[i] [j]=min(dp[i−1] [j],dp ...

54. 螺旋矩阵/面试题29. 顺时针打印矩阵（一般）给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 示例 1:1234567输入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]输出: [1,2,3,6,9,8,7,4,5] 示例 2:1234567输入:[ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12]]输出: [1,2,3,4,8,12,11,10,9,5,6,7] 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/spiral-matrix 思路：按照右，下，左，上的顺序读，每次计数num-1，直到减完，值得多看多学 思路3深搜 代码1：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152//返回的是listclass Solution { ...

53. 最大子序和/面试题42. 连续子数组的最大和(简单)给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-subarray 思路1：对于含有正数的序列而言,最大子序列肯定是正数,所以头尾肯定都是正数.我们可以从第一个正数开始算起,每往后加一个数便更新一次和的最大值;当当前和成为负数时,则表明此前序列无法为后面提供最大子序列和,因此必须重新确定序列首项. 思路2：分治法的策略一般分为三步： 定义基本情况 将大问题不断分解为小问题，递归的解决 合并所有情况并获得解 针对于该题，如果将整个数组分为左右两部分，该题可以把需要求解的目标序列（最大和序列）分为三种基本情况 目标序列都在左半边 目标序列都在 ...

50. Pow(x, n)/面试题16. 数值的整数次方（中等）实现 pow(x, n) ，即计算 x 的 n 次幂函数。 示例 1:输入: 2.00000, 10输出: 1024.00000 示例 2:输入: 2.10000, 3输出: 9.26100 示例 3:输入: 2.00000, -2输出: 0.25000解释: 2-2 = 1/22 = 1/4 = 0.25 说明:-100.0 < x < 100.0n 是 32 位有符号整数，其数值范围是[−231, 231 − 1]。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/powx-n 思路1：这里思路用分治的思想，如果是n是偶数，计算x*x^(n/2)即可，如果是奇数，我们求n-1的，最后再求x 乘以n-1得到的值，这里使用递归写法会出一些问题，由于n为int，所以会出现下面的错误，所以要进行单独判断 最后执行的输入：1.00000 -2147483648 执行出错信息：Line 8: java.lang.StackOverflowErr ...

46. 全排列(一般)给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/permutations著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。链接：https://leetcode-cn.com/problems/search-insert-position 思路：排列树的回溯，终止条件就是path与排列数大小相等，回溯尝试的是否将当前值加入path。最基本的回溯，必须多看 代码：123456789101112131415161718192021222324class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List< ...

35. 搜索插入位置（简单）给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1:输入: [1,3,5,6], 5输出: 2 示例 2:输入: [1,3,5,6], 2输出: 1 示例 3:输入: [1,3,5,6], 7输出: 4 示例 4:输入: [1,3,5,6], 0输出: 0 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/search-insert-position 思路：思路肯定是二分查找，由于形参中没有i，j，所有不能用递归，这里使用非递归的二分查找方法 代码：1234567891011121314151617class Solution { public int searchInsert(int[] nums, int target) { int left=0,right=nums.length-1; int mid=0; while ( ...

24. 两两交换链表中的节点（中等）给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例:给定 1->2->3->4, 你应该返回 2->1->4->3. 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs 思路：这里由于正在学习递归思想，这次先以递归来做，这里的递归三部曲为 终止条件：链表中只剩一个节点或者已经没有节点了 返回值：返回已经进行处理的链表 本层递归：将本层中head，next，和已经处理完的链表部分，交换这三个节点的前两个 递归思想请看这里 代码：1234567891011121314151617181920212223/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(i ...