Special Skills
Bit Manipulation
When doing bit shift, the sign bit is duplicated and shifted. e.g. 111111111(-1) >> 1 will be 111111111(-1)
XOR is Communicative and Associative. A XOR A = 0, ==> A XOR B XOR A = B.
Single out a number: 136. Single Number (1 ^ 1 ^ 3 ^ 3 ^ 8 = 8)
Single out a character: 389. Find the Difference (a ^ a ^ k ^ k ^ m = m)
int count_one(int n) {
while(n) {
n = n&(n-1);
count++;
}
return count;
}
int getSum(int a, int b) {
return b==0? a:getSum(a^b, (a&b)<<1); //be careful about the terminating condition;
}
public boolean isPowerOfFour(int num) {
return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;
//0x55555555 is to get rid of those power of 2 but not power of 4
//so that the single 1 bit always appears at the odd position
}
Sometimes we might solve problem by translating it to bit representation and use bit-wise operation to do the computation. For example, we can treat a bit position having value 1 as the presence of a character in a string: 00000000 00000000 00000000 00001001 => there is an 'a' and 'd' in the string.
318. Maximum Product of Word Lengths
Given a string array words, find the maximum value of length(word[i]) * length(word[j])
where the two words do not share common letters. You may assume that each word will contain only lower case letters.
If no such two words exist, return 0.
class Solution {
public int maxProduct(String[] words) {
int[] value = new int[words.length];
for(int i=0; i<words.length; i++) {
for(int j=0; j<words[i].length(); j++) {
value[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
int maxLen = 0;
for(int i=0; i<words.length-1; i++) {
for(int j=i+1; j<words.length; j++) {
if((value[i]&value[j]) == 0 )
maxLen = Math.max(maxLen, words[i].length() * words[j].length());
}
}
return maxLen;
}
}
Similarly, we could use the methodologies to find if the all the characters in a string are unique.
public boolean isUniqueBitMani(String str){
//assume lower case a-z
if(str.length()>26) return false;
int checker = 0; //int is 32 bit which is ok to handle 26 char pos;; cannot use this for 128 ASCII
for(char c: str.toCharArray()) {
if((checker & (1<<c)) > 0) return false;
checker |= 1<<c;
}
return true;
}
A ^ B = C ==> A ^ C = B
421. Maximum XOR of Two Numbers in an Array
The crux to this problem is... we start with the most significant bit check if any two number give it bit 1. Given the the previous significant bit not changed, we then check if there is any two number give previousSigBit + "1". If not, previousSigBit + "0" is the current largest and move to next bit.
To find if two number give that prefix, we use the property A* ^ B* = desiredPrefix ==> A* ^ DesiredPrefix = B* ==>(use hashset to look up)
*A, *B are masked A, B after the desired prefix length.
Use as Masking
We can use & | to do the masking. Another way is do the shift >>, << and do the comparison with desired number.
Integer in binary form is 0b110...
if((data[i]>>5) == 0b110) {}
Check if Exactly One Bit Set
return (checker & (checker-1)) == 0;
Isolate the Last Set Bit (Binary Indexed Tree)
i&(-i)
Drop the Last Set Bit
i&(i-1)
Integer.bitCount(x);
Encoding Infotamtion in just a Number
We can use the bit positions of an int to encode information, for example, we can set bit position 9 of a 32 bit integer to 1 to represent that we have number 9 in the set.
Dummy Head to Help with LinkedList Operations
Sentinel a dummy node, typically placed at the head or end of the list to help make operations simpler (e.g., delete) or to indicate the termination of the list.
92. Reverse Linked List II (in given start - end range)
ListNode dummyHead = new ListNode(-1);
....
return dummyHead.next;
Use Extra Array Row/Col to Help Boundary Operation
//for example, we might let index i to be 1 base...
//so that the first row will be all zeros... which could help handling the boundary scenario of the sum
treeSum[i][j] = treeSum[i-1][j/2] + v;
Reverse
Given form ABC = ((1 2 3) (4 5 6) (7 8 9)), rev(ABC) = (9 8 7 6 5 4 3 2 1). If we do sub-reverse in 9 8 7, it will give 7 8 9.
So, rev( rev(A) rev(B) rev(C)) = rev((3 2 1) (6 5 4) (9 8 7)) = ((7 8 9) (4 5 6) (1 2 3)) = CBA
186. Reverse Words in a String II
Rotation
If we are saying rotating a list, it is like connecting it as a circle and do the rotation. Rotate k places where k might > length of the list. k = k % length.
Use an Int variable to store two states
00: first digit is previous state, second digit is current state
Use |= and bit shift << >> to update and retrieve state
Use simple array to store directions
int d=0;
int[][] dir = {{-1, 1},{1, -1}};
row += dir[d][0];
col += dir[d][1];
d=1-d //this is to alternate between two directions
To loop left, right, up, down cell
final int[] shift = {0, 1, 0, -1, 0}; // or final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1,0}};
for(int k=0; k<4; k++) {
int row = coor[0] + shift[k];
int col = coor[1] + shift[k+1];
...
}
Use LinkedList to achieve cyclic alternation
Note that two items alternation is also cyclic. 281. Zigzag Iterator
public class ZigzagIterator {
private LinkedList<Iterator> data;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
data = new LinkedList<Iterator>();
if(v1!=null && v1.size()>0) data.add(v1.iterator());
if(v2!=null && v2.size()>0) data.add(v2.iterator());
}
public int next() {
Iterator listIter = data.remove();
int temp = (Integer)listIter.next();
if(listIter.hasNext()) data.add(listIter);
return temp;
}
public boolean hasNext() {
return !data.isEmpty();
}
}
Interval Sweeping
Some problems involving intervals, we usually have some tricks to play around the start point and end point. When we meet the start point, we perform the add/remove/sum etc, when we meet the end point, we restore it.
Assume you have an array of length n initialized with all 0's and are given k update operations.
Each operation is represented as a triplet:[startIndex, endIndex, inc]which increments each element of subarrayA[startIndex ... endIndex](startIndex and endIndex inclusive) with inc.
Return the modified array after all k operations were executed.
Example:
Given:
length = 5,
updates = [
[1, 3, 2],
[2, 4, 3],
[0, 2, -2]
]
Output:
[-2, 0, 3, 5, 3]
Design Problems
For most design problems, it is implemented in a class with different methods. We should consider method calls reusing internal method(s) if possible.
Pre-sum & Two Pointer
For array range sum, we could have pre-computed the pre-sum S(j) = sum(0..j) then we could find sum(i-j) easily with S(j) - S(i-1).
Some problem requires the counting on how many of such range sum satisfies certain criteria. Since we just count these pairs, we don't care the order that we check j, or j+3 first, as long as S(j) - S(i-1) satisfies the requirement.
Since it is counting, it reminds us the benefit of sorting (since order doesn't matter) and two pointer monotonicity counting.
see also... Divide & Conquer
Rotation
String rotation: if we move part of the string S to the end to form a rotation e.g. S = xy, rotated = yx
SS = xyxy, the rotated is always a substring of SS.
Hardcode the Solution if the Problem Size must be Small
For example, the number of set bits of an integer. It must be smaller than 20.
class Solution {
public:
int countPrimeSetBits(int L, int R) {
unordered_set<int> primes = {2,3,5,7,11,13,17,19}; //if the number is int, the number of set bits must < 19...!
int count = 0;
for(int i=L; i<=R; i++) {
int bits = 0;
for(int num = i; num>0; num>>=1) {
bits += num & 1;
}
if(primes.count(bits)) count++;
}
return count;
}
};
Looping the Matrix Row by Row (left to right), Col by Col (top to bottom)
for (int i = 0; i < N; i++) {
for (int j = 0, k = N - 1; j < N; j++, k--) {
//row by row, loop through from left & right side
grid[i][j] ;
grid[i][k] ;
//col by col, loop through from top & bottom
grid[j][i] ;
grid[k][i] ;
}
}
Track the Solution Possible Range, and Check Valid/Invalid Case
Use 0, 1 or 1, -1 to Mark Two Alternative States
If we use +, 1 - state will alternate between 0 and 1;
If we use *, state*-1 will alternate between 1 and -1;