Essential Coding Skills and Tricks in Java
Data Structure Operation
Array
-
Array is a consecutive allocated memory space, no overhead
-
It’s size is fixed.
-
它是mutable类型可以直接在原来位置进行CURD
-
Iterate an array from left to right
for (int i = 0; i < array.length; i++)
-
Iterate an array from right to left
for (int i = array.length - 1; i >= 0; i++)
-
Iterate an array custom step
for (int i = 0; i < array.length - 1; i+=k) // k is step
-
Convert a List to an array
int[] array = new int[size]; for (int i = 0; i < list.size(); i++) { array[i] = list.get(i); }
-
One array && two loops, skip cur element
int[] array = {1,2,3}; int[] result = new int[array.length]; for (int i = 0; i < array.length; i++) { int sum = 0; for (int j = 0; j < array.length; j++) { if (i == j) { continue; } sum += i * j; } result[i] = sum; } //result = [5,8,9]
-
Convert an array in to a 2D array
/* [1,2,3,4,5,6,7,8] [[1,2,3,4], [5,6,7,8]] */ r = 2; c = 4; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { board[i][j] = array[i * c + j]; } }
-
Print each character using loop
for (char c = 'a'; c <= 'z'; c++) { System.out.println(c); }
Comparesion and Range of Array
- Question laicode119
- Use the least number of comparisons to get the largest and smallest number in the given integer array. Return the largest number and the smallest number.
- Answer:
- We can use 2 / n times swap to make sure that left half of array contain the largest num and right half contain the smallest num
- [7, 4, 5, 6, 3, 9] –> swap(i, n - 1- i) –> [9, 4, 6, 5, 3, 7]
- (0, (n -1) / 2) ; (n / 2, n - 1)
- [7, 4, 5, 10, 6, 3, 9] –> swap(i, n - 1- i) –> [9, 4, 6, 10, 5, 3, 7]
- (0, (n -1) / 2) ; (n / 2, n - 1) include middle value 10
/ and %
-
Example:
- 3 % 10 = 3, 3 / 10 = 0
- 12 % 10 = 2, 12 / 10 = 1
-
In 2D array: Given a index of element to find coresponding row and column
row = index / column; column = index % column;
-
Convert digit number to single number
int num = 123; while (num != 0) { int cur = num % 10; System.out.println(cur); num /= 10; }
-
Implement adder
//plus one //input: [9,9,9] //output: [1,0,0,0] public int[] plueOne(int[] input) { int carry = 1; for (int i = input.length - 1; i >= 0; i--) { int cur = input[i] + carry; carry = cur / 10; input[i] = cur % 10; } if (carry != 0) { int[] result = new int[input.length + 1]; result[0] = carry; for (int i = 0; i < input.length - 1; i++) { result[i + 1] = input[i]; } return result; } return input; }
Slope
- int slope = (y1 - y0) / (x1 - x0)
- double slope = ()(y1 - y0) + 0.0) / (x1 - x0)
String
-
String 是一个object, it is immutable type in java. If we want to operate(CRUD) it, it must be a charArray
-
Convert to charArray
char[] array = string.toCharArray();
Linked List
-
It is a non-consecutive structure, overhead of multiple objects with the “next” reference
-
Using fast and slow pointer
- find middle of linked list
- find if linked list has a cycle
-
reverse linked list
-
dummy node
Tree
- Tree Travseral
- Pre-order
- In-order
- Post-order
HashMap
hashMap是一个array形式的数组,每个index存
-
Guarantee the hashcode always be positive
key.hashCode() & 0x7FFFFFFF;
-
Generate a hashMap from a list or an array
HashMap<Character, Integer> map = new HashMap<>(); //Method 1 in Java 8 for (char cur : s.toCharArray()) { Integer count = map.getOrDefault(cur, 0); map.put(cur, count + 1) } //Method 2 for (char cur : s.toCharArray()) { Integer count = map.get(cur); if (count == null) { count = 1; } else { count++; } map.put(cur, count); }
-
Iterate each of the key, value pairs in a hashMap
for (Map.Entry<K, V> entry : map.entrySet()) { entry.getValue(); entry.getKey(); }
HashSet
-
Generate HashSet
Set<Character> set = new HashSet<>(); for (char cur : s.toCharArray()) { if (set.add(cur)) { System.out.println("adding new char to the set"); } else { return false; } }
Java Concepts
Object-Oriented-Design (OOD)
-
key words: class, object, reference, dereference, primitive type, class types, fields, constructor, stack, heap, final, static
-
pass by value;
- primitive type: copy of the value itself
- objects: copy of the object reference
-
array
- it is a object
- “length” is a field of the array object, it also is a final type
-
NullPointerException (NPE) vs. Empty
- NPE: deference to null, null is object
-
linked list vs. LinkedList
-
eager computation and lazy computation
-
Interface
- It has some abality
- Can’t be instantiate, should implements
-
Abstract class
- Can’t be instantiate
Abstract class Interface It have abstract and non-abstract methods has only abstact method doesn’t support multiple inheritance supports multiple inheritance have final, non-final, static and non-static variables has only static and final variables have static methods, main method and constructor can’t have static methods, main method or constructor provide the implementation of interface can’t provide the implementation of abstract class abstract keyword is used to declare abstract class interface keyword is used to declare interface
- Can’t be instantiate
-
Good Practice:
- Declare into a general type, initialize into a concrete trap(Interface are also types)
-
Amortized Time Complexity
- ArrayList
- HashMap
-
ArrayList vs. LinkedList
- If we have a lot of random access operations, or always add/remove at the end, or time complexity is similar for using ArrayList and LinkedList, use ArrayList (overhead and locality)
-
Logical Operator Short Circuit