头像

RecursivelyAscend


访客:3698

离线:1个月前



class MinStack {
    Stack<Integer> stack;
    Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(min.isEmpty()||min.peek()>x)
            min.push(x);
    }

    public void pop() {
        int x = stack.pop();
        if(x == min.peek())
            min.pop();
    }

    public int top() {
        return stack.peek();
    }

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */



class MinStack {
    Stack<Integer> stack;
    Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(min.isEmpty()||min.peek()>x)
            min.push(x);
    }

    public void pop() {
        int x = stack.pop();
        if(x == min.peek())
            min.pop();
    }

    public int top() {
        return stack.peek();
    }

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */



class Solution {
    public int[] printMatrix(int[][] matrix) {
        int[] arr = {};
        if(matrix == null || matrix.length == 0 || (matrix.length==1 && matrix[0].length == 0))
            return arr;
        int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
        int m = matrix.length;
        int n = matrix[0].length;
        int[] res = new int[m*n];
        int[][] visited = new int[m][n];
        int x = 0, y = 0, d = 1, index = 0;
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                res[index++] = matrix[x][y];
                visited[x][y] = 1;
                int a = x + dir[d][0];
                int b = y + dir[d][1];
                if(a<0||a>=m||b<0||b>=n||visited[a][b]==1){
                    d = (d+1)%4;
                    a = x + dir[d][0];
                    b = y + dir[d][1];
                }
                x = a;
                y = b;
            }
        }
        return res;
    }
}


活动打卡代码 AcWing 39. 对称的二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        else
            return dfs(root.left, root.right);
    }

    boolean dfs(TreeNode left, TreeNode right){
        if(left == null || right == null)
            return left == null && right == null;
        if(left.val!=right.val)
            return false;
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }
}



class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode p = head;
        ListNode p1 = l1, p2 = l2;
        while(p1!=null&&p2!=null){
            if(p1.val<p2.val){
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }else{
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
        if(p1!=null)
            p.next = p1;
        if(p2!=null)
            p.next = p2;
        return head.next;
    }
}


活动打卡代码 AcWing 35. 反转链表

双指针依次反转只需遍历一遍

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return  pre;
    }
}

用辅助栈或者递归的解法都需要遍历两遍




活动打卡代码 AcWing 37. 树的子结构

class Solution {
    public boolean hasSubtree(TreeNode pRoot1, TreeNode pRoot2) {
        if(pRoot1 == null || pRoot2 == null) return false;
        if(isPart(pRoot1, pRoot2)) return true;
        return hasSubtree(pRoot1.left, pRoot2) || hasSubtree(pRoot1.right, pRoot2);
    }

    boolean isPart(TreeNode root1, TreeNode root2){
        if(root2 == null) return true;
        if(root1 == null) return false;
        else{
            if(root1.val == root2.val)
                return isPart(root1.left, root2.left) && isPart(root1.right, root2.right);
            else return false;
        }
    }
}


活动打卡代码 AcWing 38. 二叉树的镜像

class Solution {
    public void mirror(TreeNode root) {
        if(root!=null){
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        mirror(root.left);
        mirror(root.right);
        }else{
            return;
        }
    }
}



用HashSet去重

class Solution {
    public ListNode entryNodeOfLoop(ListNode head) {

        Set<ListNode> set = new HashSet<>();
        while(head!=null && set.add(head))
            head = head.next;
        return head;
    }
}

用双指针

    public ListNode entryNodeOfLoop(ListNode head) {
        ListNode pf = head;
        ListNode ps = head;
        while(pf!=null && pf.next != null){
            pf = pf.next.next;
            ps = ps.next;
            if(pf == ps){
                ps = head;
                while(ps!=pf){
                    ps = ps.next;
                    pf = pf.next;
                }
                return ps;
            }
        }
        return null;
    }



递归

    ListNode res = null;
    public ListNode findKthToTail(ListNode pListHead, int k) {
        int[] kk = {k+1};
        dfs(pListHead, kk);
        return res;
    }

    void dfs(ListNode pListHead, int[] kk){
        if(pListHead != null)
            dfs(pListHead.next, kk);
        kk[0]-=1;
        if(kk[0] == 0)
            res = pListHead;
        return;
    }

双指针

    public ListNode findKthToTail(ListNode pListHead, int k) {
       ListNode pr = pListHead;
       ListNode pl = pListHead;
       for(int i = 1; i<=k; i++){
           if(pr == null)
            return null;
           pr = pr.next;
       }
       while(pr!=null){
           pr = pr.next;
           pl = pl.next;
       }
       return pl;
    }