Java frequently used data structures and methods for leetcode

Array

• declare
  • int[] a = new int[100];
  • int[] b = {4,1,5};
  • array = new int[]{1,2,3};
  • two-dimensional
    • • code

      int a[][] = {{1,2}, {3,4}};
      

    • • code

      int array[][] = new int[3][];
      array[0] = new int[3];
      array[1] = new int[2];
      array[2] = new int[5];
      

• arr.length, a field on any array, the capacity, not the number of elements no () in the end, a final variable
  • length, length(), size()
    • .length is a field, containing the capacity (NOT the number of elements the array contains at the moment) of arrays.
    • length() is a method used by Strings (amongst others), it returns the number of chars in the String; with Strings, capacity and number of containing elements (chars) have the same value.
    • size() is a method implemented by all members of Collection (lists, sets, stacks,…). It returns the number of elements (NOT the capacity; some collections even don´t have a defined capacity) the collection contains.
• default 0, false, null
• Arrays.toString(myArr);
• Arrays.stream(myArr).sum()
• int maxx = Arrays.stream(myArr).min().getAsInt();
• Arrays.asList(“apple”,“hello”) return a fixed length list
  • • code

               String a[] = new String[] { "A", "B", "C", "D" }; 
                // Getting the list view of Array
                List<String> list = Arrays.asList(a);
    

  • 2d array res to list of list
    • • code

              List<List<Integer>> resList = new ArrayList<>();
              for(int[] rows : res) {
                  resList.add(Arrays.stream(rows).boxed().collect(Collectors.toList()));
              }
      

    • to 1d list
      • • code

        Arrays.stream(array).map(Arrays::asList).collect(Collectors.toList())
        

• Arrays.fill(myarr, -1)
• Arrays.sort(intervals, (a,b)-> a[0]-b[0]); not Collections.sort()
  • Arrays.parallelSort(myArray)
  • sort by end value, from small to big
    • (a, b) -> (a[1] - b[1])
    • • code

              Arrays.sort(points, (a, b) -> {
                  if (a[1] == b[1]) return 0;
                  if (a[1] < b[1]) return -1;
                  return 1;
              });
      

• LinkedList<int[]> merged to two d array
  • • code

    return merged.toArray(new int[merged.size()][]);
    

• copy
  • Arrays.copyOfRange
  • System.arraycopy(nums, 0, newNums, 1, n - 2);
  • copyOf
    • int[] copy = Arrays.copyOf(org, 5); new length 5

String

- string s = s.substring(0,3);  
    - s.substring(begin)
- s.equal(t),
    - == is to check whether they are in the same place, don't use it
- s.length()
  length() method is a final variable which is applicable for string objects
- char c = s.charAt(i);
  get the char at i index
- int s1.indexOf(int ch)
    - int s1.indexOf(int ch, int fromIndex)
    - int s1.indexOf(String substring)
- boolean str.contains(charSequence s)
- s.isEmpty()
- String updated = s.replace(char old, char new)
    - s.replace("abc","$")
    - not in place, the old remains the same, need to pass the return value
- String s1.equalsIgnoreCase(String another)
- String.valueOf(num)
- String s1.toLowerCase()
- String s1.toUpperCase()
- for (char c: str.toCharArray())
- Character.isLowerCase(word.charAt(i))
  isUpperCase
- s.trim()  	removes the beginning and ending spaces of this string.
- String[] words = s.split("+");
- StringBuilder sb = new StringBuilder("abc");
    - sb.append(c);
    - String s = sb.toString();
    - sb.reverse();
    - sb.deleteCharAt(path.length() - 1);

    - sb.setCharAt(0, '$'); // replace
    - sb.insert(sb.length(), '$'); // append
    - StringBuffer() thread-safe

• DecimalFormat
  • 0.00

    System.out.println(df.format(num));```
    

  • #.## 0.2 0.01, no 0 in the end
• String.format("%.2f",num);
  • 56.63, rounded
  • if %.4f, then 123.4123
  • String.format("%02d", seatNum) 01, 02… 12
• String a= String.format("ha %s what %s the number %d, %.2f", str1, str2, int1, double1); %.2f will get 2.40

Collections

Collection<E> P = new "some type"<E>();
Collection<E> Q = new "some type"<E>();

Collections.sort(xxx, comparator)

Comparator<Apple> byWeight = new Comparator<Apple>() {
	public int compare(Apple a1, Apple a2){ return a1.getWeight().compareTo(a2.getWeight());
}};

Comparator<Apple> byWeight = (Apple a1, Apple a2) -> a1.getWeight().compareTo(a2.getWeight());

Collections.sort(values, Collections.reverseOrder());

Collections.binarySearch(list, key)

return the index of key in the list of -1.

Collections.binarySearch(seats, requestedSeat)

int index = Collections.binarySearch(stoneList, newStone);

Collections…

Collections.reverse(seatList)
Collections.min(seatList)
Collections.max(seatList)
Collections.shuffle(seatList)
Collections.copy(des, src)
Collections.swap(seatList, iIndex, jIndex)

ArrayList, Stack

ArrayList

public List<String> myList = new ArrayList<String>();
List<Integer> sub = myList.subList(start, endIndex);
myList.size()
add(item), get(index), set(index, newItem), remove(index), contains(item)
list.getOrDefault(item, 0)
indexOf(item) , -1 if not found

Change to Array and change back

myArr = myArrList.toArray(new String[myArrList.size()])
only String, not int, but Integer

String[] arr = list.toArray(new String[0])

int[] arr = list.stream().mapToInt(i -> i).toArray(); Arrays.stream(ints).boxed().collect(Collectors.toList());

Stack

In Java, Stack is a class that falls under the Collection framework that extends the Vector class. It also implements interfaces List, Collection, Iterable, Cloneable, Serializable.

    Stack<E> stk = new Stack<E>();  

Deque: ArrayDeque, LinkedList

could not traverse it’s values or get a value by it’s position

• peek() the head of the list. read it
  • peekFirst
  • peekLast
• contains()
• offer add to the last, return true
  • offerFirst can return False, better than addFirst()Adds an item to the beginning of the list.T
  • offerLast
  • add(position, item)
• poll retrieve and remove the head
  • pollFirst() This method retrieves and removes the first element of this list, or returns null if this list is empty.
  • pollLast()
  • remove() remove the first one
    • remove(int index) or remove(Object o)
    • removeFirstOccurrence(), return true or false
    • bucket.removeFirstOccurance(Integer.valueOf(key));
    • removeLastOccurrence
    • removeFirst()Remove an item from the beginning of the list.Try it »
    • removeLast()Remove an item from the end of the listTry it »
• toArray LinkedList<int[]> merged to two d array
  • • code

    return merged.toArray(new int[merged.size()][]);
    

• Iterator i = mylinkedList.iterator(); while (i.hasNext()){ i.next(); }
  • if it’s ListIterator rather than Iterator
    • i.previou4 questions from Jias(); i.hasPrevious()
• ArrayDeque
  • Deque queue = new ArrayDeque<>();

Set: HashSet, LinkedHashSet

Since Set is an interface, objects cannot be created of the type Set. We always need a class which extends this list in order to create an object.

Syntax

    Set<String> hs = new HashSet<String>();
    Set<String> lhs = new LinkedHashSet<String>();
    Set<String> ts = new TreeSet<String>();

Itrator Syntax:

 Iterator<String> itr=set.iterator();  
  while(itr.hasNext()){  
   System.out.println(itr.next());  
  }  

s1.constainsAll(s2)
s1.addAll(s2)
s1.removeAll(s2)
s1.retainAll(s2) : intersection, only elements common to both sets, gonna change s1.

• use your own obj in a set or as a key in map, need to overwrite equals and hashcode
  • hashcode determines which bucket the object is going to get into
    • as long as you defind Obj equal has the same hashcode
    • the same obj will always has the same hashcode
  • two object if equal, they must have the same hashcode

  • @ Override
    public boolean equals(Object obj) 
    

Map: HashMap, TreeMap, LinkedHashMap

Map<K,V> m=new HashMap<K,V>();
Map<K,V> map = new LinkedHashMap<K,V>();
Map<K,V> map = new TreeMap<K,V>();

Map.Entry

for (Map.Entry<String,String> entry : gfg.entrySet())
            System.out.println("Key = " + entry.getKey() +
                             ", Value = " + entry.getValue());
}

Frequent map methods

• Map<Integer, String> m = Map.of(2, "a", 3, "b");
• getOrDefault(key, default)
  • • code

    List<Integer> nei = adja.getOrDefault(start, new ArrayList<Integer>());
    

• computeIfAbsent
  • Map<Integer, Stack> group;
  • group.computeIfAbsent(f, z-> new Stack()).push(x);
    • 895. Maximum Frequency Stack
• key should be an immutable object
• languages.put(“Java”, “hello java..");
  • reverseAdjList.putIfAbsent(c, new ArrayList<>());
  • myMap.get(eachKey)
    • languages.get(“Java”);
  • languages.remove(“Lisp”)
  • languages.replace(“lisp”,“more features”)
    • could also replace(key, oldValue, newValue)
• myHashmap.keySet() entrySet()
  • foreach

    for(String key: language.keySet()){
      language.get(key)
    }
    

  • • forEach with lambda

    HashMap<Integer, Integer> m = new HashMap<>();
    m.put(2, 3);
    m.put(3, 4);
    m.forEach((k, v) -> {
        System.out.println(k);
        System.out.println(v);
    });
          
    

• myMap.containsKey(checkKey)
• stream
  • find the maximum value first and retrieve all keys mapping to that value afterwards:
    • • code

      private List<Integer> testStreamMap(Map<Integer, Long> mapGroup) {
          if(mapGroup.isEmpty())
              return Collections.emptyList();
          long max = mapGroup.values().stream().max(Comparator.naturalOrder()).get();
          return mapGroup.entrySet().stream()
              .filter(e -> e.getValue() == max)
              .map(Map.Entry::getKey)
              .collect(Collectors.toList());
      }```
      

  • • code

    return dist.values().stream().max(Comparator.naturalOrder()).get();
    

  • • codek

    Map.Entry<Integer, Long> maxEntry = map.entrySet().stream()
      .max(Map.Entry.comparingByValue()).get();```
    
    

TreeMap, TreeSet

sorted by keys

• code

     scores = new TreeMap<>(Collections.reverseOrder());
     private TreeMap<Integer, Integer>  scores = new TreeMap<>((a, b) -> b - a);

PriorityQueue

Refer to Queue

• init

  • instead of Pair, can use an array

    • • code

              // Create a Priority Queue that measures firstly on strength and then indexes.
              PriorityQueue<int[]> pq = new  PriorityQueue<>((a, b) -> {
                  if (a[0] == b[0]) return b[1] - a[1];
                  else return b[0] - a[0];
              });
      

    • • code

                  int[] entry = new int[]{strength, i};
                  pq.add(entry);
      

  • Pair

    • • code

              PriorityQueue<Pair> q = new PriorityQueue<>(
                  (Pair a, Pair b) -> 
                      a.first == b.first ? (b.second - a.second) : b.first - a.first
              ); // pass the Compartor
      

    • • code

      class Pair{
          int first;
          int second;
          Pair(int first, int second){
              this.first = first;
              this.second = second;
          }
      }
      

    • • code

      class Pair<U, V> {
          public U k;
          public V v;
          public Pair (U k, V v){
              this.k = k;
              this.v = v;
          }
      }
      

      • for Pair<Integer, Integer> p

  • PriorityQueue heap = new PriorityQueue<>(Comparator.reverseOrder()); // In Java, a Heap is represented by a Priority Queue import java.util.Collections; import java.util.PriorityQueue; import java.util.Arrays;

    // Construct an empty Min Heap PriorityQueue minHeap = new PriorityQueue<>();

    // Construct an empty Max Heap PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    // Construct a Heap with initial elements. // This process is named “Heapify”. // The Heap is a Min Heap PriorityQueue heapWithValues= new PriorityQueue<>(Arrays.asList(3, 1, 2));

• poll()
• peek()
• pq.add(xxx)

  Queue<Candidate> pq = new PriorityQueue<>((a,b) -> a.totalEstimate - b.totalEstimate);
  pq.add(new Candidate(0, 0, 1, estimate(0, 0, grid)));
  

• pq.remove(), return the top
• addAll
  • Arrays.asList(factors) returns a List<int[]> where factors is an int array
  • PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->b[1] - a[1]); queue.addAll(Arrays.asList(boxTypes));
    • https://yanjiyu.com/leetcode/1710/
  • error int[] nums; pq; pq.addAll(Arrays.asList(nums));
    • Arrays.asList is expecting a variable number of Object. int is not an Object, but int[] is, thus Arrays.asList(A) will create a List<int[]> with just one element.
    • List<Integer> list = IntStream.of(a).boxed().collect(Collectors.toList());

 PriorityQueue<WorkerBikePair> pq = new PriorityQueue<>(
 (WorkerBikePair a, WorkerBikePair b) -> 
 a.distance == b.distance 
 ? (a.workerIndex == b.workerIndex ? a.bikeIndex - b.bikeIndex : a.workerIndex - b.workerIndex ) 
 : a.distance - b.distance
 );

Math and Integer Class

• Math Integer Random
  • Math
    • Math.abs(a)
    • Math.max(a, b)
    • Math.sqrt(x)
    • Math.pow(a, b)
    • Math.ceil(a)
    • Math.floor(a)
    • Math.random()
      • returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0.
      • Random r = new Random();
      • r.nextInt(n) // // Will generate values b/w 0 to n-1
      • r.nextInt((max-min)+1) + min -Between min and max, inclusive
    • Math.log(2.7) // 2.7 is close to e, which is 1
    • Math.log10(x)
    • Math.sin/cos/tan/asin/acos/atan(double a)
  • Integer
    • Integer.parseInt(String s)
    • Integer.valueOf(String s)
    • Integer.toBinaryString(int i) // pass 4, get 100

Reference:

https://github.com/itsPrasheel/lastMinuteJavaSyntax