搜索旋转排序数组、买卖股票、岛屿数量
33. 搜索旋转排序数组
递归，考虑子数组所有可能情况，代码看着不够优雅：
class Solution {
public int search(int[] nums, int target) {
return search(nums,target,0,nums.length-1);
}
private int search(int[] nums,int target,int left,int right) {
if(left>right) return -1;
int mid = (left+right)/2;
if(nums[left]==target) return left;
if(nums[right]==target) return right;
if(nums[mid]==target) return mid;
if(nums[right]>nums[left]) {
if(nums[mid]>target) return search(nums,target,left,mid-1);
else return search(nums,target,mid+1,right);
}
if(nums[mid]>nums[left]) {
if(target<nums[left]||target>nums[mid]) return search(nums,target,mid+1,right);
else return search(nums,target,left,mid-1);
}
if(target<nums[mid]) return search(nums,target,left,mid-1);
else if(target<=nums[right]) return search(nums,target,mid+1,right);
else return search(nums,target,left,mid-1);
}
}
其实也就是这个思想，代码简洁的就是把里面的情况整合了一下。
123. 买卖股票的最佳时机 III
能想到用动态规划，但是第二次交易可能会在第一次交易没成的时候把0认为交易后的，从而导致错误，所以用了个最小值判断。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][3][2];
for(int i=0;i<n;i++) {
for(int j=0;j<3;j++) {
for(int k=0;k<2;k++) {
dp[i][j][k] = Integer.MIN_VALUE;
}
}
}
// prices遍历，第几次交易，1持有0不持有
dp[0][0][1] = -prices[0];
dp[0][0][0] = 0;
// dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j][0]-prices[i])
// dp[i][j][0] = max(dp[i-1][j-1][1]+prices[j],dp[i-1][j][0])
for(int i=1;i<n;i++) {
for(int j=0;j<=2;j++) {
dp[i][j][1] = dp[i-1][j][1];
if(dp[i-1][j][0]!=Integer.MIN_VALUE) {
dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j][0]-prices[i]);
}
dp[i][j][0] = dp[i-1][j][0];
if(j>=1 && dp[i-1][j-1][1]!=Integer.MIN_VALUE) {
dp[i][j][0] = Math.max(dp[i][j][0],dp[i-1][j-1][1]+prices[i]);
}
}
}
//System.out.println(Arrays.deepToString(dp));
return Math.max(dp[n-1][1][0],Math.max(dp[n-1][2][0],0));
}
}
一看答案，这么简洁的。。。
OK，一状态压缩，我的也挺简洁：
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[3][2];
for(int j=0;j<3;j++) {
for(int k=0;k<2;k++) {
dp[j][k] = Integer.MIN_VALUE;
}
}
// prices遍历，第几次交易，1持有0不持有
dp[0][1] = -prices[0];
dp[0][0] = 0;
// dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j][0]-prices[i])
// dp[i][j][0] = max(dp[i-1][j-1][1]+prices[j],dp[i-1][j][0])
for(int i=1;i<n;i++) {
for(int j=0;j<=2;j++) {
if(dp[j][0]!=Integer.MIN_VALUE) {
dp[j][1] = Math.max(dp[j][1],dp[j][0]-prices[i]);
}
if(j>=1 && dp[j-1][1]!=Integer.MIN_VALUE) {
dp[j][0] = Math.max(dp[j][0],dp[j-1][1]+prices[i]);
}
}
}
//System.out.println(Arrays.deepToString(dp));
return Math.max(dp[1][0],Math.max(dp[2][0],0));
}
}
200. 岛屿数量
深搜
直接深搜，遍历过加上标志。
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int result = 0;
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(grid[i][j]!='1') continue;
dfs(grid,i,j);
result++;
}
}
return result;
}
private void dfs(char[][] grid,int i,int j) {
if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]!='1') return;
grid[i][j] = '#';
dfs(grid,i+1,j);
dfs(grid,i-1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
}
}
并查集
好久没写过并查集了，也练练手吧。
class Solution {
private int[] getFather(int[][][] father,int i,int j) {
int[] f = father[i][j];
if(f[0]==i&&f[1]==j) return f;
return getFather(father,f[0],f[1]);
}
private void union(int[][][] father,int i,int j,int a,int b) {
int[] f = getFather(father,i,j);
int[] f2 = getFather(father,a,b);
father[f2[0]][f2[1]][0] = f[0];
father[f2[0]][f2[1]][1] = f[1];
}
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][][] father = new int[m][n][2];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
father[i][j][0] = i;
father[i][j][1] = j;
}
}
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(grid[i][j]=='1') {
if(i>0&&grid[i-1][j]=='1') union(father,i,j,i-1,j);
if(j>0&&grid[i][j-1]=='1') union(father,i,j,i,j-1);
}
}
}
int result = 0;
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(grid[i][j]=='1') {
int[] f = getFather(father,i,j);
if(i==f[0]&&j==f[1]) result++;
}
}
}
return result;
}
}
遇到的问题：union的时候，
union(father,i,j,i-1,j);
union(father,i,j,i,j-1);
private void union(int[][][] father,int i,int j,int a,int b) {
int[] f = getFather(father,i,j);
int[] f2 = getFather(father,a,b);
father[f2[0]][f2[1]][0] = f[0];
father[f2[0]][f2[1]][1] = f[1];
}
应该统一把后者挂到前面，也就是父节点挂到父节点。