第31天--算法（Leetcode 128,130,131）
128.最长连续序列
public int longestConsecutive(int[] nums) {
int len = 0;
HashMap hm = new HashMap<>();
for(int i : nums) {
if(!hm.containsKey(i)) {
hm.put(i,1);
int preLen = hm.containsKey(i - 1) ? hm.get(i - 1) : 0;
int posLen = hm.containsKey(i + 1) ? hm.get(i + 1) : 0;
int curLen = preLen + posLen + 1;
hm.put(i - preLen,curLen);
hm.put(i + posLen,curLen);
len = Math.max(len,curLen);
}
}
return len;
}
130.被围绕的区域
public void solve(char[][] board) {
if(board == null || board.length == 0) {
return;
}
int M = board.length;
int N = board[0].length;
for(int i = 0;i < N;i ++) {
if(board[0][i] == 'O') {
process(board,0,i);
}
if(board[M - 1][i] == 'O') {
process(board,M - 1,i);
}
}
for(int i = 1;i < M - 1;i ++) {
if(board[i][0] == 'O') {
process(board,i,0);
}
if(board[i][N - 1] == 'O') {
process(board,i,N - 1);
}
}
for(int i = 0;i < M;i ++) {
for(int j = 0;j < N;j ++) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
if(board[i][j] == 'F') {
board[i][j] = 'O';
}
}
}
}
public void process(char[][] board,int i,int j) {
if(i < 0 || j < 0 || i == board.length || j == board[0].length || board[i][j] != 'O') {
return;
}
board[i][j] = 'F';
process(board,i + 1,j);
process(board,i - 1,j);
process(board,i,j + 1);
process(board,i,j - 1);
}
131.分割回文串
public List> partition(String s) {
List> res = new ArrayList<>();
if(s == null || s.length() == 0) {
return res;
}
char s1[] = s.toCharArray();
int N = s.length();
boolean dp[][] = new boolean[N][N];
dp[N - 1][N - 1] = true;
for(int i = 0;i < N - 1;i ++) {
dp[i][i] = true;
dp[i][i + 1] = s1[i] == s1[i + 1];
}
for(int i = N - 3;i >= 0;i --) {
for(int j = i + 2;j < N;j ++) {
if(dp[i + 1][j - 1] && s1[i] == s1[j]) {
dp[i][j] = true;
}
}
}
LinkedList path = new LinkedList<>();
process(res,path,0,s,dp);
return res;
}
public void process(List> res,LinkedList path,int index,String s,boolean dp[][]) {
if(index == s.length()) {
res.add(new ArrayList<>(path));
}else {
for(int j = index;j < s.length();j ++) {
if(dp[index][j]) {
path.addLast(s.substring(index,j + 1));
process(res,path,j + 1,s,dp);
path.pollLast();
}
}
}
}