Posted Updated Algorithm Template

Common Algorithm Implementation Templates

Traverse an array by groups

1
2
3
4
5
6
for (int i = 0; i < arr.length; i += interval) {
    for (int j = i; j < i + interval && j < arr.length; j++) {
        // do something
    }
    // do something
}

Calculate the submatrix sums fast

We can use a 2D prefix sum array. Each row of the 2D prefix sum array is a 1D prefix sum array for the corresponding row in the original matrix.

After initialization which takes $O(mn)$, calculating a submatrix sum takes $O(k)$, where k is the number of rows in the submatrix.

1
2
3
4
5
6
7
8
// given matrix[m][n]
int[][] prefixSum = new int[m][n];
// init
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        // initialize each element in prefixSum[i]
    }
}
Posted Updated Programming Tips

Java Programming Tips

Convert char to int

1
2
char c = '9';
int i = Character.getNumericValue(c);
1
2
char c = '9';
int i = c - '0';

Add zeros at the beginning of a number

1
2
int i = 640;
System.out.printf("%05d\n", i);
1
00640
1
2
int[] a = {1,2,3,4,5,6};
System.out.println(Arrays.toString(a));

Fill an array

Use Arrays.fill(array, val) to assign values to an array.

1
2
3
int[] a = new int[10];
Arrays.fill(a, 7);
System.out.println(Arrays.toString(a));
1
[7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

Convert between string and char array

1
2
3
char[] arr = {'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd'};
String s = new String(arr);
char[] arr2 = s.toCharArray();

Convert integer to string

1
2
3
String s1 = String.valueOf(i);
String s2 = Integer.toString(i, 10); // radix = 10
String s3 = String.format("%d", i);

Parse integer from string

Do not forget to catch the possible exception thrown by parseInt(). parseInt() ignores leading zeros.

1
2
3
4
5
try {
    Integer.parseInt(s, 10);
} catch (Exception ignored) {

}
1
int i = Integer.parseInt("000015640", 10); // 15640

Default initialization of an array in Java

Everything in a Java program not explicitly set to something by the programmer, is initialized to a zero value.

  • For references (anything that holds an object) that is null.
  • For int/short/byte/long that is a 0.
  • For float/double that is a 0.0
  • For booleans that is a false.
  • For char that is the null character '\u0000' (whose decimal equivalent is 0).

Initialize the capacity of a List

1
List<Integer> list = new ArrayList<>(10);

In this line of code, we initialize an array list with initial capacity of 10. Note that 10 is its capacity, not its size. So we still need to add elements one by one to this list. Assessing directly without adding any elements, such as directly calling list.get(1), will cause out-of-bound exceptions.

Reverse a List

1
Collections.reverse(list);

Create a List from an array

Take the return of Array.asList() as the parameter of ArrayList constructor.

1
2
int[] array = new int[10];
ArrayList<Integer> arraylIST = new ArrayList<>(Arrays.asList(array));

Sort

  • Primitive array: Arrays.sort(arr)
  • Object array: Arrays.sort(integerArr, comparator)
  • List: Collections.sort(list, comparator)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int[] arr = new int[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
Integer[] integerArr = new Integer[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
List<Integer> list = new ArrayList<Integer>(Arrays.asList(integerArr));
Arrays.sort(arr);
Arrays.sort(integerArr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});
Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});

Traverse a map

Use Map.Entry or HashMap.Entry.

1
2
3
4
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (HashMap.Entry<Integer, Integer> e:hashMap.entrySet()) {
    // do something
}

isLetter() and isAlphabetic()

isLetter() and isAlphabetic() are two methods of Character. The difference between them is:

  • isAlphabetic() checks UPPERCASE_LETTER && LOWERCASE_LETTER && TITLECASE_LETTER && MODIFIER_LETTER && OTHER_LETTER && LETTER_NUMBER.
  • isLetter() checks UPPERCASE_LETTER && LOWERCASE_LETTER && TITLECASE_LETTER && MODIFIER_LETTER && OTHER_LETTER.

The point is that isLetter() will return false given a letter number. For example, roman numeral five (the letter looks like “V”). Certainly, for the English language, the distinction makes no difference.

Use Deque over Stack for LIFO stacks

We should use Deque rather than Stack for LIFO stacks.

1
2
Deque<Integer> dstack = new ArrayDeque<>();
Stack<Integer> sstack = new Stack<>(); // not recommended

There are many reasons to prefer Deque:

  • Deque is an interface but Stack is a class. So using Deque brings us more flexibility for future extension.
  • Stack is synchronized but Deque is not thread-safe. In the case of no need to ensure thread safety, Deque is more efficient.
  • Deque iterates elements from top to bottom. Stack iterates elements from bottom to top.
  • Most important: with Stack, we can access/insert/remove arbitrary elements in the LIFO stack by indexes, stack.get(index); stack.add(index, e); stack.remove(index), which breaks the LIFO rule. Although Deque does not absolutely obey the LIFO rule, it can only access/insert/remove the first/last element in the LIFO stack.
1
2
System.out.println(Arrays.toString(arr)); // print a 1D array
System.out.println(Arrays.deepToString(marr)); // print a multi-dimensional array

Get ceiling/floor value of a number

1
2
double ceilingValue = Math.ceil(3.1); // 4.0
double floorValue = Math.floor(3.1);  // 3.0

Note that these twoMath functions return double. Or if we need to get the ceiling value of a fraction X/Y, we can also do as the following:

1
int res = (X + Y - 1) / Y;

Sort an array/list

  • Primitive array int[]: Arrays.sort
  • Objective array Integer[]: Arrays.sort and optional comparator
  • Objective list List<Integer>: Collections.sort and optional comparator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int[] arr = new int[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
Integer[] integerArr = new Integer[]{4, 1, 5, 4, 4, 0, 6, 1, 9};
List<Integer> list = new ArrayList<Integer>(Arrays.asList(integerArr));
Arrays.sort(arr);
Arrays.sort(integerArr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});
Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
});

Common time complexity calculation

$$
\sum_{1}^{n}{k^2}=\frac{1}{n}{n(n+1)(2n+1)}=O(n^3)\
\sum_{1}^{n}{k^3}=(\frac{1}{2}{n(n+1)})^2=O(n^4)
$$

String manipulation

1
2
3
4
StringBuilder builder1 = new StringBuilder("abcdefg");
// if we want to delete c and add it back
builder1.deleteCharAt(2); // "abdefg"
builder1.insert(2, 'c');  // "abcdefg"

toCharArray() and getBytes()

toCharArray() is better if we are not dealing with characters outside of the Unicode BMP, which are encoded as two surrogate characters. getBytes() needs to specify encoding, which is prone to mistakes. Also, toCharArray() is faster because for Java 7 and newer, a String object contains a char array internally. toCharArray() just need to complete a copy operation.

Integer object comparison

For two Integer objects, == compares their references while < and > compare their values. To examinate whether they have the same value, we should use equals() or unbox them by intValue().

And, it is safe to use comparison operators (==, <, >) for comparing values between an int and an Integer object.

1
2
3
4
5
6
7
Integer i1 = new Integer(15640);
Integer i2 = new Integer(15640);
Integer i3 = new Integer(15440);
System.out.printf("i1 == i2 : %b\n" +
        "i1.value == i2.value : %b\n" +
        "i1.equals(i2) : %b\n" +
        "i2 > i3 : %b\n", i1 == i2, i1.intValue() == i2.intValue(), i1.equals(i2), i2 > i3);
1
2
3
4
i1 == i2 : false
i1.value == i2.value : true
i1.equals(i2) : true
i2 > i3 : true

substring()

substring(beginIndex, endIndex) returns the substring in [beginIndex, endIndex). And it is safe for beginIndex == endIndex == 0 or length.

1
2
3
String s = "hello";
System.out.println(s.substring(0, 0)); // return ""
System.out.println(s.substring(s.length(), s.length())); // return ""

indexOf()

s.indexOf(pattern, fromIndex) returns the first index of given pattern from fromIndex (inclusive). If such pattern does not exist, it returns -1.

abstract keyword

If a class is declared abstract, it means that this class may be partially implementd. Thus, Java does not allow us to instantiate an abstract class. An abstract class can implement its constructor, functions (abstract or non-abstract) and have its variables.

An abstract function cannot have body. Any classes that declare any abstract functions must also be declared abstract. Any non-abstract classes that inherit abstract functions must implement all of them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static abstract class Node {
    int id;
    String name;

    public Node(int _id, String _name) {
        id = _id;
        name = _name;
    }

    public void printHello() {
        System.out.println("hello");
    }

    // an abstract function cannot have body
    public abstract void printWorld();
}

static class ANode extends Node {
    public ANode(int _id, String _name) {
        super(_id, _name);
    }

    // the non-abstract subclass of an abstract class must implement all inherited abstract functions
    @Override
    public void printWorld() {
        System.out.println("world");
    }
}

public static void main(String[] args) {
    // cannot instantiate an abstract class
    // Node n = new Node();
    Node n = new ANode(1, "node1");
    n.printHello();
    n.printWorld();
}

Immutable objects

String and all primitive wrapper classes (Integer, Double, Long, Character, etc.) are immutable.

Inner class and nested class

An instance of inner class can exist only within an instance of its outerClass. The instance of the inner class has direct access to the methods and fields of its outer instance. A nested class can access all static resources of its outer class.

The difference between inner class and nested class is straightforward. Inner class has non-static features. Nested class has static features.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class TestInnerNested {

    class InnerClass {
        final String name = "inner";

        public void print() {
            printHello();
        }
    }

    static class NestedClass {
        NestedClass next;

        public void print() {
            System.out.println(id);
        }
    }

    static final String id = "15640";

    private void printHello() {
        System.out.println("hello");
    }

    public static void main(String[] args) {
        // an instance of InnerClass can exist only within an instance of OuterClass
        // the instance of the inner class has direct access to the methods and fields of its outer instance
        TestInnerNested test = new TestInnerNested();
        TestInnerNested.InnerClass inner = test.new InnerClass();
        inner.print();

        // a nest class can access all static resources of its outer class
        TestInnerNested.NestedClass nested = new TestInnerNested.NestedClass();
        nested.print();
    }
}

Round a float number to n decimal places

Use DecimalFormat.

1
2
3
DecimalFormat df = new DecimalFormat("#.####");
df.setRoundingMode(RoundingMode.CEILING);
System.out.println(df.format(15640.123456)); // 15640.1235

Traverse key-value pairs in a map

Use nested class Map.Entry<>.

1
2
3
4
5
Map<Integer, String> map = new HashMap<>();
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    int key = entry.getKey();
    String value = entry.getValue();
}

assert keyword

Do Not use assert in test. They can be activated at run-time by way of the -ea option on the java command, but are not turned on by default.

Split a string into at most 2 pieces

1
String[] arr = str.split(" ", 2);

Difference between Exception and RuntimeException

Any exception that derives from Exception is a checked exception. If a function throws an Exception in its body, it should also declare this behavior in this function declaration. Whereas a class that derives from RuntimeException is un-checked. RuntimeExceptions do not need to be explicitly handled by the calling code.

Generally RuntimeExceptions are exceptions that can be prevented programmatically.

floorEntry() and lowerEntry() of TreeMap

floorEntry(key) gets the entry corresponding to the specified key; if no such entry exists, returns the entry for the greatest key less than the specified key; if no such entry exists, returns null.

lowerEntry(key) returns the entry for the greatest key less than the specified key; if no such entry exists (i.e., the least key in the Tree is greater than the specified key), returns null.

Using a custom class as a key

To use a custom class as a key in Java Map, the custom class must define its equals and hashCode methods. Though Java provides an implicit implementation of these two methods for every class, the default implementation may lead to unexpected behaviors of Map (such as failing to find an existing key when inquiring with a new object with the same fields).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public boolean equals(Object obj) {
    if (obj == null) {
        return false;
    }
    if (obj.getClass() != this.getClass()) {
        return false;
    }
    // return ...
}

@Override
public int hashCode() {
    return Objects.hash(...);
}

Shift

Signed shift: <<, >>

Unsigned shift: <<<, >>>

Follow

Categories

Tags

Array5
BFS4
Backtrace6
Binary Search7
C1
Coloring1
Combination3
Common Substring2
DFS12
DP15
Delta2
Go1
Graph1
Greedy3
Heap3
In-place2
Interval8
Java2
K Sum7
List2
Monotonic5
Permutation5
Prefix Sum2
Queue1
Rolling Hash1
Simulation1
Sliding Window5
Stack1
String7
Subset1
Substring3
Tree6
Two Pointers5

Recents

Archives

×