mixiuhuang

8712

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<>();
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.left != null) {
}
if (node.right != null) {
}
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()) {
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<>();
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;
}
}


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);
}
}
}


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());
}
}
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);
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个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


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;
}
}