第24天--算法（Leetcode 76,78,79,84,88）
76.覆盖最小子串
public String minWindow(String s, String t) {
if(s.length() < t.length()) {
return "";
}
char s1[] = s.toCharArray();
char t1[] = t.toCharArray();
int L = 0;
int R = 0;
int ansL = -1;
int ansR = -1;
int minLen = -1;
int all = 0;
int map[] = new int[256];
for(char c : t1) {
map[c] ++;
all ++;
}
while(R < s1.length) {
map[s1[R]] --;
if(map[s1[R]] >= 0) {
all --;
}
if(all == 0) {
while(map[s1[L]] < 0) {
map[s1[L ++]] ++;
}
if(minLen == -1 || minLen > R - L + 1) {
minLen = R - L + 1;
ansL = L;
ansR = R;
}
map[s1[L ++]] ++;
all ++;
}
R ++;
}
return minLen == -1 ? "" : s.substring(ansL,ansR + 1);
}
78.子集
public List> subsets(int[] nums) {
List> res = new ArrayList<>();
List path = new ArrayList<>();
process(res,path,0,nums);
return res;
}
public void process(List> res,List path,int index,int nums[]) {
if(index == nums.length) {
res.add(new ArrayList<>(path));
}else {
process(res,path,index + 1,nums);
path.add(nums[index]);
process(res,path,index + 1,nums);
path.remove(path.indexOf(nums[index]));
}
}
79.单词搜索
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0) {
return false;
}
if(word == null || word.length() == 0) {
return true;
}
char word1[] = word.toCharArray();
for(int i = 0;i < board.length;i ++) {
for(int j = 0;j < board[0].length;j ++) {
if(process(board,i,j,word1,0)) {
return true;
}
}
}
return false;
}
public boolean process(char[][] board,int i,int j,char word[],int k) {
if(k == word.length) {
return true;
}
if(i < 0 || j < 0 || i == board.length || j == board[0].length) {
return false;
}
if(board[i][j] != word[k]) {
return false;
}
char temp = board[i][j];
board[i][j] = 0;
boolean ans = process(board,i + 1,j,word,k + 1)
|| process(board,i - 1,j,word,k + 1)
|| process(board,i,j + 1,word,k + 1)
|| process(board,i,j - 1,word,k + 1);
board[i][j] = temp;
return ans;
}
84.柱状图中最大的矩形
public int largestRectangleArea(int[] heights) {
if(heights == null || heights.length == 0) {
return 0;
}
int maxArea = 0;
Stack stack = new Stack<>();
for(int i = 0;i < heights.length;i ++) {
while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
int x = stack.pop();
int L = stack.isEmpty() ? -1 : stack.peek();
int R = i;
int curArea = (R - L - 1) * heights[x];
maxArea = Math.max(maxArea,curArea);
}
stack.push(i);
}
while(!stack.isEmpty()) {
int x = stack.pop();
int L = stack.isEmpty() ? -1 : stack.peek();
int R = heights.length;
int curArea = (R - L - 1) * heights[x];
maxArea = Math.max(maxArea,curArea);
}
return maxArea;
}
88.合并两个有序数组
public void merge(int[] nums1, int m, int[] nums2, int n) {
int ans[] = new int[m + n];
int s1 = 0;
int s2 = 0;
int i = 0;
while(s1 < m && s2 < n) {
if(nums1[s1] <= nums2[s2]) {
ans[i ++] = nums1[s1 ++];
}else {
ans[i ++] = nums2[s2 ++];
}
}
while(s1 < m) {
ans[i ++] = nums1[s1 ++];
}
while(s2 < n) {
ans[i ++] = nums2[s2 ++];
}
for(int j = 0;j < m + n;j ++) {
nums1[j] = ans[j];
}
}