humpydonkey

class Solution {
    private static final int SIZE = 26;
    private static final int[][] DIRECTIONS = new int[][] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    private static final char VISITED_CHAR = '*';
    
    
    // Time: O(mn*3^k)
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        List<String> result = new ArrayList<>();

humpydonkey

class AutocompleteSystem {
    private static final int MAX_RESULT = 3;

    private final TrieNode root;
    private final StringBuilder currInput;
    private TrieNode prevNode;

    // Trie + Min heap
    // Time: O(N), N = number of sentences
    public AutocompleteSystem(String[] sentences, int[] times) {

humpydonkey

class Solution {
    // Time: O(nlogn)
    // Space: O(n)
    public int lastStoneWeight(int[] stones) {
        if (stones.length == 1) {
            return stones[0];
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        for (int weight : stones) {
            queue.add(weight);

humpydonkey

class Solution {
    // We maintain a 2D array , dp[n][subSetSum] 
    // For an array element i and sum j in array nums,
    // dp[i][j]=true if the sum j can be formed by array elements 
    // in subset nums[0]..nums[i], otherwise dp[i][j]=false
    //
    // Time: O(n * sum)
    // Space: O(n * sum)
    public boolean canPartition(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();

humpydonkey

class Solution {
    // A variant of the knapsack problem
    // dp[i][j]: is there a subset of stones (0 to i-1) can sum up to weight j
    // dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
    // result: last stone weight = the shortest distance between any two nodes among dp[n][0] ... dp[n][W] 
    //
    // Time: O(n * totalWeight)
    // Space: O(n * totalWeight)
    public int lastStoneWeightII(int[] stones) {
        int totalWeight = Arrays.stream(stones).sum();

humpydonkey

class Solution {
    // The unbounded knapsack problem
    // dp[i][j]: the fewest # coins among 0 to i-1 to make up to amount j
    // dp[i][j] = min(dp[i-1][j], dp[i-1][j-coins[i]] + 1, dp[i][j-coins[i]] + 1)
    // since dp[i][j-coins[i]] includes dp[i-1][j-coins[i]], thus:
    // dp[i][j] = min(dp[i-1][j],  dp[i][j-coins[i]] + 1)
    // dp[i][j] < 0 means there is no solution.
    // 
    // Time: O(n * amount)
    // Space: O(n * amount)

humpydonkey

class Solution {
    // f(n) = 1 / n + (n - 2) / n * f(n - 1)
    // 
    // f(n) = 1/n                                    -> 1st person picks his own seat
    //      + 1/n * 0                                 -> 1st person picks last one's seat
    //	    + (n-2)/n * (                            ->1st person picks one of seat from 2nd to (n-1)th
    //	      1/(n-2) * f(n-1)                   -> 1st person pick 2nd's seat
    //	      1/(n-2) * f(n-2)                  -> 1st person pick 3rd's seat
    //        ......
    //        1/(n-2) * f(2)                     -> 1st person pick (n-1)th's seat

humpydonkey

{
    "config":
    {
        "background": "#ffffff",
        "axis":
        {
            "labelColor": "#262730",
            "titleColor": "#262730",
            "gridColor": "rgba(38, 39, 48, 0.2)",
            "labelFont": "IBM Plex Sans, sans-serif",

humpydonkey

import logging
import numpy as np
import PIL.Image
from segment_anything import SamPredictor, sam_model_registry
import matplotlib.pyplot as plt

logger = logging.getLogger(__name__)
model_type = "default"
_SAM_CKPT = "sam_vit_h_4b8939.pth"
sam = sam_model_registry[model_type](checkpoint=_SAM_CKPT).to(device="cuda")

humpydonkey

import logging
import numpy as np
import PIL.Image
import matplotlib.pyplot as plt
from datasets import load_dataset
from rembg import remove
import cv2


def show_mask(mask, ax, random_color=False):