Strategies
From charlesreid1
Random assorted notes from competitive programming problems - various strategies, etc.
Arrays and Strings
Hash tables
- Using a HashSet or HashMap in Java is a fast, O(1) way to look things up
- Use hash tables when you need to keep track of how many of X different things you have seen
- Internally, hash tables can use binary trees to stay balanced, and use less space
Array lists
- Internally resized array with O(1) access
- When array runs out of space, needs to double, which takes O(N)
- Doubling in size should happen infrequently, so ends up taking O(1) on average
StringBuffer
- Avoids the expensive/costly construction of a new string in a loop
- StringBuffer internally stores an array of Strings, does not concatenate them until it needs to return the result (when toString() method called)
public string joinWords(String[] words) {
StringBuffer sentence = new StringBuffer();
for(String w : words) {
sentence.append(w + " ");
}
return sentence.toString();
}