头像

joyonline


访客:1670

离线:5个月前



joyonline
5个月前
class Solution {
    public int treeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        LinkedList<TreeNode> list = new LinkedList();
        list.add(root);
        int count = 0;
        while(root != null && !list.isEmpty()){
            int len = list.size();
            count++;
            while(len > 0){
                TreeNode tmp = list.pop();
                if(tmp.left != null) {
                    list.add(tmp.left);
                    root = tmp.left;
                }
                if(tmp.right != null){
                    list.add(tmp.right);
                    root = tmp.right;
                }
                len--;
            }
        } 
        return count;
    }

}



joyonline
5个月前

递归。满足条件跳出递归

class Solution {
    public TreeNode kthNode(TreeNode root, int k) {
        Solution s = new Solution();
        List<TreeNode> list = new ArrayList();
        return s.zx(root,k,list).get(k-1);
    }

    public List<TreeNode> zx(TreeNode root,int k,List<TreeNode> list){
        if(root.left != null){
            zx(root.left,k,list);
        }
        if(root != null){
            list.add(root);
            if(list.size() == k) {
                new RuntimeException();
            }
        }
        if(root.right != null){
            zx(root.right,k,list);
        }
        return list;
    }

}

非递归中序

class Solution {
    public TreeNode kthNode(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        int count = 0;
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                TreeNode t = stack.pop();//弹出根节点
                count++;
                if(count == k){
                    return t;
                }
                root = t.right;
            }

        }
        return root;
    }
}



joyonline
5个月前

go代码

func getMissingNumber(nums []int) int {

    if len(nums) == 0 || len(nums) == 1 || 
            nums[len(nums) - 1] == len(nums) - 1{
        return len(nums)
    }
    if nums[0] !=0 {
        return 0
    }
    start,end :=0,len(nums)-1
    for ;end - start > 1 ; {
        mid := (start + end) >> 1
        if nums[mid] <= mid {
            start = mid
        }else {
            end = mid
        }

    }
    return nums[end]-1

}



joyonline
5个月前

java 代码

class Solution {
    public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
        Stack<ListNode> a = new Stack();
        Stack<ListNode> b = new Stack();
        while(headA!=null || headB!=null){
            if(headA!=null) {
                a.push(headA);
                headA = headA.next;
            }
            if(headB!=null){
                b.push(headB);
                headB = headB.next;  
            }
        }
        ListNode tmp = null;
        while(!a.isEmpty() && !b.isEmpty()){
            ListNode f = a.pop();
            ListNode s = b.pop();
            if(f==s){
                tmp = f;
            }else{
                break;
            }
        }
        return tmp;
    }
}

a+c+b b+c+a

class Solution {
    public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while(p != q){
            if(p!=null) p = p.next;
            else p = headB;
            if(q!=null) q = q.next;
            else q = headA;
        }
        return p;
    }
}



joyonline
5个月前

java 代码

class Solution {
    public char firstNotRepeatingChar(String s) {
        int len = s.length();
        if(len == 0) return '#';
        int[] array = new int[126 - 32];//采用数组来存放位置。如果已存放,则职位-1
        for(int i=0;i<array.length;i++)
            array[i] = -1;
        for (int i = 0; i < len; i++) {
            int index = s.charAt(i) - 32;
            if (array[index] == -1) {
                array[index] = i;
            }else{
                array[index] = -1;
            }
        }
        int min = array.length;
        for (int i = 0; i < array.length; i++) {
            if(array[i] !=-1) {
                if(array[i] < min) min = array[i];
            }
        }
        ;
        return min==array.length?'#':s.charAt(min);
    }
}



joyonline
5个月前

java 代码

class Solution {
    public int longestSubstringWithoutDuplication(String s) {
        int len = s.length();
        if(len == 0 || len == 1) return len;
        //定义一个数组,长度位26。用于存储a-z最后一次出现的位置
        int[] array = new int[]{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
        int frist = 0;
        int second = 1;
        int max = 1;
        while(frist < len){
            int fristchar = s.charAt(frist)-97;
            array[fristchar] = frist;
            while(second < len){
                int secondchar = s.charAt(second)-97;
                if(array[secondchar] != -1){
                    frist = frist<=array[secondchar]? array[secondchar]+ 1:frist;
                }
                array[secondchar] = second;
                if((second-frist + 1) > max) max = second-frist + 1;
                second++;
            }
            frist++;
        }
        return max;
    }

}



joyonline
5个月前

java 代码

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] + sum) > nums[i]) { //判断前面的值+当前位置值 后的大小
                sum = nums[i] + sum;//如果比当前位置大,则前面的留着
            } else {
                sum =nums[i];//否则舍弃前面的
            }
            if(sum>max) max = sum;
        }
        return max;
    }
}



joyonline
5个月前

java 代码

class Solution {
    public List<Integer> printFromTopToBottom(TreeNode root) {
        List<Integer> result = new ArrayList();
        if(root==null){
            return result;
        }
        LinkedList<TreeNode> list = new LinkedList();//先进先出
        list.add(root);
        while(list.size()>0){
            TreeNode tmp = list.get(0);
            result.add(tmp.val);
            if(tmp.left !=null) list.add(tmp.left);
            if(tmp.right !=null) list.add(tmp.right);
            list.pop();
        }
        return result;
    }


}



joyonline
5个月前

java 代码

class MinStack {


    public Stack<Integer> a;
    public Stack<Integer> c;

    /** initialize your data structure here. */
    public MinStack() {
        a = new Stack();
        c = new Stack();
    }

    public void push(int x) {
        a.push(x);
        if(c.isEmpty()){
            c.push(x);
            return;
        }
        c.push(Math.min(x,c.peek()));
    }

    //删除第一个元素
    public void pop() {
        int x = a.pop();
        while(!c.isEmpty() && x == c.peek()){
             c.pop();
        }

    }

    //返回第一个元素
    public int top() {
        return  a.peek();
    }

    public int getMin() {
        return c.peek();
    }

}



joyonline
5个月前

java代码

class Solution {
    public boolean isPopOrder(int [] pushV,int [] popV) {
        int pul = pushV.length;
        int pol = popV.length; 
        if(pul != pol) return false;
        if(pul == 0 && pol == 0) return true; 
        Stack stack = new Stack();
        int k = 0;
        int flag = 0;
        while(k < pul){
            if(pushV[k] == popV[flag]){
                k++;
                flag++;
            }else{
                if(stack.isEmpty() || !stack.peek().equals(popV[flag])){
                    stack.push(pushV[k]);
                    k++;
                }else{
                    stack.pop();
                    flag++;
                }
            }

        }
        if(stack.isEmpty()){
            return true;
        }
        // for(int i=flag;i<pol;i++){
        //     // System.out.print(popV[i]);
        //     System.out.print(stack.pop());
        // }
        while(flag < pol){
            if(!stack.pop().equals(popV[flag])){
                return false;
            }
            flag++;
        }
        return true;
    }
}