头像

mixiuhuang




离线:19天前


活动打卡代码 AcWing 1497. 树的遍历

import java.util.*;

public class Main {
    static Map<Integer, Integer> map = new HashMap<>();
    static int[] postorder;
    static int[] inorder;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        postorder = new int[n];
        inorder = new int[n];
        for (int i = 0; i < n; i++) {
            postorder[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            inorder[i] = scanner.nextInt();
            map.put(inorder[i], i);
        }
        Node root = build(0, n - 1, 0, n - 1);
        bfs(root);
    }

    private static void bfs(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            System.out.print(node.val + " ");
        }
    }

    private static Node build(int pl, int pr, int il, int ir) {
        if (pl > pr || il > ir) {
            return null;
        }
        int rootVal = postorder[pr];
        int rootIndex = map.get(rootVal);
        Node root = new Node(rootVal);
        root.left = build(pl, pl + rootIndex - il - 1, il, rootIndex - 1);
        root.right = build(pl + rootIndex - il, pr - 1, rootIndex + 1, ir);
        return root;
    }

    static class Node {
        int val;
        Node left;
        Node right;
        Node() {}
        Node(int x) { val = x; }
    }
}



递归做法

public class NestedIterator implements Iterator<Integer> {
    List<Integer> list;
    int k;
    public NestedIterator(List<NestedInteger> nestedList) {
        list = new ArrayList<>();
        k = 0;
        for (int i = 0; i < nestedList.size(); i++) {
            dfs(nestedList.get(i));
        }
    }

    private void dfs(NestedInteger nestedInteger) {
        if (nestedInteger.isInteger()) {
            list.add(nestedInteger.getInteger());
            return;
        }
        for (NestedInteger n : nestedInteger.getList()) {
            dfs(n);
        }
    }

    @Override
    public Integer next() {
        return list.get(k++);
    }

    @Override
    public boolean hasNext() {
        return k < list.size();
    }
}

非递归做法

public class NestedIterator implements Iterator<Integer> {

    private Deque<Iterator<NestedInteger>> stack;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new LinkedList<>();
        stack.push(nestedList.iterator());
    }



    @Override
    public Integer next() {
        return stack.peek().next().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            Iterator<NestedInteger> it = stack.peek();
            if (!it.hasNext()) {
                stack.pop();
                continue;
            }
            NestedInteger next = it.next();
            if (next.isInteger()) {
                List<NestedInteger> list = new ArrayList<>();
                list.add(next);
                stack.push(list.iterator());
                return true;
            }
        }
        return false;
    }
}



class Solution {
    public int add(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        int xor = num1 ^ num2;
        int conj = (num1 & num2) << 1;
        return add(xor, conj);
    }
}


活动打卡代码 AcWing 191. 位1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}



import java.util.*;

/**
 * @author mixiuhuang
 * @create 2021-03-25 18:56
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            if (n == 0) {
                break;
            }
            int[] height = new int[n];
            for (int i = 0; i < n; i++) {
                height[i] = scanner.nextInt();
            }
            int[] left = new int[n];
            int[] right = new int[n];
            Deque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    left[i] = -1;
                } else {
                    left[i] = stack.peek();
                }
                stack.push(i);
            }
            stack.clear();
            for (int i = n - 1; i >= 0; i--) {
                while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    right[i] = n;
                } else {
                    right[i] = stack.peek();
                }
                stack.push(i);
            }
            long res = 0;
            for (int i = 0; i < n; i++) {
                res = Math.max(res, (long)height[i] * (long)(right[i] - left[i] - 1));
            }
            System.out.println(res);
        }
    }
}


活动打卡代码 LeetCode 456. 132模式

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        Deque<Integer> d = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {

            if (nums[i] < k) {
                return true;
            }
            while (!d.isEmpty() && d.peekLast() < nums[i]) {
                k = Math.max(k, d.pollLast());
            }
            d.add(nums[i]);
        }
        return false;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}



public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy, q = head;
        while (p != null && q != null) {
            if (q.next != null && q.next.val == q.val) {
                while (q.next != null && q.next.val == q.val) {
                    q = q.next;
                }
                q = q.next;
                p.next = q;
            } else {
                p = p.next;
                q = q.next;
            }
        }
        return dummy.next;
    }
}



mixiuhuang
2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 LeetCode 134. 加油站

mixiuhuang
4个月前

134. 加油站

一次遍历

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int rest = 0, run = 0, start = 0;
        for (int i = 0; i <gas.length; i++) {
            run += gas[i] - cost[i];
            rest += gas[i] - cost[i];
            if (run < 0) {
                start = i + 1;
                run = 0;
            }
        }
        return rest < 0 ? -1 : start;
    }
}