Question

link

Sort the letters in one word by the order they occur in another in linear time.

Solution

This

text

is

used

to

stop

you

from

looking

at

the

answer

immediately

The answer is counting sort.

Code

Question

link

Solution

This question is very standard “rotate 3 times” solution.

Code

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int len = nums.length;
        k = k % len;

        reverse(nums, 0, len - k - 1);
        reverse(nums, len - k, len - 1);
        reverse(nums, 0, len - 1);
    }

    void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Question

link

Analysis

This question is standard bit manipulation. We essentially get bits one by one from n, and append it to the result.

However, the question ask how to optimize it, to improve its performance. Em, that’s interesting.

Solution

First code is the standard solution.

I found another interesting solution from programcreek, which uses “swap bits” method. I’ve never seen this before, so I posted his solution below.

But is it really a faster solution?

Finally, I found something in 书影 博客, quoted as below:

以4位为单位执行反转，将0x0至0xF的反转结果预存在一个长度为16的数组中，反转时直接查询即可。

Thus this is the best solution for performance.

Code

My code

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int last = n & 1;
            n >>= 1;
            result <<= 1;
            result = result | last;
        }
        return result;
    }
}

“swap bits”

public int reverseBits(int n) {
    for (int i = 0; i < 16; i++) {
        n = swapBits(n, i, 32 - i - 1);
    }

    return n;
}

public int swapBits(int n, int i, int j) {
    int a = (n >> i) & 1;
    int b = (n >> j) & 1;

    if ((a ^ b) != 0) {
        return n ^= (1 << i) | (1 << j);
    }

    return n;
}

Best solution:

char tb[16] = {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};

uint32_t reverseBits(uint32_t n) {
        int curr = 0;
        uint32_t ret = 0;
        uint32_t msk = 0xF;
        for(int i = 0; i < 8; i++) {
            ret = ret << 4;
            curr = msk&n;
            ret |= tb[curr];
            n = n >> 4;
        }
        return ret;
}

Question

link

11110
11010
11000
00000

11000
11000
00100
00011

Analysis

At every ‘1’ position, do DFS.

Solution

I post my code below. Note that we do not actually have to have the method “findLand” - we can simply read through the grid and mark all ‘1’s in one run.

You might want to come up with your own code. Mine is just for reference. This is not an very interesting question, I assume.

Code

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;

        Pair firstPiece = findLand(grid, m, n);
        while (firstPiece != null) {
            // mark all neighbors, and count increment
            mark(grid, m, n, firstPiece);
            firstPiece = findLand(grid, m, n);
            count++;
        }

        return count;
    }

    void mark(char[][] grid, int m, int n, Pair p) {
        if (p.x < 0 || p.x == m || p.y < 0 || p.y == n) {
            return;
        } else if (grid[p.x][p.y] != '1') {
            return;
        }
        // mark current and then dfs
        grid[p.x][p.y] = '2';
        mark(grid, m, n, new Pair(p.x - 1, p.y));
        mark(grid, m, n, new Pair(p.x + 1, p.y));
        mark(grid, m, n, new Pair(p.x, p.y - 1));
        mark(grid, m, n, new Pair(p.x, p.y + 1));
    }

    Pair findLand(char[][] grid, int m, int n) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    return new Pair(i, j);
                }
            }
        }
        return null;
    }

    class Pair {
        int x;
        int y;

        public Pair(int a, int b) {
            x = a;
            y = b;
        }
    }
}

Question

link

Analysis

In order to remove the last ‘1’ bit, we use this operation:

n = n & (n - 1);

Solution

Just remove all the ‘1’ bits.

Code

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

Question

link

Solution

DP question. Be careful what the initial values of dp(1) is. You should work this out without a problem!

Code

public class Solution {
    public int rob(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        } else if (num.length == 1) {
            return num[0];
        }
        int len = num.length;
        int[] dp = new int[len];
        dp[0] = num[0];
        dp[1] = Math.max(num[0], num[1]);
        int max = Math.max(num[0], num[1]);
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + num[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

Question

link

Analysis

This is a pretty interesting mathematics question. Now we take 2 numbers as example:

Num1: 110010

Num2: 110111

Result: 110000

And:

Num1: 0110

Num2: 1100

Result: 0

Note that:

1. if the first ‘1’ bit of the 2 numbers are at different position, the answer should simply be 0.

2. if have same position, then the result would be the continous sequence of 1s, followed by all 0s.

Solution

The 2 best solutions is very well presented by Grandyang using bit shifting and masking. Please refer to code 1 and code 2 below.

I found a third solution at programcreek, which makes use of the fact that m is smaller than n.

Code

code 1

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int d = INT_MAX;
        while ((m & d) != (n & d)) {
            d <<= 1;
        }
        return m & d;
    }
};

code 2

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++i;
        }
        return (m << i);
    }
};

code 3

public int rangeBitwiseAnd(int m, int n) {
     while (n > m) {
          n = n & n - 1;
     }
     return m & n;
}

Question

link

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Solution

This question basically is binary tree traversal. During the process, we keep a list and update the elements in it.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        traverse(result, root, 1);
        return result;
    }

    void traverse(List<Integer> result, TreeNode node, int level) {
        if (node == null) return;
        if (level > result.size()) {
            result.add(node.val);
        }
        traverse(result, node.right, level + 1);
        traverse(result, node.left, level + 1);
    }
}

Question

link

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Analysis

This question is straight-forward: just iterate thru all the 10-letter long subsequences, and then add into hashmap.

However, if you simply use String as hash key, it will exceed OJ run time.

Solution

Convert string to int is the right approach. To get the best performance, we use 2 bits to represent each DNA nucleotide. Integer is 32-bit long so, no problem with that.

Node that Integer.Max = 2,147,483,647. There’s total of 10 digitals, so using 1 digit to represent 1 letter is not feasible. Ref: BUPT-哲人善思

Code

The code is pretty difficult to write.

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return res;
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        // map<> stores int-to-int: first int is "ACGT" -> 1234
        // second int is the init position of the pattern in s

        int num = 0;
        int mask = 0xFFFFFFFF;
        mask >>>= (32 - 18);

        for (int i = 0; i < s.length(); i++) {
            num = mask & num;
            // get the last 18 binary digits of num

            num = (num << 2) | convertChatToInt(s.charAt(i));
            // append num with the number representing charAt(i)

            if (i >= 9) {
                // insert or search num in the map
                if (!map.containsKey(num)) {
                    map.put(num, (i - 9));
                    // (i - 9) is the start position of 
                    // the 10-letter-long sequence
                } else if (map.get(num) != -1) {
                    res.add(s.substring(map.get(num), map.get(num) + 10));
                    map.put(num, -1);
                    // after the sequence has been added, mark it in the map
                } else {
                    // do nothing
                }
            }
        }

        return res;
    }

    int convertChatToInt(char ch) {
        if (ch == 'A') {
            return 1;
        } else if (ch == 'C') {
            return 2;
        } else if (ch == 'G') {
            return 3;
        }
        return 0;
    }
}

Question

link

Analysis

Please refer to [[ItInt5] Numbers Concatenation Max (Largest Number)(/blog/2014/08/17/Numbers-Concatenation-Max/).

Solution

Note that we can not override Comparator(Integer). So we must first convert int to string then sort.

Code

public class Solution {

    // this code should pass
    public String largestNumber(int[] num) {
        if (num == null || num.length == 0) {
            return "0";
        }
        String[] strs = new String[num.length];
        for (int i = 0; i < num.length; i++) {
            strs[i] = String.valueOf(num[i]);
        }
        Arrays.sort(strs, new LargerComparator());

        String res = "";
        for (String str : strs) {
            res = res + str;
        }
        return res;
    }

    class LargerComparator implements Comparator<String> {

        public int compare(String a, String b) {
            String first = a + b;
            String second = b + a;
            return second.compareTo(first);
        }
    }
}