LeetCode 47. Permutations II

LeetCode 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.此问题同46题思路,条件基本一致,只是给定的数组中可能有重复值,需要去掉.
假设数组A[10],我们在遍历每个元素A[i]的时候,都检查A[i]是否在A[1:i]中出现过,如果曾经出现,则直接跳过

继续阅读

LeetCode 46. Permutations

Given a collection of distinct integers, return all possible permutations.写好递归函数的要点是:1.确定递归关系式 2. 确定递归结束条件 3.A问题可以分解成B,C,D···Z几个子问题,假设子问题已经解决,在此情况下来解决A问题
此题目中,假设有一个数组A[10],我们拿出A[1],假设A[1:10](两端的值都可以取到)组成的所有序列都已经取到,我们把A[1]和所有的组合相加,就得到了
以A[1]为首的所有可能组合
同理,我们把A[2]拿出来,把A[1]+A[3:10]组成一个新的数组,假设此数组的所有排列组合和已经取到,再把A[2]和它们相加,就得到了以A[2]为首的所有组合

继续阅读
LeetCode 45. Jump Game II

LeetCode 45. Jump Game II

Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example: Input: [2,3,1,1,4] Output: 2

Explanation: The minimum number of jumps to reach the last index is 2.

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:You can assume that you can always reach the last index.

继续阅读

LeetCode 42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

继续阅读