LeetCode(105) -- 187,

P187. Repeated DNA Sequences (Medium)

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

My Solution

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> ans = new HashSet<>();
        if (s.length() <= 10) {
            return new ArrayList<>();
        }
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String substring = s.substring(i, i + 10);
            if (set.contains(substring)) {
                ans.add(substring);
            } else {
                set.add(substring);
            }
        }
        return new ArrayList<>(ans);
    }
}

81%

The Best Solution

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() <= 10) {
            return Collections.emptyList();
        }
        int mask = 0xFFFFF;
        boolean[] hashes = new boolean[1 << 20];
        int[] encoded = new int[128];
        encoded['A'] = 0;
        encoded['C'] = 1;
        encoded['G'] = 2;
        encoded['T'] = 3;

        int hash = 0;
        char[] sChars = s.toCharArray();
        Set<String> repeated = new HashSet<>();
        for (int i = 0; i < sChars.length; i++) {
            hash <<= 2;
            hash &= mask;
            hash += encoded[sChars[i]];
            if (i >= 9) {
                if (hashes[hash]) {
                    repeated.add(s.substring(i - 9, i + 1));
                }
                hashes[hash] = true;
            }
        }
        return new ArrayList(repeated);
    }
}

P199. Binary Tree Right Side View (Medium)

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

My Solution

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                if (i == size - 1) {
                    ans.add(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return ans;
    }
}

80%

The Best Solution

class Solution {
    List<Integer> ret;
    public List<Integer> rightSideView(TreeNode root) {
        ret = new ArrayList<>();
        trackRightFirst(root, 0);
        return ret;
    }

    private void trackRightFirst(TreeNode root, int level) {
        if (root == null) {
            return;
        }
        if (ret.size() == level) {
            ret.add(root.val);
        }
        trackRightFirst(root.right, level + 1);
        trackRightFirst(root.left, level + 1);
    }
}

从右边开始做dfs，用level 记录层级，比我的代码简洁很多。学习。

P201. Bitwise AND of Numbers Range (Medium)

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Solution

方法一：

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

方法二：

class Solution {
  public int rangeBitwiseAnd(int m, int n) {
    while (m < n) {
      // turn off rightmost 1-bit
      n = n & (n - 1);
    }
    return m & n;
  }
}