Design题选编

251. Flatten 2D Vector

Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.

class Vector2D {

    List<Integer> list;
    Iterator<Integer> iterator;
    public Vector2D(int[][] vec) {
        list=new ArrayList<>();
        for (int[] arrs : vec) {
            for (int arr : arrs) {
                list.add(arr);
            }
        }
        iterator=list.iterator();
    }

    public int next() {
        return iterator.next();
    }

    public boolean hasNext() {
        return iterator.hasNext();
    }
}

295. Find Median from Data Stream

class MedianFinder {

    PriorityQueue<Integer> firstHalf;
    PriorityQueue<Integer> secondHalf;
    int size;
    public MedianFinder() {
        firstHalf=new PriorityQueue<>((a,b)->(b-a));    //2 1 0
        secondHalf=new PriorityQueue<>();               //3 4
        size=0;
    }

    public void addNum(int num) {
        if((size&1)==0){
            firstHalf.offer(num);
        }else{
            secondHalf.offer(num);
        }
        size++;
        while(!secondHalf.isEmpty() && secondHalf.peek()<firstHalf.peek()){
            int second=secondHalf.poll();
            int first=firstHalf.poll();
            secondHalf.offer(first);
            firstHalf.offer(second);
        }
    }

    public double findMedian() {
        if((size&1)==1){
            return firstHalf.peek();
        }
        return (firstHalf.peek()+secondHalf.peek())/2.0;
    }
}

308. Range Sum Query 2D - Mutable

class NumMatrix {

    int[][] sum;
    int row;
    int col;
    int[][] matrix;
    public NumMatrix(int[][] matrix) {
        row=matrix.length;
        col=matrix[0].length;
        this.matrix=matrix;
        sum=new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                sum[i][j]=sumRec(i-1,j)+sumRec(i,j-1)+matrix[i][j]-sumRec(i-1,j-1);
            }
        }
    }

    public void update(int r, int c, int val) {
        int delta=val-matrix[r][c];
        for(int i=r; i<row; i++){
            for(int j=c; j<col; j++){
                sum[i][j]+=delta;
            }
        }
        matrix[r][c]=val;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sumRec(row2,col2)+sumRec(row1-1,col1-1)-sumRec(row1-1,col2)-sumRec(row2,col1-1);
    }

    private int sumRec(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col){
            return 0;
        }
        return sum[i][j];
    }
}

348. Design Tic-Tac-Toe

class TicTacToe {

    int[] row;
    int[] col;
    int diagonal;
    int anti_diagonal;
    int n;
    public TicTacToe(int n) {
        row=new int[n];
        col=new int[n];
        diagonal=0;
        anti_diagonal=0;
        this.n=n;
    }

    public int move(int i, int j, int player) {
        int val=player==2 ? -1 : 1;
        row[i]+=val;
        col[j]+=val;
        //diagonal : top-left to bottom-right
        //anti-diagonal: top-right to bottom-left
        if(i==j){
            diagonal+=val;
        }
        if(i+j==n-1){
            anti_diagonal+=val;
        }
        if(row[i]==n || col[j]==n || diagonal==n || anti_diagonal==n){
            return 1;
        }
        if(row[i]==-n || col[j]==-n ||diagonal==-n || anti_diagonal==-n){
            return 2;
        }
        return 0;
    }
}

384. Shuffle an Array

class Solution {

    int[] nums;
    int[] origin;
    Random rand=new Random();
    public Solution(int[] nums) {
        this.nums=nums;
        this.origin=nums.clone();
    }

    public int[] reset() {
        this.nums=this.origin;
        this.origin=this.origin.clone();
        return nums;
    }

    public int[] shuffle() {
        for (int i = 0; i < nums.length; i++) {
            swap(i,pick(i,nums.length));
        }
        return nums;
    }

    private int pick(int min, int max){
        //[min,max)
        return rand.nextInt(max-min)+min;
    }

    private void swap(int a, int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }
}

588. Design In-Memory File System

class FileSystem {

    Node root;
    public FileSystem() {
        root=new Node();
    }

    public List<String> ls(String path) {
        String[] split = path.split("/");
        //skip split[0] ""
        Node node=root;
        String s=null;
        for (int i = 1; i < split.length; i++) {
            s=split[i];
            node=node.children.get(s);
        }
        if(node.content!=null){
            return new ArrayList<>(Arrays.asList(s));
        }
        return new ArrayList<>(node.children.keySet());
    }

    public void mkdir(String path) {
        getNode(path);
    }


    public void addContentToFile(String filePath, String content) {
        Node node=getNode(filePath);
        if(node.content==null){
            node.content=content;
        }else{
            node.content+=content;
        }
    }

    public String readContentFromFile(String filePath) {
        return getNode(filePath).content;
    }

    private Node getNode(String path){
        String[] split = path.split("/");
        //skip split[0] ""
        Node node=root;
        for (int i = 1; i < split.length; i++) {
            String s=split[i];
            if(!node.children.containsKey(s)){
                node.children.put(s,new Node());
            }
            node=node.children.get(s);
        }
        return node;
    }
}

class Node{
    String content;
    TreeMap<String,Node> children;
    Node(){
        children=new TreeMap<>();
    }
}

1603. Design Parking System

class ParkingSystem {

    int[] lots;
    public ParkingSystem(int big, int medium, int small) {
        lots=new int[4];
        lots[1]=big;
        lots[2]=medium;
        lots[3]=small;
    }

    public boolean addCar(int carType) {
        if(lots[carType]>0){
            lots[carType]--;
            return true;
        }
        return false;
    }
}

2102. Sequentially Ordinal Rank Tracker

https://leetcode.com/problems/sequentially-ordinal-rank-tracker/discuss/1632156/Two-Heaps

class SORTracker {
    PriorityQueue<Pair<String,Integer>> maxHeap;
    PriorityQueue<Pair<String,Integer>> minHeap;
    int count=0;
    public SORTracker() {
        maxHeap=new PriorityQueue<>((a,b)->(!a.getValue().equals(b.getValue()) ? b.getValue()-a.getValue() : a.getKey().compareTo(b.getKey())));
        minHeap=new PriorityQueue<>((a,b)->(!a.getValue().equals(b.getValue()) ? a.getValue()-b.getValue() : b.getKey().compareTo(a.getKey())));
    }

    //minHeap : largest i elements
    public void add(String name, int score) {
        minHeap.offer(new Pair<>(name,score));
        maxHeap.offer(minHeap.poll());
    }

    //i = number of get()
    public String get() {
        Pair pair=maxHeap.poll();
        minHeap.offer(pair);
        return (String)pair.getKey();
    }
}

901. Online Stock Span

class StockSpanner {

    Deque<int[]> stack; //date,value
    int date;
    public StockSpanner() {
        stack=new LinkedList<>();
        date=0;
    }

    //100,80,60,70,60,75,85
    public int next(int price) {
        date++;
        while(!stack.isEmpty() && stack.peek()[1]<=price){
            stack.pop();
        }
        int pre=stack.isEmpty() ? 0 : stack.peek()[0];
        int res=date-pre;
        stack.push(new int[]{date,price});
        return res;
    }
}

170. Two Sum III - Data structure design

class TwoSum {
    Map<Integer,Integer> map;
    public TwoSum() {
        map=new HashMap<>();
    }

    public void add(int number) {
        map.put(number,map.getOrDefault(number,0)+1);
    }

    public boolean find(int value) {
        for (int key : map.keySet()) {
            if(map.containsKey(value-key) && key*2!=value || key*2==value && map.get(key)>1){
                return true;
            }
        }
        return false;
    }
}

281. Zigzag Iterator

public class ZigzagIterator {

    Iterator<Integer> i1;
    Iterator<Integer> i2;
    int turn=1;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        i1=v1.listIterator();
        i2=v2.listIterator();
    }

    public int next() {
        if(turn==1){
            if(i1.hasNext()){
                turn=2;
                return i1.next();
            }else{
                return i2.next();
            }
        }else{
            if(i2.hasNext()){
                turn=1;
                return i2.next();
            }else{
                return i1.next();
            }
        }
    }

    public boolean hasNext() {
        return i1.hasNext() || i2.hasNext();
    }
}

Follow up: What if you are given k vectors? How well can your code be extended to such cases?

public class ZigzagIterator {

    Deque<Iterator> list;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        list = new LinkedList<Iterator>();
        if(!v1.isEmpty()) list.offer(v1.iterator());
        if(!v2.isEmpty()) list.offer(v2.iterator());
    }

    public int next() {
        Iterator poll = list.poll();
        int result = (Integer)poll.next();
        if(poll.hasNext()) list.offer(poll);
        return result;
    }

    public boolean hasNext() {
        return !list.isEmpty();
    }
}

346. Moving Average from Data Stream

class MovingAverage {

    Deque<Integer> q;
    double sum;
    int size;
    public MovingAverage(int size) {
        q=new LinkedList<>();
        sum=0;
        this.size=size;
    }

    public double next(int val) {
        q.offer(val);
        sum+=val;
        if(q.size()>size){
            sum-=q.poll();
        }
        return sum/q.size();
    }
}

359. Logger Rate Limiter

class Logger {

    Map<String,Integer> map;    //nextAllowedTime
    public Logger() {
        map=new HashMap<>();
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        boolean res=true;
        if(map.containsKey(message) && map.get(message)>timestamp){
            res=false;
        }
        if(res){
            map.put(message,timestamp+10);
        }
        return res;
    }
}

362. Design Hit Counter

class HitCounter {
    Deque<Integer> q;
    public HitCounter() {
        q=new LinkedList<>();
    }

    public void hit(int timestamp) {
        q.offer(timestamp);
    }

    public int getHits(int timestamp) {
        //[t-299,t]
        while(!q.isEmpty() && q.peek()<timestamp-299){
            q.poll();
        }
        return q.size();
    }
}

Follow up: What if the number of hits per second could be huge? Does your design scale?

716. Max Stack

并非手撸大根堆

class MaxStack {
    Deque<int[]> stack;
    PriorityQueue<int[]> pq;
    Set<Integer> removed;
    int idx;
    public MaxStack() {
        stack=new LinkedList<>();
        pq=new PriorityQueue<>((a,b)->(a[0]!=b[0] ? b[0]-a[0] : b[1]-a[1]));
        removed=new HashSet<>();
        idx=0;
    }

    public void push(int x) {
        stack.push(new int[]{x,idx});
        pq.offer(new int[]{x,idx});
        idx++;
    }

    public int pop() {
        while(removed.contains(stack.peek()[1])){
            stack.pop();
        }
        int[] cur=stack.pop();
        removed.add(cur[1]);
        return cur[0];
    }

    public int top() {
        while(removed.contains(stack.peek()[1])){
            stack.pop();
        }
        return stack.peek()[0];
    }

    public int peekMax() {
        while(removed.contains(pq.peek()[1])){
            pq.poll();
        }
        return pq.peek()[0];
    }

    public int popMax() {
        while(removed.contains(pq.peek()[1])){
            pq.poll();
        }
        int[] cur=pq.poll();
        removed.add(cur[1]);
        return cur[0];
    }
}

1166. Design File System

注意审题：

value不可修改

class FileSystem {
    Node root;
    public FileSystem() {
        root=new Node();
    }

    public boolean createPath(String path, int value) {
        String[] split = path.split("/");
        Node node=root;
        int n=split.length;
        //["","leetcode"]
        //can not modify
        for (int i = 1; i < n; i++) {
            String s=split[i];
            if(node.children.containsKey(s)){
                node=node.children.get(s);
            }else{
                if(i==n-1){
                    node.children.put(s,new Node());
                    node=node.children.get(s);
                }else{
                    return false;
                }
            }
        }
        if(node.val!=0){
            return false;
        }
        node.val=value;
        return true;
    }

    public int get(String path) {
        String[] split = path.split("/");
        Node node=root;
        int n=split.length;
        //["","leetcode"]
        for (int i = 1; i < n; i++) {
            String s=split[i];
            if(node.children.containsKey(s)){
                node=node.children.get(s);
            }else{
                return -1;
            }
        }
        return node.val;
    }
}

class Node{
    int val;
    Map<String,Node> children;
    Node(){
        children=new HashMap<>();
    }
}

353. Design Snake Game

https://leetcode.com/problems/design-snake-game/discuss/82668/Java-Deque-and-HashSet-design-with-detailed-comments

class SnakeGame {

    Deque<Integer> snake;
    Set<Integer> set;
    int[][] food;
    int row;
    int col;
    int foodIdx;
    int score;
    public SnakeGame(int width, int height, int[][] food) {
        snake=new LinkedList<>();
        set=new HashSet<>();
        this.row=height;
        this.col=width;
        this.food=food;
        foodIdx=0;
        score=0;
        snake.offerFirst(0);
        set.add(0);
    }

    public int move(String direction) {
        if(score==-1){
            return -1;
        }
        int head=snake.isEmpty() ? 0 : snake.peekFirst();
        int i=head/col;
        int j=head%col;
        switch (direction){
            case "U":
                i--;
                break;
            case "D":
                i++;
                break;
            case "L":
                j--;
                break;
            default:
                j++;
        }
        set.remove(snake.peekLast());
        int next=i*col+j;
        if(i<0 || i>=row || j<0 || j>=col || set.contains(next)){
            score=-1;
            return -1;
        }
        set.add(next);
        snake.offerFirst(next);
        if(foodIdx<food.length){
            int x=food[foodIdx][0];
            int y=food[foodIdx][1];
            if(x==i && y==j){
                set.add(snake.peekLast());
                foodIdx++;
                return ++score;
            }
        }
        snake.pollLast();
        return score;
    }
}

489. Robot Room Cleaner

public class LeetCode489 {
     interface Robot {
      // Returns true if the cell in front is open and robot moves into the cell.
              // Returns false if the cell in front is blocked and robot stays in the current cell.
              public boolean move();

              // Robot will stay in the same cell after calling turnLeft/turnRight.
              // Each turn will be 90 degrees.
              public void turnLeft();
      public void turnRight();

              // Clean the current cell.
              public void clean();
    }


    Set<String> visited=new HashSet<>();
     //clockwise: u, r, d, l
     int[][] dirs=new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    private void goBack(Robot robot){
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }

    private void dfs(Robot robot, int i, int j, int d){
        visited.add(i+","+j);
        robot.clean();
        for (int k = 0; k < 4; k++) {
            int idx=(d+k)%4;
            int x=i+dirs[idx][0];
            int y=j+dirs[idx][1];
            String s=x+","+y;
            if(!visited.contains(s) && robot.move()){
                dfs(robot,x,y,idx);
                goBack(robot);
            }
            robot.turnRight();
        }
    }

    public void cleanRoom(Robot robot) {
        dfs(robot,0,0,0);
    }
}

1265. Print Immutable Linked List in Reverse

 interface ImmutableListNode {
  public void printValue(); // print the value of this node.
  public ImmutableListNode getNext(); // return the next node.
}


public void printLinkedListInReverse(ImmutableListNode head) {
    ImmutableListNode p=head;
    Deque<ImmutableListNode> stack=new LinkedList<>();
    while(p!=null){
        stack.push(p);
        p=p.getNext();
    }
    while(!stack.isEmpty()){
        stack.pop().printValue();
    }
}

Could you solve this problem in:

Constant space complexity?
- O(n^2) time complexity, for loop, each time print ith Node
Linear time complexity and less than linear space complexity?
- split into sub linklists

1429. First Unique Number

class FirstUnique {

    Set<Integer> past;
    LinkedHashSet<Integer> set;
    public FirstUnique(int[] nums) {
        past=new HashSet<>();
        set=new LinkedHashSet<>();
        for (int num : nums) {
            if(!set.contains(num)){
                if(!past.contains(num)){
                    set.add(num);
                }
            }else{
                set.remove(num);
                past.add(num);
            }
        }
    }

    public int showFirstUnique() {
        if(set.size()>0){
            return set.iterator().next();
        }
        return -1;
    }

    public void add(int num) {
        if(!set.contains(num)){
            if(!past.contains(num)){
                set.add(num);
            }
        }else{
            set.remove(num);
            past.add(num);
        }
    }
}

715. Range Module

class RangeModule {
    TreeMap<Integer,Integer> map;   //<start,end>
    public RangeModule() {
        map=new TreeMap<>();
    }

    public void addRange(int left, int right) {
        //no overlaps
        Integer start=map.floorKey(left);
        if(start!=null && map.get(start)>=left){
            left=start;
        }
        Integer end=map.floorKey(right);
        if(end!=null && map.get(end)>right){
            right=map.get(end);
        }
        //expand the range as far as possible
        map.put(left,right);
        //remove any subrange in between
        map.subMap(left,false,right,true).clear();
    }

    public boolean queryRange(int left, int right) {
        Integer start=map.floorKey(left);
        return start==null ? false : map.get(start)>=right;
    }

    public void removeRange(int left, int right) {
        Integer start=map.floorKey(left);
        Integer end=map.floorKey(right);

        //can not reverse order
        if(end!=null && map.get(end)>right){
            map.put(right,map.get(end));
        }
        if(start!=null && map.get(start)>left){
            map.put(start,left);
        }
        map.subMap(left,true,right,false).clear();
    }
}

1352. Product of the Last K Numbers

思路：

与prefix sum不同，0之前的所有prefix product无意义，遇0则清
队头设初值1,便于计算

class ProductOfNumbers {

    List<Integer> prefix;
    public ProductOfNumbers() {
        prefix=new ArrayList<>();
        prefix.add(1);
    }

    public void add(int num) {
        if(num==0){
            prefix.clear();
            prefix.add(1);
        }else{
            prefix.add(prefix.get(prefix.size()-1)*num);
        }
    }

    public int getProduct(int k) {
        int n=prefix.size();
        //last k: [n-k,n-1]
        return n>k ? prefix.get(n-1)/prefix.get(n-k-1) : 0;
    }
}

895. Maximum Frequency Stack

class FreqStack {

    Map<Integer,Integer> numToFreq;
    Map<Integer, Deque<Integer>> freqToStack;
    int maxFreq;
    public FreqStack() {
        numToFreq=new HashMap<>();
        freqToStack=new HashMap<>();
        maxFreq=0;
    }

    public void push(int val) {
        int f=numToFreq.getOrDefault(val,0);
        f++;
        maxFreq=Math.max(maxFreq,f);
        freqToStack.putIfAbsent(f,new LinkedList<>());
        numToFreq.put(val,f);
        freqToStack.get(f).push(val);
    }

    public int pop() {
        int x=freqToStack.get(maxFreq).pop();
        numToFreq.put(x,maxFreq-1);
        if(freqToStack.get(maxFreq).isEmpty()){
            maxFreq--;
        }
        return x;
    }
}

1628. Design an Expression Tree With Evaluate Function

binary expression tree

https://leetcode.com/problems/design-an-expression-tree-with-evaluate-function/discuss/1209901/Java-Factory-method-pattern

factory pattern

import java.util.Deque;
import java.util.LinkedList;

/**
 * This is the interface for the expression tree Node.
 * You should not remove it, and you can define some classes to implement it.
 */

abstract class Node {
    public abstract int evaluate();
    // define your fields here
    public static Node from(String s){
        switch (s){
            case "+":
                return new AddNode();
            case "-":
                return new SubtractNode();
            case "*":
                return new MultiplyNode();
            case "/":
                return new DivideNode();
            default:
                return new NumberNode(s);
        }
    }
};

abstract class OperatorNode extends Node{
    protected Node left;
    protected Node right;
    public void setLeft(Node left){
        this.left=left;
    }
    public void setRight(Node right){
        this.right=right;
    }
}

class AddNode extends OperatorNode{
    @Override
    public int evaluate() {
        return left.evaluate()+right.evaluate();
    }
}

class SubtractNode extends OperatorNode{
    @Override
    public int evaluate() {
        return left.evaluate()-right.evaluate();
    }
}

class MultiplyNode extends OperatorNode{
    @Override
    public int evaluate() {
        return left.evaluate()*right.evaluate();
    }
}

class DivideNode extends OperatorNode{
    @Override
    public int evaluate() {
        return left.evaluate()/ right.evaluate();
    }
}

class NumberNode extends Node{
    private String val;

    NumberNode(String val){
        this.val=val;
    }

    @Override
    public int evaluate() {
        return Integer.valueOf(val);
    }
}


/**
 * This is the TreeBuilder class.
 * You can treat it as the driver code that takes the postinfix input
 * and returns the expression tree represnting it as a Node.
 */

class TreeBuilder {
    Node buildTree(String[] postfix) {
        Deque<Node> stack=new LinkedList<>();
        for (String s : postfix) {
            Node n=Node.from(s);
            if(n instanceof NumberNode){
                stack.push(n);
            }else if(n instanceof OperatorNode){
                OperatorNode op=(OperatorNode)n;
                op.setRight(stack.pop());
                op.setLeft(stack.pop());
                stack.push(op);
            }
        }
        return stack.pop();
    }
};


/**
 * Your TreeBuilder object will be instantiated and called as such:
 * TreeBuilder obj = new TreeBuilder();
 * Node expTree = obj.buildTree(postfix);
 * int ans = expTree.evaluate();
 */

2336. Smallest Number in Infinite Set

class SmallestInfiniteSet {

    Set<Integer> poped;
    int smallest;
    public SmallestInfiniteSet() {
        poped=new HashSet<>();
        smallest=1;
    }

    public int popSmallest() {
        while(poped.contains(smallest)){
            smallest++;
        }
        int p=smallest;
        poped.add(smallest);
        smallest++;
        return p;
    }

    public void addBack(int num) {
        if(poped.contains(num)){
            poped.remove(num);
        }
        if(num<smallest){
            smallest=num;
        }
    }
}

981. Time Based Key-Value Store

class TimeMap {

    Map<String, TreeMap<Integer,String>> keyToMap;
    public TimeMap() {
        keyToMap=new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        keyToMap.putIfAbsent(key,new TreeMap<>());
        keyToMap.get(key).put(timestamp,value);
    }

    public String get(String key, int timestamp) {
        if(!keyToMap.containsKey(key)){
            return "";
        }
        Integer k = keyToMap.get(key).floorKey(timestamp);
        return k==null ? "" : keyToMap.get(key).get(k);
    }
}

2034. Stock Price Fluctuation

class StockPrice {

    TreeMap<Integer,Integer> map;
    TreeMap<Integer,Integer> count;
    public StockPrice() {
        map=new TreeMap<>();
        count=new TreeMap<>();
    }

    public void update(int timestamp, int price) {
        if(map.containsKey(timestamp)){
            int old=map.get(timestamp);
            int c=count.get(old);
            if(c==1){
                count.remove(old);
            }else{
                count.put(old,c-1);
            }
        }
        map.put(timestamp,price);
        count.put(price,count.getOrDefault(price,0)+1);
    }

    public int current() {
        Integer last=map.lastKey();
        return map.get(last);
    }

    public int maximum() {
        return count.lastKey();
    }

    public int minimum() {
        return count.firstKey();
    }
}

729. My Calendar I

Google似乎很喜欢考TreeMap

class MyCalendar {

    TreeMap<Integer,Integer> map;
    public MyCalendar() {
        map=new TreeMap<>();
    }

    public boolean book(int start, int end) {
        int st=start;
        int ed=end;
        Integer floor=map.floorKey(st);
        Integer ceil=map.ceilingKey(st);
        if(floor!=null && map.get(floor)>st ||
            ceil!=null && ceil<ed){
            return false;
        }
        if(floor!=null && map.get(floor)==st){
            start=floor;
            map.remove(floor);
        }
        if(ceil!=null && ceil==ed){
            end=map.get(ceil);
            map.remove(ceil);
        }
        map.put(start,end);
        return true;
    }
}

1570. Dot Product of Two Sparse Vectors

class SparseVector {

    Map<Integer,Integer> map;
    SparseVector(int[] nums) {
        map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                map.put(i,nums[i]);
            }
        }
    }

    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int res=0;
        for (Integer i : vec.map.keySet()) {
            if(this.map.containsKey(i)){
                res+=vec.map.get(i)*this.map.get(i);
            }
        }
        return res;
    }
}

1396. Design Underground System

class UndergroundSystem {
    Map<Integer,String> startStation;// <id,startStation>
    Map<Integer,Integer> startTime;//<id,time>
    Map<String,double[]> map;//<path,[total,count]>
    public UndergroundSystem() {
        startStation=new HashMap<>();
        startTime=new HashMap<>();
        map=new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        startStation.put(id,stationName);
        startTime.put(id,t);
    }

    public void checkOut(int id, String stationName, int t) {
        int t1=startTime.get(id);
        String s1=startStation.get(id);
        String s=s1+","+stationName;
        double[] arr=new double[2];
        arr[0]=0;
        arr[1]=0;
        if(map.containsKey(s)){
            arr=map.get(s);
        }
        arr[0]+=t-t1;
        arr[1]++;
        map.put(s,arr);
    }

    public double getAverageTime(String startStation, String endStation) {
        String s=startStation+","+endStation;
        double[] arr=map.get(s);
        return arr[0]/arr[1];
    }
}

1146. Snapshot Array

TLE: 67/74

class SnapshotArray {

    Map<Integer,Integer>[] map;
    int[] arr;
    int snap=0;
    public SnapshotArray(int length) {
        map=new Map[length];
        arr=new int[length];
        for (int i = 0; i < length; i++) {
            map[i]=new HashMap<>();
        }
    }

    public void set(int index, int val) {
        arr[index]=val;
    }

    public int snap() {
        for (int i = 0; i < map.length; i++) {
            map[i].put(snap,arr[i]);
        }
        return snap++;
    }

    public int get(int index, int snap_id) {
        return map[index].get(snap_id);
    }
}

TLE: 69/74

class SnapshotArray {

    TreeMap<Integer,Integer>[] map;
    int[] arr;
    int snap=0;
    public SnapshotArray(int length) {
        map=new TreeMap[length];
        arr=new int[length];
        for (int i = 0; i < length; i++) {
            map[i]=new TreeMap<>();
        }
    }

    public void set(int index, int val) {
        arr[index]=val;
    }

    public int snap() {
        for (int i = 0; i < map.length; i++) {
            Integer pre=map[i].floorKey(snap);
            if(pre==null || map[i].get(pre)!=arr[i]){
                map[i].put(snap,arr[i]);
            }
        }
        return snap++;
    }

    public int get(int index, int snap_id) {
        int key=map[index].floorKey(snap_id);
        return map[index].get(key);
    }
}

class SnapshotArray {

    TreeMap<Integer,Integer>[] map;
    int snap=0;
    public SnapshotArray(int length) {
        map=new TreeMap[length];
        for (int i = 0; i < length; i++) {
            map[i]=new TreeMap<>();
            map[i].put(0,0);
        }
    }

    public void set(int index, int val) {
        map[index].put(snap,val);
    }

    public int snap() {
        return snap++;
    }

    public int get(int index, int snap_id) {
        return map[index].floorEntry(snap_id).getValue();
    }
}