sonnen8

Zoom University

1549

sonnen8
7个月前
class Solution {
public boolean validUtf8(int[] data) {
int left = 0;
for (int d : data) {
if (left == 0) {
if ((d >> 3) == 0b11110) left = 3;
else if ((d >> 4) == 0b1110) left = 2;
else if ((d >> 5) == 0b110) left = 1;
else if ((d >> 7) == 0b0) left = 0;
else return false;
}
else {
if ((d >> 6) != 0b10) return false;
left --;
}
}
return left == 0;
}
}


sonnen8
7个月前
class Solution {
public int lengthLongestPath(String input) {
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
stack.push(0);
for (String s : input.split("\n")) {
int lev = s.lastIndexOf("\t") + 1;
while (lev + 1 < stack.size()) stack.poll();
int len = stack.peek() + s.length() - lev + 1;
stack.push(len);
if (s.contains(".")) res = Math.max(res, len - 1);
}
return res;
}
}


sonnen8
7个月前
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> lexicalOrder(int n) {
for (int i = 1; i <= 9; i ++) dfs(i, n);
return res;
}
public void dfs(int cur, int n) {
if (cur <= n) res.add(cur);
else return;
for (int i = 0; i <= 9; i ++) dfs(cur * 10 + i, n);
}
}


sonnen8
7个月前
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*     // Constructor initializes an empty nested list.
*     public NestedInteger();
*
*     // Constructor initializes a single integer.
*     public NestedInteger(int value);
*
*     // @return true if this NestedInteger holds a single integer, rather than a nested list.
*     public boolean isInteger();
*
*     // @return the single integer that this NestedInteger holds, if it holds a single integer
*     // Return null if this NestedInteger holds a nested list
*     public Integer getInteger();
*
*     // Set this NestedInteger to hold a single integer.
*     public void setInteger(int value);
*
*     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
*     public void add(NestedInteger ni);
*
*     // @return the nested list that this NestedInteger holds, if it holds a nested list
*     // Return null if this NestedInteger holds a single integer
*     public List<NestedInteger> getList();
* }
*/
class Solution {
int u;
public NestedInteger deserialize(String s) {
u = 0;
return dfs(s);
}

public NestedInteger dfs(String s) {
NestedInteger res = new NestedInteger();

if (s.charAt(u) == '[') {
u++;
while (s.charAt(u) != ']') {
}
u++;
if (u < s.length() && s.charAt(u) == ',') {
u++;
}
} else {
int k = u;
while (k < s.length() && s.charAt(k) != ',' && s.charAt(k) != ']') {
k++;
}
int t = Integer.parseInt(s.substring(u, k));
res.setInteger(t);
if (k < s.length() && s.charAt(k) == ',') {
k++;
}
u = k;
}

return res;
}
}



sonnen8
7个月前
class Solution {
int[] a;
List<Integer> b;
Random rand = new Random();
public Solution(int[] nums) {
a = nums;
b = new ArrayList<>();
}

public int pick(int target) {
for (int i = 0; i < a.length; i ++) {
if (a[i] == target) {
}
}
return b.get(rand.nextInt(b.size()));
}
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/


sonnen8
7个月前
class Solution {
int[] a;
Random rand = new Random();
public Solution(int[] nums) {
a = nums;
}

/** Resets the array to its original configuration and return it. */
public int[] reset() {
return a;
}

/** Returns a random shuffling of the array. */
public int[] shuffle() {
int n = a.length;
int[] b = a.clone();
for (int i = 0; i < n; i ++) {
int j = i + rand.nextInt(n - i);
int t = b[i];
b[i] = b[j];
b[j] = t;
}
return b;
}

}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/


sonnen8
7个月前
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {

Note that the head is guaranteed to be not null, so it contains at least one node. */
ListNode h;
Random rand = new Random();

public Solution(ListNode head) {
}

/** Returns a random node's value. */
public int getRandom() {
int c = -1, n = 0;
for (var p = h; p != null; p = p.next) {
n++;
if (rand.nextInt(n) % n == 0) c = p.val;

}
return c;
}
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/


sonnen8
7个月前
class RandomizedCollection {
Random rand = new Random();
Map<Integer, Set<Integer>> map;
List<Integer> list;
/** Initialize your data structure here. */
public RandomizedCollection() {
map = new HashMap<>();
list = new ArrayList<>();
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int x) {
boolean res = map.containsKey(x);
map.computeIfAbsent(x, l -> new HashSet<>()).add(list.size() - 1);
return !res;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int x) {
if (!map.containsKey(x) || map.get(x).size() == 0) return false;
int y = list.get(list.size() - 1);
int px = map.get(x).iterator().next(), py = list.size() - 1;
Collections.swap(list, px, py);
map.get(x).remove(px);
map.get(y).remove(py);
map.get(x).remove(py);
list.remove(list.size() - 1);
return true;
}

/** Get a random element from the collection. */
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}

/**
* Your RandomizedCollection object will be instantiated and called as such:
* RandomizedCollection obj = new RandomizedCollection();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/


sonnen8
7个月前
class RandomizedSet {
Map<Integer, Integer> hash;
List<Integer> nums;
Random rand = new Random();

/** Initialize your data structure here. */
public RandomizedSet() {
hash = new HashMap<>();
nums = new ArrayList<>();
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int x) {
if (!hash.containsKey(x)) {
hash.put(x, nums.size() - 1);
return true;
}
return false;

}

/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int x) {
if (hash.containsKey(x)) {
int y = nums.get(nums.size() - 1);
int px = hash.get(x);
nums.set(px, y);
hash.put(y, px);
nums.remove(nums.size() - 1);
hash.remove(x);
return true;
}
return false;
}

/** Get a random element from the set. */
public int getRandom() {
return nums.get(rand.nextInt(nums.size()));
}
}

/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/


sonnen8
7个月前
import java.util.*;

class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();

PriorityQueue<Integer> heap = new PriorityQueue<>();

for (int i = 0; i < n; i ++) {