👨💻个人主页: 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈
解法一
BFS
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
while(!list.isEmpty()){
int size = list.size();
List<Integer> l = new ArrayList<>();
for(int i = 0;i < size;i++){
TreeNode t = list.pop();
l.add(t.val);
if(t.left != null)list.add(t.left);
if(t.right != null)list.add(t.right);
}
res.add(l);
}
return res;
}
}
解法一
递归 最简单
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
fun(root,list);
return list;
}
public void fun(TreeNode root,List<Integer> list){
if(root == null)return;
fun(root.left,list);
list.add(root.val);
fun(root.right,list);
}
}
解法二
自己维护栈
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.add(root);
root = root.left;
}
TreeNode node = stack.pop();
list.add(node.val);
root = node.right;
}
return list;
}
}
解法一
暴力枚举 外层循环枚举起始值 内层循环枚举结束值 然后比较数组
class Solution {
public String minWindow(String s, String t) {
int slen = s.length();
int tlen = t.length();
if(slen < tlen) return "";
int res = slen + 1;
int left = 0;
char [] arrs = s.toCharArray();
char [] arrt = t.toCharArray();
int [] s1 = new int[128];
int [] t1 = new int[128];
for(int i = 0;i < tlen;i++){
t1[arrt[i]]++;
}
for(int i = 0;i < slen;i++){ // 枚举起始位置
Arrays.fill(s1,0);
for(int j = i;j < slen;j++){ // 枚举结束位置
s1[arrs[j]]++;
if(j-i+1 < tlen) continue;
if(check(s1,t1)){
System.out.println(i+" "+j);
if(res > j-i+1){
res = j-i+1;
left = i;
}
break;
}
}
}
if(res == slen+1) return "";
StringBuilder sb = new StringBuilder();
for(int i = left;i < left+res;i++){
sb.append(arrs[i]);
}
return sb.toString();
}
public boolean check(int[] arrs,int[] arrt){
for(int i = 0;i < arrs.length;i++){
if(arrs[i] < arrt[i]){
return false;
}
}
return true;
}
}
解法二
滑动窗口
class Solution {
public String minWindow(String s, String t) {
int slen = s.length();
int tlen = t.length();
if(slen < tlen) return "";
int minLen = slen + 1;
int begin = 0;
int left = 0;
int right = 0;
int distance = 0;
char [] arrs = s.toCharArray();
char [] arrt = t.toCharArray();
int [] s1 = new int[128];
int [] t1 = new int[128];
for(int i = 0;i < tlen;i++){
t1[arrt[i]]++;
}
while(right < slen){
//1. 如果当前字符没有在t中
if(t1[arrs[right]] == 0){
s1[arrs[right]]++;
right++;
continue;
}
//2. 到这里说明当前字符在t中存在
//2.1 当left - right中这个字符的个数少于t1中这个字符个数时候才加一
// 因为当等于或者大于的时候,说明s1中这个的字符与t1中相等或者大于,但是他实际包含的t1的长度是t1中字符的长度
if(s1[arrs[right]] < t1[arrs[right]]){
distance++;
}
s1[arrs[right]]++;
right++;
//3.说明找到一个字符串满足条件了,就开始收缩左边界
while(distance == tlen){
if(right - left < minLen){
minLen = right-left;
begin = left;
}
if(s1[arrs[left]] == t1[arrs[left]]){
distance--;
}
s1[arrs[left]]--;
left++;
}
}
if(minLen == slen + 1) return "";
return s.substring(begin,begin+minLen);
}
}