Java for DSA (杀穿Java Coding面试!)
⚠️ Unless imported, all of the classes/package in this note are built-in/ready to use
Note that the problem-solving function has to be modified with
statickeyword to be called inside the Solution class without instantiating the class!Review Quizlet flashcard sets!
Major Types/Classes
Primitive types
Note: if estimated maximum representation value of a number is too large, for example
1 ≤ nums[i] ≤ 10^9, then uselongto represent the large number.Note: for generic type slot
T,K,V, a class type is required. So we can use the wrapper class type when using a primitive data type.| Column 1 | Column 2 | Column 3 |
| --------- | ---------- | ---------- |
| Data 1 | Data 2 | Data 3 |
| Data 4 | Data 5 | Data 6 |
| Data 7 | Data 8 | Data 9 |
| primitive |
byte|short|int|long| | --- | --- | --- | --- | --- | | class type |Byte|Short|Integer|Long| | size on disk | 1 | 2 | 4 | 8 | | data range | -128 to 127 | -32,768 to 32,767 | -2,147,483,648 to 2,147,483,647 | -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 || primitive |
float|double|char|boolean| | --- | --- | --- | --- | --- | | class type |Float|Double|Character|Boolean| | size on disk | 4 | 8 | 2 | 4 as variable; 1 in array | | data range | 6 to 7 decimal digits | 15 decimal digits | ASCII values(256) | true/false |Array(reference data type)
Arrays are mutable but of fixed size.
Default value of arrays: 0; works out the same with 2-D arrays
Basics
int[] arrInt = {0, 1, 2, 3}; String[] arrStr = {"a", "b", "c"}; int[] array = new int[n]; // allocate memory space with size n; arrInt[1] // returns the value of index 1 arrInt[1] = 0; // set value to index 1 arrInt.lengthSort & Copy (import class Arrays)
import java.util.Arrays; Arrays.sort(arrInt); Arrays.sort(arrInt, fromIdx, toIdx); // sort a subarray [fromIdx, toIdx) // create new array of 'size' // if created array is larger than original, create default 0 values in slots // if created array is smaller than original, pick the first 'size' elements int[] arr2 = Arrays.copyOf(arr, size); // copy of subarray from [fromIdx, toIdx) int[] arr3 = Arrays.copyOfRange(arr, fromIdx, toIdx);2D array
int[][] arrayName = new int[rows][columns]; arrayName[0][0] = 1; arrayName[0][1] = 2; ... arrayName[2][2] = 9; // initialization int[][] arrayName = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; // initialization at declaration // Print the array elements for (int i = 0; i < arrayName .length; i++) { for (int j = 0; j < arrayName [i].length; j++) { System.out.print(arrayName [i][j] + " "); } System.out.println(); } // Sort the array by the first index Arrays.sort(array, new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { return Integer.compare(a[0], b[0]); } });Object array
String(reference data type)
Objects of String class are immutable. Every modifying operation creates a new object. So we use array to extensively operate the String object.
char cannot be converted into String like in Python, use
Character.toString().Only use
“ ”to wrap Strings, because‘ ’is for chars.
String str = "Hello";
str.charAt(idx); // value of the char at idx
str.substring(int beginIdx, int endIdx); // substring from [beginIdx, endIdx)
str.substring(int index); // remove the substring before index
str.indexOf('e'); // idx of first occurence of char 'e'
str.indexOf('ell') // idx of first occurence of string 'ell'
str.length(); // return the length
str.equals(str2); // whether two strings are the same
str = str1 + str2; // str concatenation
str = "a" + "bc"; // must use double quote symbol to operate strings
str.trim(); // remove whitespaces on both ends of the string
Variable declared as interface, but to receive an instance of the class that implements it.
// this is a common practice, we can use a implementing class instance // to provide initial value to a interface-declared variable // to be added: what is the benefit of doing this? List<Integer> list = new ArrayList<Integer>(); // we can also just declare it first and add Type to it later List<Integer> list = new ArrayList<>(); list.add(3);instantiation syntax in return statement
return new ArrayList<>(hashMap.values());
Java Collections Framework(in java.util Package)
Note:
List<T>is an interface, and when interface appears in the return type of a Java method, just return object of one of the concrete classes that implement theList<T>interface.Loop through a Collection:
ArrayList (insertion) ordered, duplicated collection, can be used for random(index) access
Official Documentation
difference between array and ArrayList
| Basis | Array | ArrayList | | | --- | --- | --- | --- | | Definition | An array is a dynamically-created object. It serves as a container that holds the constant number of values of the same type. It has a contiguous memory location. | The ArrayList is a class of Java Collections framework. It contains popular classes like Vector, HashTable, and HashMap. | | | Static/ Dynamic | Array is static in size. | ArrayList is dynamic in size. | | | Resizable | An array is a fixed-length data structure. | ArrayList is a variable-length data structure. It can be resized itself when needed. | | | Initialization | It is mandatory to provide the size of an array while initializing it directly or indirectly. | We can create an instance of ArrayList without specifying its size. Java creates ArrayList of default size. | | | Performance | It performs fast in comparison to ArrayList because of fixed size. | ArrayList is internally backed by the array in Java. The resize operation in ArrayList slows down the performance. | | | Primitive/ Generic type | An array can store both objects and primitives type. | We cannot store primitive type in ArrayList. It automatically converts primitive type to object. | | | Iterating Values | We use for loop or for each loop to iterate over an array. | We use an iterator to iterate over ArrayList. | | | Type-Safety | We cannot use generics along with array because it is not a convertible type of array. | ArrayList allows us to store only generic/type, that's why it is type-safe. | | | Length | Array provides a length variable which denotes the length of an array. | ArrayList provides the size() method to determine the size of ArrayList. | | | Adding Elements | We can add elements in an array by using the assignment operator. | Java provides the add() method to add elements in the ArrayList. | | | Single/Multi-Dimensional | Array can be multi-dimensional. | ArrayList is always single-dimensional. | |
Basics
import java.util.ArrayList; ArrayList<Integer> numArr = new ArrayList<Integer>(); ArrayList<int[]> arrOfArr = new ArrayList<int[]>(); import java.util.Arrays; ArrayList<Integer> arr = new ArrayList(Arrays.asList(1, 2, 3, 4, 5)); numArr.add(0); // appends 0 at the tail numArr.add(new int[]{1, 2, 3}); // adds an int array numArr.get(1); // returns the element at index 1 numArr.set(2, 3); // sets element at index 2 to values 3 numArr.remove(4); // removes element at index 3 numArr.remove(numArr.size() - 1); numArr.size(); // returns length of the arraylist numArr.clear(); // removes all the elementsSort
import java.util.Collections; Collections.sort(numArr); // ascending order Collections.sort(numArr, Collections.reverseOrder());Loop through
for(int i; i < arraylist_name.size(); i++){ // current item is arrayList.get(i) } for(Integer item: arraylist_name){ // current item is item }Conversion between array and ArrayList
import java.util.Arrays; Integer[] arr = new arr[]{1, 2, 3, 4, 5}; ArrayList<T> arrayList= new ArrayList<T>(Arrays.asList(array_name)); int[] arr = arrayList.toArray();Reverse
import java.util.Collections; ArrayList<Integer> arrList= new ArrayList<>(); Collections.reverse(arrList);
ArrayDeque (insertion) ordered, duplicated collection, very versatile data structure, can be used for queue, stack & deque(double end)
import java.util.ArrayDeque; // use as a stack (First-in, First-out) Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); // pushes an element into the stack stack.pop(); // removes and returns the element at the top of the stack stack.peek(); // returns (but doesn't remove) the element at the top of the stack // use as a queue (Last-in, First-out) Queue<Integer> queue = new ArrayDeque<>(); queue.offer(10); // addes an element into the queue queue.poll(); // removes and returns the element at the front of the queue queue.peek(); // returns (but doesn't remove) the element at the front of the queue. // use as a deque (Double-Ended Queue) Deque<Integer> deque = new ArrayDeque<>(); deque.addFirst(10); deque.addLast(20); deque.removeFirst(); deque.removeLast(); deque.peekFirst(); deque.peekLast(); // other functions deque.size() deque.isEmpty() deque.clear() Object[] toArray() <T> T[] toArray(T[] a) String[] stringArray = deque.toArray(new String[0]);PriorityQueue (priority) ordered, duplicated, use as a max/min or customized heap
- Basics
import java.util.PriorityQueue;
// by default, PriorityQueue generates a min heap
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
minHeap.add(4);
minHeap.peek(); // return the element on the peak(smallest by default)
minHeap.poll(); // pop out and return the element on the peak
minHeap.contains(element); // check membership
minHeap.remove(4); // remove one instance of an element
minHeap.size(); // like other container classes, it returns the size fo
int[] arr = minHeap.toArray();
// in this way, the heap has a Comparator that reverses comparsion
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
Note: by default, the type used for
PriorityQueuemust implementComparableinterface, if not(for example String), provide aComparatorobject at the time of instantiation.For user-defined types, the requirement is the same as above.
PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s2.compareTo(s1); // Reverse order
}
});
HashSet unordered, unique collection
Basics
import java.util.HashSet; HashSet<Integer> nums = new HashSet<Integer>(); HashSet<String> cars = new HashSet<String>(); cars.add("Volvo"); // add "Volvo" if it doesn't exist in cars cars.contains("Mazda"); // check "Mazda" membership for (String i : cars) { System.out.println(i); } //size(), clear(): similar to ArrayListSet Arithmetic
Set<Integer> set1 = new HashSet<>(); Set<Integer> set2 = new HashSet<>(); set1.addAll(set2); // set1 = set1 + set2, returns a boolean indicating changes set1.removeAll(set2); // set1 = set1 - set2 set1.retainAll(set2); // set1 = set1 [intersect] set2De-duplicate an array with HashSet
Set<Integer> set = new HashSet<>(); for (int num: arr) { set.add(num); } int[] res = new int[set.size()]; int i = 0; for (int num : set) { res[i++] = num; }
HashMap<K, V> unordered, (key) unique map
import java.util.HashMap; // Import the HashSet class // note: cannot be a primitive type HashSet<Integer, Integer> nums = new HashSet<Integer>(); HashMap<String, String> capitalCities = new HashMap<String, String>(); capitalCities.put("England", "London"); capitalCities.get("England"); // get value with key capitalCities.remove("England"); // remove pair with key capitalCities.containsKey("England"); // Print values for (String i : capitalCities.values()) { System.out.println(i); } // Print keys and values for (String i : capitalCities.keySet()) { System.out.println("key: " + i + " value: " + capitalCities.get(i)); } //size(), clear(): similar to ArrayList
\==================== Not Often Used ====================
LinkedList (insertion) ordered, duplicated collection, can be used as a FIFO queue
import java.util.LinkedList; List<String> cars = new LinkedList<String>(); cars.add("Volvo"); cars.addFirst() // Adds an item to the beginning of the list cars.addLast() // Add an item to the end of the list cars.removeFirst() // Remove an item from the beginning of the list cars.removeLast() // Remove an item from the end of the list cars.getFirst() // Get the item at the beginning of the list cars.getLast() // Get the item at the end of the listStack (insertion) ordered, duplicated collection, can be used as a LIFO stack
import java.util.Stack; List<String> cars = new LinkedList<String>(); cars.add("Volvo"); cars.addFirst() // Adds an item to the beginning of the list cars.addLast() // Add an item to the end of the list cars.removeFirst() // Remove an item from the beginning of the list cars.removeLast() // Remove an item from the end of the list cars.getFirst() // Get the item at the beginning of the list cars.getLast() // Get the item at the end of the listTreeSet/TreeMap<K, V> (sorting) ordered, unique collection/(key) map
LinkedHashSet/LinkedHashMap<K, V> (insertion) ordered, unique collection/(key) map
Conversions
int ↔️ string
int num = 123; String str = Integer.toString(num); String str2 = "123"; int num2 = Integer.parseInt(str2);char → string
char ch = 'H'; String str= Character.toString(ch);bool ↔️ int
int i = bool ? 1 : 0 boolean b = (i == 1)int ↔️ char
char digitChar = '5'; int numericValue = Character.getNumericValue(digitChar); int digit = 5; char charFromDigit = Character.forDigit(digit, 10);The integer value of a char is its ASCII value; the char value of an integer is its char representation in ACSII. We can directly do arithmetic operations.
'c' - 'a' // 2 97 - 'a' // 0char array ↔️ string
char[] charArray = {'H', 'e', 'l', 'l', 'o'}; String str = new String(charArray); String str = "Hello"; char[] charArray = str.toCharArray();char ↔️ ASCII value
char character = 'A'; int asciiValue = (int) character; int asciiValue = 65; char character = (char) asciiValue;array → ArrayList (not used very often, requires the array to be declared to be
Integer)Integer[] arr = new Integer[10]; ArrayList<Integer> arraylist_name= new ArrayList<>(Arrays.asList(arr));
Other Operations
Division (between integer, results in integer)
integer division
int c = 5 / 2; // 2float division (between integer, results in a ratio)
double c = (double) a / (double) b;
Logical Operators
&&logical AND (will skip the second decision if the first is wrong)||logical OR (will skip the second decision if the first is correct)!logical NOT==whether the two sides equals
Calculate power of a number
int b = (int) Math.pow(2, 3); // because pow() returns doubleCompare value in
ifstatementbetween two primitive values
==whether value is null
val == null
Compare String, Array
For objects like String and Array,
==compares the reference to the object, not the value!Note that only in classes like String that overrides
equals()method of Object class will compare the actual content or otherwise compare reference like==do, which is the default in Object class.equals still compares references in arrays!Compare Strings
String a = new String("沉默王二"); String b = new String("沉默王二"); // 使用 == 比较 System.out.println(a == b); // 输出 false，因为 a 和 b 引用不同的对象 // 使用 equals() 比较 System.out.println(a.equals(b)); // 输出 true，因为 a 和 b 的内容相同Compare Arrays
import java.util.Arrays; int[] arr1 = {1, 2, 3}; int[] arr2 = {1, 2, 3}; arr1 == arr2 // compare references arr1.equals(arr2) // compare references Arrays.equals(arr1, arr2) // compare array contents
Utility Methods
Math methods(built-in)
Math.abs(-1); // returns 1 Math.min(a, b); Math.max(a, b); Math.random(); // returns double in range [0, 1)Random (need to import and instantiate)
import java.util.Random; Random rand = new Random(); // because the methods are non-static int rand_int = rand.nextInt(1000); // integer in [0, 1000) double rand_dub = rand.nextDouble(); // double in [0, 1)
Syntax Sugars
- use
?and:to create conditional output
return cond ? 0 : result; // cond is true, return 0; cond is false, return result
Forced pass-by-value and pass-by-reference
By default, the Java passes the primitive data types by value and passes reference data types by reference(address of the object).
we can pass a primitive data type by reference by putting it in an array
int[] arr = new arr[1]; // passes res by reference, just interact with arr[0] traverse(root, res);we can pass a reference data type by value by re-instantiating in the call
Mistake Notes
When using index pointers on an array, index 0 can be out of bound when the array length is 0.
If the range of input is of ~
10^9power level, consider usinglongtype (for return value) to prevent overflow. The representation range ofintis+- 2.1 * 10^9be aware that do not confuse
num[a]andaread the problem thoroughly and carefully!
overflow of local variables will cause strange errors
import java.util.*; class UglyNumber { public static int nthUglyNumber(int n) { List<Integer> res = new ArrayList<Integer>(); res.add(1); while(res.size() < n){ int ptr = 0; int lowerBound = res.get(res.size() - 1); int minNew = lowerBound * 2; // overflow of the upper bound of int! while(ptr < res.size()){ int curr = res.get(ptr); if(curr * 2 > lowerBound) minNew = Math.min(minNew, curr * 2); if(curr * 3 > lowerBound) minNew = Math.min(minNew, curr * 3); if(curr * 5 > lowerBound) minNew = Math.min(minNew, curr * 5); ptr++; } res.add(minNew); } return res.get(res.size() - 1); } public static void main(String[] args) { System.out.println(UglyNumber.nthUglyNumber(1600)); } }when putting the value into the result list, we must do pass-by-value!(wrap-instantiating!) Or the object will be modified.
// LeetCode #77 Combinations: Mistake Demo class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); backtrack(new ArrayList<Integer>(), res, n, k); return res; } public static void backtrack(List<Integer> currPath, List<List<Integer>> res, int n, int k){ int len = currPath.size(); if(len == k){ res.add(currPath); return; } int i = 1; if(len > 0) i = currPath.get(len - 1) + 1; while(i <= n){ // Should be doing wrap-instantiation here. // currPath is always changing in the back-tracking call tree! currPath.add(i); backtrack(currPath, res, n, k); currPath.remove(len); i++; } } }
Topics to be added (constantly updating…)
primitive type conversion
Object array for storing objects of different types in the same array
Back-Tracking & Recursion: pass-by-value the tentative value(for ex. the path of a Binary Tree); pass-by-reference the global value(for ex. the recording var)
Use
longtype if both array length and element upper limit is10^5!!!!!conversion between long and int