Java Basics
int[] result = {INT_MIN_VALUE, INT_MAX_VALUE};
result = {1, 1}; //this will give compilation error ... as the {} can only be used in initialization.
INT_MAX_VALUE & INT_MIN_VALUE
if it is required to handle Math.abs, be careful of the boundary value of int, -n / Math.abs(n) will not give correct answer if n = Integer.MIN_VALUE.
Integer.MIN_VALUE is -2147483648, but the highest value a 32 bit integer can contain is +2147483647. Attempting to represent +2147483648 in a 32 bit int will effectively "roll over" to -2147483648.
long absN = n;
absN = -absN; // or absN = Math.abs(absN);
Math.abs(-2147483648); //will give wrong answer as it first try to abs it to positive 2147483648
Math.abs((long)numerator) //should first cast it to long type... same in c++
Integer.bitCount(x); //for bit manipulation problem
Long x = 1l;// must put the l at the end to denote it is long not int
x.intValue(); // get int of a Long
//Integer parseInt can handle text like +3, -4
Integer.parseInt(operand.substring(0, operand.length()-1)); //to get coefficient of "-3x"
long runningSum; // use long to store int sum to avoid overflow possibility
(double) runningSum/numElement; // int / int will give int, so need to cast to double
Consider the boundary of the problem from time to time, for example: 556. Next Greater Element III
Use CONST instead of Hard-code
private final static String SEP = ",";
private final static String NULL = "#";
Random
//java.util.Random
Random rand = new Random();
// Generate random integers in range 0 to 999
int rand_int1 = rand.nextInt(1000); //.nextDouble() .nextLong()
//Math.random()
Math.random(); //return a random double num [0, 1)
int randomIndex = (int) (Math.random() * CHARSET.length()); //need to cast to int if we want an integer
String & Character
check if a char is alphanumeric or not
Character.isLetterOrDigit()
Character.isLetter()
Character.isDigit()
char c = ''; // this is invalid code, empty character literal
//instead we can do
char c = '\0'; //this means null character
//and null character '\0' is also terminating character in a string
char c[10] = {'a', '\0', 'c', '\0'}; //this will output "a" if as a string
String split: we have to escape some special characters e.g. . Otherwise it will give wrong result.
String[] ver1Arr = version1.split("\\.");
"aaa".substring(3) // this gives "", not ArrayIndexOutOfBound
indexOf(String str, int fromIndex)
lastIndexOf(String str)
//tricky way to deal with int n as array of char
char[] digits = (n+"").toCharArray();
String.format("%d:%d", a,b); //will output a:b
String.join(" ", words);
str.toLowerCase();
s.split(" +"); // the sep is one or more space
s.split("\\+"); //split by plus sign need escape
//java string use regx to split ...
//so need to use \\ to escape instead of \, as \ is also meta-char
String[] blocks = IP.split("\\.");
s.matches(".*LLL.*|.*A.*A.*"); //reg matches
s.replaceAll("[^a-zA-Z]", ""); //replace all non a-z A-Z
//string split but with delimiter retained
String[] operands = exp.split("(?=[+-])");
Use char array instead of substring:
When substring is used, a new object is created every time, which is time consuming. You should instead use start index so that you can always keep the original string as is and moving index only.
search(root, word.toCharArray(), 0);
public boolean search(Node root, char[] charArr, int k) {}
StringBuilder
StringBuilder sb = new StringBuilder();
sb.append(node.val).append(SEP);
sb.toString();
sb.reverse().toString();
sb.substring(i,j);
//can insert at particular position
sb.insert(indexMap.get(num), "(");
Arrays & List
Arrays.sort() cannot be used directly to sort primitive arrays in descending order. If you try to call the Arrays.sort() method by passing reverse Comparator defined by Collection.reverseOrder() , it will throw the error - "no suitable method found for sort(int[],comparator<object>)" That will work fine with Integer array but will not work with an int array. The only way to sort a primitive array in descending order is, first sort the array in ascending order and then reverse the array in place. This is also true for two-dimensional primitive arrays.– akuriako Jan 2 at 15:56
int[] result = Arrays.copyOf(nums, nums.length); //must provide a length
Arrays.fill(nums, -1);
Arrays.sort(nums);
Arrays.sort(digits, swapPos+1, digits.length); //sort within a given range in the array
resultList.addAll(list1);
Collections.reverse(list);
int[] numsCopy = nums.clone() //we can clone an array (shallow) with clone method
//list delete tails
list.subList(from, to).clear();
Arrays.asList(): This method also provides a convenient way to create a fixed-size list initialized to contain several elements.
List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
//if we want to change the size e.g. add more elements later, we should make a new ArrayList which is a copy of it.
List<String> stooges = new ArrayList<String>(Arrays.asList("Larry", "Moe", "Curly"));
Arrays.sort() vs Collections.sort()
Arrays.sort works for arrays which can be of primitive data type also. Collections.sort() works for objects Collections like ArrayList, LinkedList, etc.
LinkedList
LinkedList is a List in Java. The generic variable can be int[]. When covert it to array, we have to provide the size of the array list.
LinkedList<int[]> result = new LinkedList<int[]>();
for(int[] person: people) {
result.add(person[1], person);
}
return result.toArray(new int[people.length][]);
.isEmpty()
.remove()
.add()
.addFirst() // is equivalent to .add(0, curr)
.addAll(Arrays.asList(data.split(SEPERATOR)));
Queue
Queue<TreeNode> q = new LinkedList<>();
TreeNode node = q.poll();
q.offer(node.left);
Deque<E>
The name deque is short for "double ended queue" and is usually pronounced "deck".
Deque<Integer> q = new ArrayDeque<Integer>(windowSize);
Deque<Integer> q = new ArrayDeque<Integer>();
q.pollFirst(); q.pollLast();
q.addFirst(); q.addLast();
q.peek(); q.peekLast();
Difference between Poll() and Remove()
peek() // return null if empty
element() //throws a NoSuchElementException
poll() // return null if empty
remove() //throws a NoSuchElementException
PriorityQueue
Add all entries from a HashMap to PriorityQueue/ LinkedList using Map.Entry<> and addAll()
PriorityQueue<Map.Entry<Character, Integer>> charFreqHeap = new PriorityQueue<>((a,b) -> b.getValue() - a.getValue());
Map<Character, Integer> count = new HashMap<>();
for(int i=0; i<s.length(); i++) {
char c = s.charAt(i);
count.put(c, count.getOrDefault(c, 0)+1);
}
charFreqHeap.addAll(count.entrySet());
LinkedList<Map.Entry<Character, Integer>> waitingQueue = new LinkedList<>();
pq.remove(num); //remove the num if its num value is there in pq
Stack
stack.addAll(list);
HashMap, HashSet
Set<String> banned = new HashSet<>(Arrays.asList(bannedStrArr)); // construct a set from an array
set = new HashSet();
if(set.add(9)) {....} //HashSet return true means no duplicate
if(set.remove(9)) {....} //HashSet return true means it has element 9 and removed
set.iterator().next(); //return first element of the set
//we can even put a List<Integer> into hashset, the collection implementation of List will have hashCode and equals
Set<List<Integer>> result = new HashSet<List<Integer>>();
return new ArrayList<List<Integer>>(result);
//use Map.Entry for HashMap traverse
for(Map.Entry<Integer, Integer> indegreeCount:indegree.entrySet()) {
if(indegreeCount.getValue()==0) {
q.add(indegreeCount.getKey());
}
}
map.containsKey(key);
map.containsValue(val);
//Some convenient shortcuts of HashMap
adjList.putIfAbsent(ppid.get(i), new ArrayList<Integer>());
adjList.get(ppid.get(i)).add(pid.get(i));
//**** HashMap put has a return value ****
// the previous value associated with the key, or null
HashMap of a List / Set
Map<String, Set<String>> similarWordsMap = new HashMap<>(); //for O(1) random access
Map<String, List<String>> similarWordsMap = new HashMap<>(); //for sequential access
LinkedHashSet
It is just like HashSet but the elements are stored in the order which they were added. It is useful when we want to retrieve the element in the order of least recently used.
//we still need iterator to get the first element
int keyToRemove = freqKeyMap.get(minFreq).iterator().next();
freqKeyMap.get(minFreq).remove(keyToRemove); // remove is O(1)
LinkedHashMap
It is similar as LinkedHashSet. To get first key, we have to first get keySet() then iterator().
leastRecentUsedList.remove(leastRecentUsedList.keySet().iterator().next());
Comparator
Create an anonymous class that implements the Comparator interface. The comparator class is then pass to Arrays.sort().
In the code, you're not creating an instance of the interface. Rather, the code defines an anonymous class that implements the interface, and instantiates that class. It is called anonymous type/class which implements that interface.
@Override //Override, O must be capital letter
public int compare(String a, String b) {
String str1 = a+b;
String str2 = b+a;
return str2.compareTo(str1);
}
};
Arrays.sort(s_nums, strComp);
PriorityQueue Comparator & Java 8 Comparator
** The compare method no need to return 1, 0 or -1 as result. negative means <, 0 means ==, positive means >, so we just do the subtraction of a.end - b.end.
//java 8
PriorityQueue<Interval> pq = new PriorityQueue<Interval>(intervals.length, (a,b) -> a.end-b.end);
PriorityQueue<Interval> pq = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
@Override
public int compare(Interval a, Interval b) {
return a.end-b.end;
}
});
//java 8 pairs[i][0], pairs[i][1]
Arrays.sort(pairs, (a,b) -> (b[0] - a[0]));
Enum
We can implement the enum with a rank attribute, which is then can be used to do customised Comparator<YourEnumClass>().
enum Color {
red(1), blue(2), green(3), yellow(4), black(5), white(6), pink(7);
private final int rank;
/*this constructor is private as we don't want people to change the rank*/
private Color(int rank){
this.rank=rank;
}
public int getRank() {
return rank;
}
}
Loops
Circular Loop
We sometimes need to loop over the array for specific number of times.
//If the number of times is not fixed, we better use while loop and i = (i+1) % n;
for(int i=0; i<2*n; i++) {
while(!s.isEmpty() && nums[i%n] > nums[s.peek()])
result[s.pop()] = nums[i%n];
if(i<n) s.push(i);
}
Include boundary check in loop variables
for(int v=Math.max(0, i-1); v<Math.min(m, i+2); v++) {
for(int h=Math.max(0, j-1); h<Math.min(n, j+2); h++) {
}
}
Pair class
/*
Pair (K key, V value) : Creates a new pair
boolean equals() : It is used to compare two pair objects. It does a deep comparison, i.e.,
it compares on the basic of the values (<Key, Value>) which are stored in the pair objects.
*/
Pair p1 = new Pair(3,4);
Pair p2 = new Pair(3,7); //p1 =/= p2
p1.getKey();
p1.getValue();
I/O
The FileReader and FileWriter classes are a bit tricky, since they implicitly use the system's default character encoding(UTF-8). If this default is not appropriate, the recommended alternatives are, for example:
FileInputStream fis = new FileInputStream("test.txt");
InputStreamReader in = new InputStreamReader(fis, "UTF-8");
FileOutputStream fos = new FileOutputStream("test.txt");
OutputStreamWriter out = new OutputStreamWriter(fos, "UTF-8");
Scanner scanner = new Scanner(file, "UTF-8");
public GameOfLife(String boardFilePath, String newBoardFilePath) throws IOException{
boardInput = new BufferedReader(new FileReader(boardFilePath));
newBoardOutput = new BufferedWriter(new FileWriter(newBoardFilePath));
}
while((input = readLine())!=null) {
//.....
}
BitSet
It use a bit to represent a number. The space used is thus much less.
public class PhoneDirectory{
private BitSet bitSet;
int maxNumbers;
int idx;
public PhoneDirectory(int maxNumbers){
bitSet = new BitSet(maxNumbers);
this.maxNumbers = maxNumbers;
idx = 0;
}
public int get(){
if(idx == maxNumbers) return -1;
int num = idx;
bitSet.set(num);
idx = bitSet.nextClearBit(idx);
return num;
}
public boolean check(int number){
if(number < 0 || number >= maxNumbers) return false;
return !bitSet.get(number);
}
public void release(int number){
if(number < 0 || number >= maxNumbers) return;
if(!bitSet.get(number)) return;
bitSet.clear(number);
if(number < idx) idx = number;
}
}
Implements equals method
Comparing every element with the instance given tocontainsis wasteful, though, and a whole class of data structures uses a more performant approach. Instead of comparing the requested instance with each element they contain, they use a shortcut that reduces the number of potentially equal instances and then only compare those.
This shortcut is the hash code, which can be seen as an object’s equality boiled down to an integer value. Instances with the same hash code are not necessarily equal but equal instances have the same hash code.
https://www.sitepoint.com/how-to-implement-javas-hashcode-correctly/
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof Sector)){
return false;
}
Sector that = (Sector) o;
return this.x == that.getX() && this.y == that.getY();
}
Combining them could be done manually. A common algorithm is to start with some arbitrary number and to repeatedly multiply it with another (often a small prime) before adding a field’s hash:
int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;
@Override
public int hashCode() {
int prime = 31;
int result = 1;
result = prime*result + this.x;
result = prime*result + this.y;
return result;
}
This might result in overflows, which is not particularly problematic because they cause no exceptions in Java.