头像

sonnen8

Zoom University




离线:17小时前



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


活动打卡代码 LeetCode 386. 字典序排数

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) != ']') {
                res.add(dfs(s));
            }
            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;
    }
}



活动打卡代码 LeetCode 398. 随机数索引

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) {
                b.add(i);
            }
        }
        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);
 */


活动打卡代码 LeetCode 384. 打乱数组

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 {

    /** @param head The linked list's head.
        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) {
        h = 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);
        list.add(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(x).add(py);
        map.get(y).remove(py);
        map.get(y).add(px);
        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)) {
            nums.add(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();
 */


活动打卡代码 AcWing 148. 合并果子

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 ++) {
            heap.add(in.nextInt());
        }

        int res = 0;
        while (heap.size() > 1) {
            int a = heap.poll();
            int b = heap.poll();
            res += a + b;
            heap.add(a + b);
        }
        System.out.println(res);
    }
}