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;
}
}
解法二：使用一個棧量淌，棧中保存下標，當插入一個新的下標時胚股，如果該下標對應的高度小于棧頂下標所對應的高度琅拌，那么直接插入摘刑，否則，將棧頂拋出即彪，然后根據(jù)當前棧頂和要插入的下標對應的高度來計算可以儲水的容量隶校，并將該元素插入棧中。
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題類似，用動態(tài)規(guī)劃的思路舞终，維護一個二維的數(shù)組敛劝。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代表步數(shù)征绎，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());
}
}
