982. Triples with Bitwise AND Equal To Zero

Version #1 DP

37.50 %
class Solution {
    public int countTriplets(int[] A) {
        int N = 1 << 16;
        int[] dp = new int[N];
        for (int a : A) {
            dp[a] += 1;
        }
        for (int i = 0; i < 2; i++) {
            int[] temp = new int[N];
            for (int k = 0; k < N; k++) {
                for (int a : A) {
                    temp[k & a] += dp[k];
                }
            }
            dp = temp;
        }
        return dp[0];
    }
}

556. Next Greater Element III

96.55 %
class Solution {
    public int nextGreaterElement(int n) {
        char[] chars = String.valueOf(n).toCharArray();
        int i = 0;
        for (i = chars.length - 1; i > 0; i--) {
            if (chars[i] > chars[i - 1]) break;
        }
        int nextLargerDigit = i;
        if (i != 0) {
            for (int j = chars.length - 1; j > i; j--) {
                if (chars[j] > chars[i - 1] && chars[j] < chars[nextLargerDigit]) {
                    nextLargerDigit = j;
                }
            }
            char temp = chars[i - 1];
            chars[i - 1] = chars[nextLargerDigit];
            chars[nextLargerDigit] = temp;
            Arrays.sort(chars, i, chars.length);
        } else {
            return -1;
        }
        long result = Long.valueOf(new String(chars));
        return result > Integer.MAX_VALUE ? -1 : (int) result;
    }
}

249. Group Shifted Strings

3.04 %
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strings) {
map.computeIfAbsent(normalize(str), list -> new ArrayList<>()).add(str);
}
List<List<String>> result = new ArrayList<>();
for (List<String> list : map.values()) {
result.add(list);
}
return result;
}

private String normalize(String s) {
int offset = (int)(s.charAt(0) - 'a');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
sb.append((char) ('a' + ((s.charAt(i) - offset + 26) % 26)));
}
// System.out.println(sb.toString());
return sb.toString();
}

616. Add Bold Tag in String

Version #1 Merge Intervals

13.51 %
class Solution {
    public String addBoldTag(String s, String[] dict) {
// [interval[0], interval[1])
List<int[]> intervals = new ArrayList<>();
for (String word : dict) {
int start = 0;
while (start >= 0) {
start = s.indexOf(word, start);
if (start == -1) {
break;
}
intervals.add(new int[]{start, start + word.length()});
start++;
}
}
Collections.sort(intervals, Comparator.comparing(a -> a[0])); // only compare the start index
int i = 0;
List<int[]> merged = new ArrayList<>();
while (i < intervals.size()) {
int[] curr = intervals.get(i);
while (i < intervals.size() - 1 && intervals.get(i + 1)[0] <= curr[1]) {
curr[1] = Math.max(curr[1], intervals.get(i + 1)[1]);
i++;
}
merged.add(curr);
i++;
}
StringBuilder sb = new StringBuilder();
int prev = 0;
for (int[] interval : merged) {
sb.append(s.substring(prev, interval[0])).append("<b>").append(s.substring(interval[0], interval[1])).append("</b>");
prev = interval[1];
}
sb.append(s.substring(prev));
return sb.toString();
}
}

935. Knight Dialer

Version #1 DP

71.11 %
class Solution {
    public int knightDialer(int N) {
        int[][] map = new int[][]{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
        int[] prev = new int[10];
        int mod = (int)(1e9 + 7);
        Arrays.fill(prev, 1);
        for (int i = 2; i <= N; i++) {
            int[] curr = new int[10];
            for (int x = 0; x <= 9; x++) {
                for (int last : map[x]) {
                    curr[x] = (curr[x] + prev[last]) % mod;
                }
            }
            prev = curr;
        }
        int sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum = (sum + prev[i]) % mod;
        }
        return sum;
    }
}

421. Maximum XOR of Two Numbers in an Array

Version #1 PrefixTrie + DFS

We are passing two nodes into dfs simultaneously,  if we can choose branch of different value, we choose. Otherwise choose the same value

95.05 %
class Solution {
    class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}
public int findMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
for (int num : nums) {
insert(root, num);
}
return dfs(root.children[0], root.children[1] == null ? root.children[0] : root.children[1], 0);
}

private int dfs(TrieNode left, TrieNode right, int diff) {
TrieNode left0 = left.children[0], left1 = left.children[1];
TrieNode right0 = right.children[0], right1 = right.children[1];

if (left0 == null && left1 == null) {
return diff;
} else if (left0 != null && left1 != null && right0 != null && right1 != null) {
return Math.max(dfs(left0, right1, (diff << 1) + 1), dfs(left1, right0, (diff << 1) + 1));
} else if (left0 != null && right1 != null) {
return dfs(left0, right1, (diff << 1) + 1);
} else if (left1 != null && right0 != null) {
return dfs(left1, right0, (diff << 1) + 1);
} else if (left0 != null && right0 != null){
return dfs(left0, right0, (diff << 1));
} else if (left1 != null && right1 != null) {
return dfs(left1, right1, (diff << 1));
}
return 0;
}

private void insert(TrieNode root, int num) {
TrieNode curr = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null) {
curr.children[bit] = new TrieNode();
}
curr = curr.children[bit];
}
}
}

448. Find All Numbers Disappeared in an Array

69.09 %
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // If we see this number, we mark the number that at this index as negative
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        return result;
    }
}