41. First Missing Positive
class Solution {
public int firstMissingPositive(int[] nums) {
int I=0;
while(i < nums.length){
if(nums[i] != i+1 && nums[i]>0 && nums[i]<=nums.length && nums[nums[i]-1] != nums[I])
swap(nums,i,nums[i]-1);
else
I++;
}
for(i=0;i<nums.length;i++)
if(nums[i] != I+1)
return I+1;
return nums.length+1;
}
public static void swap(int[] nums,int i,int j){
int temp = nums[I];
nums[i] = nums[j];
nums[j] = temp;
}
}
42. Trapping Rain Water
思路1:
代码：
class Solution {
public int trap(int[] height) {
if (height==null || height.length==0)
return 0;
int[] left_max = new int[height.length];
int[] right_max = new int[height.length];
left_max[0] = height[0];
right_max[height.length-1] = height[height.length-1];
for(int i = 1;i<height.length;i++){
left_max[i] = Math.max(height[i],left_max[i-1]);
}
for(int j=height.length-2;j>=0;j--){
right_max[j] = Math.max(height[j],right_max[j+1]);
}
int ans = 0;
for(int i = 0;i<height.length;i++){
ans += Math.min(left_max[i],right_max[i]) - height[I];
}
return ans;
}
}
解法二：使用一个栈，栈中保存下标，当插入一个新的下标时，如果该下标对应的高度小于栈顶下标所对应的高度，那么直接插入，否则，将栈顶抛出，然后根据当前栈顶和要插入的下标对应的高度来计算可以储水的容量，并将该元素插入栈中。
class Solution {
public int trap(int[] height) {
int ans = 0;
if(height==null || height.length==0)
return ans;
int current = 0;
Stack<Integer> stack = new Stack<Integer>();
while(current < height.length){
while(!stack.empty() && height[current]>height[stack.peek()]){
int top = stack.peek();
stack.pop();
if(stack.empty())
break;
ans += (Math.min(height[current],height[stack.peek()])-height[top]) * (current-stack.peek()-1);
}
stack.push(current);
current ++;
}
return ans;
}
}
44. Wildcard Matching
跟前面的第10题类似，用动态规划的思路，维护一个二维的数组。dp[i][j] 表示p[0...j-1]和s[0...i-1]是否相配，注意当p[j]为和不为两种情况下如何判断当前为true和false就行了。
class Solution {
public boolean isMatch(String s, String p) {
int row = p.length() + 1;
int col = s.length() + 1;
boolean[][] dp = new boolean[row][col];
dp[0][0] = true;
for(int i=1;i<col;i++){
dp[0][i] = false;
}
for(int j=1;j<row;j++){
if(p.charAt(j-1)=='*')
dp[j][0] = dp[j-1][0];
else
dp[j][0] = false;
}
for(int i=1;i<col;i++)
for(int j=1;j<row;j++){
if(p.charAt(j-1)=='*'){
//要么是上面是true 要么是左边是true，如果上面是true，此时*当空串使，如果左边是true，那么此时*当一个字符使
if(dp[j-1][i] || dp[j][i-1])
dp[j][i]=true;
else
dp[j][i]=false;
}
else{
//如果不为*的话，首先左上角的位置要是true，如果不是的话，s和p都增加一个字符也不会匹配，同时s和p增加的字符要相同或者p是？
if(dp[j-1][i-1] && (p.charAt(j-1)==s.charAt(i-1) || p.charAt(j-1)=='?'))
dp[j][i] = true;
else
dp[j][i] = false;
}
}
return dp[row-1][col-1];
}
}
45. Jump Game II
stepCount代表步数，curmax表示当前能够走到的最大值，chase代表上一步能走到的最大值，当我们遍历到chase这的时候，curmax变成了在这一段里面能够走到的最远的地方。比如2，3，1，1，4，我们第一步最多走到索引为2的地方，此时chase为0，curmax为2，第二步最多走到索引为4的地方，此时chase为2，curmax为4。
class Solution {
public int jump(int[] nums) {
int stepCount = 0;
int curmax = 0;
int chase = 0;
for(int i=0;i<nums.length-1;i++){
curmax = Math.max(curmax,i+nums[I]);
if(i==chase){
stepCount++;
chase = curmax;
}
}
return stepCount;
}
}
46. Permutations
回溯法的应用
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
backtracking(nums,new ArrayList<>(),list);
return list;
}
public static void backtracking(int[] nums,ArrayList<Integer> now,List<List<Integer>> list){
if(now.size() == nums.length){
list.add(new ArrayList<Integer>(now));
}
else{
for(int i=0;i<nums.length;i++){
if(now.contains(nums[i])) continue;
now.add(nums[I]);
backtracking(nums,now,list);
now.remove(now.size()-1);
}
}
}
}
47. Permutations II
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) return res;
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backtracking(nums,used,new ArrayList<Integer>(),res);
return res;
}
public static void backtracking(int[] nums,boolean[] used,ArrayList<Integer> arr,List<List<Integer>> res){
if(arr.size() == nums.length)
res.add(new ArrayList<Integer>(arr));
else{
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
if(i>0 && nums[i-1]==nums[i] && used[i-1]) continue;
used[i] = true;
arr.add(nums[i]);
backtracking(nums,used,arr,res);
arr.remove(arr.size()-1);
used[i] = false;
}
}
}
}
48. Rotate Image
分两步：
class Solution {
public void rotate(int[][] matrix) {
if(matrix==null || matrix.length==0)
return;
int col = matrix[0].length;
int row = matrix.length;
for(int i=0;i<row;i++){
for(int j=0;j<col/2;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][col-j-1];
matrix[i][col-j-1] = temp;
}
}
for(int i=0;i<row;i++){
for(int j=0;j<col-i-1;j++){
int temp= matrix[i][j];
matrix[i][j] = matrix[col-j-1][row-i-1];
matrix[col-j-1][row-i-1] = temp;
}
}
}
}
49. Group Anagrams
采用排序的方法，判断两个字符串是否相似
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List> ans = new HashMap<String, List>();
for (String s : strs) {
char[] ca = s.toCharArray();
Arrays.sort(ca);
String key = String.valueOf(ca);
if (!ans.containsKey(key)) ans.put(key, new ArrayList());
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
