72. Edit Distance
动态规划：
public class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] cost = new int[m + 1][n + 1];
for(int i = 0; i <= m; I++)
cost[i][0] = I;
for(int i = 1; i <= n; I++)
cost[0][i] = I;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(word1.charAt(i) == word2.charAt(j))
cost[i + 1][j + 1] = cost[i][j];
else {
int a = cost[i][j];
int b = cost[i][j + 1];
int c = cost[i + 1][j];
cost[i + 1][j + 1] = a < b ? (a < c ? a : c) : (b < c ? b : c);
cost[i + 1][j + 1]++;
}
}
}
return cost[m][n];
}
}
73. Set Matrix Zeroes
用第一行和第一列标记改行或改列是否要变成0，但是左上角的一个值是代表行还是列我们不确定，所以在定义两个标记变量，标明第0行和第0列要不要变成0.
class Solution {
public void setZeroes(int[][] matrix) {
if(matrix==null || matrix.length==0)
return;
boolean firstrow = false;
boolean firstcol = false;
for(int i=0;i<matrix.length;i++){
if(matrix[i][0]==0)
firstcol = true;
for(int j=0;j<matrix[0].length;j++){
if(i==0 && matrix[0][j]==0)
firstrow=true;
if(matrix[i][j]==0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i=1;i<matrix[0].length;i++)
if(matrix[0][i]==0)
for(int j=1;j<matrix.length;j++)
matrix[j][i] = 0;
for(int i=1;i<matrix.length;i++)
if(matrix[i][0]==0)
for(int j=1;j<matrix[0].length;j++)
matrix[i][j] = 0;
if(firstrow)
for(int i=0;i<matrix[0].length;i++)
matrix[0][i]=0;
if(firstcol)
for(int j=0;j<matrix.length;j++)
matrix[j][0]=0;
}
}
74. Search a 2D Matrix
当作一个一维的二分搜索就可以，只不过需要根据将一维的index转换为二维的index
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length==0)
return false;
int row = matrix.length;
int col = matrix[0].length;
int left = 0;
int right = row * col - 1;
while(left <= right){
int mid = (right - left) / 2 + left;
int value = matrix[mid/col][mid%col];
if(value == target)
return true;
else if(value < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
}
75. Sort Colors
两次循环，第一循环将0排到前面，第二次循环再把1排到中间
class Solution {
public void sortColors(int[] nums) {
if(nums==null || nums.length==0)
return;
int left = 0;
int right = nums.length-1;
while(left <= right){
while(left<=right && nums[left]==0) left++;
while(left<=right && nums[right]!=0) right--;
if(left < right)
swap(nums,left,right);
}
right = nums.length-1;
while(left <= right){
while(left<=right && nums[left]==1) left++;
while(left<=right && nums[right]!=1) right--;
if(left < right)
swap(nums,left,right);
}
}
public static void swap(int[] nums,int i,int j){
int temp = nums[I];
nums[i] = nums[j];
nums[j] = temp;
}
}
76. Minimum Window Substring
维护两个索引Start 和 End（初值都为0），分别标识 子串W（这里表示Window）的开始位置和结束位置。
下面关键就是判断何时这两个索引要变化。
1.首先如果没有找到map中的单词，End++，继续往后找。
2.如果map中的字母还没找完，且找到了当前字母，则map中当前单词对应的value--（表示找到一个）。
3.当然可能有重复字母，即value减为负了，这样找出来的window包含多余重复字母肯定不是最优，所以我们要记录找到字母个数。
4.一旦找满单词，这个时候Start到End的位置肯定是包含目标T串所有字符的子串W（即Window）
5.但是这个window不是最优的，我们要对start++，start++的条件有两个，满足其一即可，第一个是当前的字符不在map中，另一个是当前的字符在map中的value是负的，标明这个字符有盈余
class Solution {
public String minWindow(String s, String t) {
if(s.length() < t.length())
return "";
int start = 0;
int end = 0;
int astart = 0;
int aend = 0;
int minLength = s.length()+1;
Map<Character,Integer> map = new HashMap<Character,Integer>();
for(int i = 0;i<t.length();i++){
if(map.containsKey(t.charAt(i)))
map.put(t.charAt(i),map.get(t.charAt(i))+1);
else
map.put(t.charAt(i),1);
}
int findCount = 0;
while(end<s.length()){
if(map.containsKey(s.charAt(end))){
int count = map.get(s.charAt(end));
if(count > 0){
findCount ++;
}
map.put(s.charAt(end),map.get(s.charAt(end))-1);
//如果找到了足够的长度的单词，我们移动start，让他移动到最小字串的位置
if(findCount == t.length()){
//如果start位置的字符不在字典中，或者字典中记录的出现次数是负数，均要移动start
while(!map.containsKey(s.charAt(start)) || map.get(s.charAt(start))<0){
if(map.containsKey(s.charAt(start)) && map.get(s.charAt(start))<0)
map.put(s.charAt(start),map.get(s.charAt(start))+1);
start++;
}
if(minLength > (end-start+1)){
minLength = end-start + 1;
astart = start;
aend = end;
}
}
}
end++;
}
return minLength == s.length() + 1?"":s.substring(astart,aend+1);
}
}
77. Combinations
回溯法
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(n<=0 || n<k)
return res;
backtracking(res,new ArrayList<Integer>(),n,k,1);
return res;
}
public static void backtracking(List<List<Integer>> res,List<Integer> arr,int n,int k,int start){
if(arr.size()==k){
res.add(new ArrayList<Integer>(arr));
}
else if(arr.size()>k)
return;
else{
for(int i=start;i<=n;i++){
arr.add(i);
backtracking(res,arr,n,k,i+1);
arr.remove(arr.size()-1);
}
}
}
}
78. Subsets
回溯法
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0)
return res;
backtracking(res,new ArrayList<Integer>(),nums,0);
return res;
}
public static void backtracking(List<List<Integer>> res,List<Integer> arr,int[] nums,int start){
res.add(new ArrayList<Integer>(arr));
for(int i=start;i<nums.length;i++){
arr.add(nums[i]);
backtracking(res,arr,nums,i+1);
arr.remove(arr.size()-1);
}
}
}
79. Word Search
回溯法，先遍历数组，找到和word第一个字符相同的位置，从这些位置开始进行回溯，往上下左右四个方向进行搜索，同时，需要一个boolean数组保存哪些位置已经用过。
class Solution {
public boolean exist(char[][] board, String word) {
if(board==null || board.length==0)
return false;
int row = board.length;int col = board[0].length;
boolean[][] used = new boolean[row][col];
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
used[i][j] = false;
for(int i = 0;i<row;i++)
for(int j=0;j<col;j++){
if(word.charAt(0) == board[i][j]){
used[i][j] = true;
boolean res = tracking(board,i,j,word,1,used);
if(res)
return true;
used[i][j] = false;
}
}
return false;
}
public static boolean tracking(char[][] board,int row,int col,String word,int start,boolean[][] used){
if(start>=word.length())
return true;
//向上搜索
if(row>0 && used[row-1][col]==false && board[row-1][col]==word.charAt(start)){
used[row-1][col]=true;
boolean res = tracking(board,row-1,col,word,start+1,used);
if(res)
return true;
used[row-1][col]=false;
}
//向左搜索
if(col>0 && used[row][col-1]==false && board[row][col-1]==word.charAt(start)){
used[row][col-1]=true;
boolean res = tracking(board,row,col-1,word,start+1,used);
if(res)
return true;
used[row][col-1]=false;
}
//向下搜索
if(row<board.length-1 && used[row+1][col]==false && board[row+1][col]==word.charAt(start)){
used[row+1][col] = true;
boolean res = tracking(board,row+1,col,word,start+1,used);
if(res)
return true;
used[row+1][col] = false;
}
//向右搜索
if(col<board[0].length-1 && used[row][col+1]==false && board[row][col+1]==word.charAt(start)){
used[row][col+1] = true;
boolean res = tracking(board,row,col+1,word,start+1,used);
if(res)
return true;
used[row][col+1] = false;
}
return false;
}
}
80 Remove Duplicates from Sorted Array II
class Solution {
public int removeDuplicates(int[] nums) {
if(nums==null || nums.length==0)
return 0;
int count = 1;
int cur = nums[0];
int index = 1;
for(int i=1;i<nums.length;i++){
if(nums[i] == cur){
count++;
if(count>2){
continue;
}
else{
nums[index++] = nums[I];
}
}
else{
count = 1;
cur = nums[I];
nums[index++] = nums[I];
}
}
return index;
}
}
