记录

Today:
1. Merge two binary trees.
Make sure to use dummy nodes -- much simpler.



2. Hamming Distancepublic
class Solution {
    public int hammingDistance(int x, int y) {
        int i = x ^ y;
        int sum = 0;
        while (i != 0) {
            sum += i & 1;
            i = i >>> 1;
        }
        return sum;
    }
}

Make up

0809 1. Maximum Sum of 3 Non-Overlapping Subarrays

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSumOfThreeSubarrays = function(nums, k) {
    if (nums == null || nums.length === 0) {return [];}
    const sum = [];
    let localSum = 0;
    // !!!! must do it in o(n)
    for (let i = 0; i < nums.length; i++) {
        localSum += nums[i];
        if (i >= k) {
            localSum -= nums[i - k];
        }
        if (i >= k - 1) {
            sum[i - k + 1] = localSum;
        }
        
    }
    console.log(sum)
    const leftMax = [];
    let maxIndex = 0;
    for (let i = 0; i < sum.length; i++) {
        leftMax[i] = maxIndex = sum[i] > sum[maxIndex] ? i : maxIndex; // !!!!! you will also need to update the current max index !!!
    }
    console.log(leftMax);
    const rightMax = [];
    maxIndex = sum.length - 1;
    for (let i = sum.length - 1; i >= 0; i--) {
        rightMax[i] = maxIndex = sum[i] >= sum[maxIndex] ? i : maxIndex;
    }
    let maxTriple;
    for (let j = k; j + 2 * k - 1 < nums.length; j++) { // !!!!! here using sum and using nums have different meaning because they have different length !!!!!
        const i = leftMax[j - k];
        const m = rightMax[j + k];
        if ((j === k) || (sum[i] + sum[j] + sum[m] > sum[maxTriple[0]] + sum[maxTriple[1]] + sum[maxTriple[2]])) {
            maxTriple = [i, j, m];
        }
    }
    return maxTriple;
};

0114 The Maze III

/**
* @param {number[][]} maze
* @param {number[]} ball
* @param {number[]} hole
* @return {string}
*/
var findShortestWay = function(maze, ball, hole) {
    // !!! this is a shortest path problem
    // 1. if is unweighted graph, use BFS (in this case just degenerated Dijkstra)
    // 2. if is weighted graph, use Dijkstra,
    // consult the maze II, why BFS has the same complexity as DFS? Because this kind of problems are weighted graph, so you
    // cannot just use BFS to solve it fast. You need to use Dijkstra. Thus using BFS you just brute force search, which is the
    // same as DFS.
    // use dijkistra with pq
   
    // now the challenge is: 1. stop at any time, that's not too difficult,
    // 2. need to get the path. how? need to backtrack since we are not using dfs.
    // need to keep a backtrack map
    // for each node, keep the smallest path to this current node using the prev map.
    // but they don't want the node path, they want the direction path, we could still get it, but is there a way to get it directly? we store the complete path on each node? that is also doable.
    class Heap {
        constructor (data, compare) {
            this.data = data || []
            this.compare = compare || ((a, b) => a - b);
            const lastParent = this.getParent(this.data.length - 1);
            for (let i = lastParent; i >= 0; i--) {
                this.siftDown(i);
            }
        }
        getParent (i) {
            return Math.trunc((i - 1) / 2);
        }
        swap (i, j) {
            ;[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
        }
        siftDown (i) {
            let min = i;
            const left = 2 * i + 1;
            const right = 2 * i + 2;
            for (let index of [left, right]) {
                if (index < this.data.length && this.compare(this.data[index], this.data[min]) < 0) {
                    min = index;
                }
            }
            if (min !== i) {
                this.swap(min, i);
                this.siftDown(min);
            }
        }
        siftUp (i) {
            const parent = this.getParent(i);
            if (this.compare(this.data[i], this.data[parent]) < 0) {
                this.swap(parent, i);
                this.siftUp(parent);
            }
        }
        push (val) {
            this.data.push(val);
            this.siftUp(this.data.length - 1);
        }
        get size () {
            return this.data.length;
        }
        peak () {
            return this.data[0];
        }
        pop () {
            if (this.size === 0) {return undefined}
            const val = this.peak();
            this.swap(0, this.data.length - 1);
            this.data.pop();
            this.siftDown(0);
            return val;
        }
    }
   
    if (maze == null || maze.length === 0) {
        return 'impossible';
    }
    const rowLen = maze.length;
    const colLen = maze[0].length;
    const dist = Array(rowLen).fill().map(() => Array(colLen).fill(Infinity));
    const path = Array(rowLen).fill().map(() => Array(colLen).fill('z')); // !!! init to z for infinity
    dist[ball[0]][ball[1]] = 0;
    path[ball[0]][ball[1]] = '';
    const compare = (dist1, path1, dist2, path2) => {
        if (dist1 === dist2) {
            if (path1 < path2) {
                return -1;
            } else if (path1 > path2) {
                return 1
            } else {
                return 0;
            }
        } else {
            return dist1 - dist2;
        }
    }
    const heap = new Heap([], (a, b) => compare(a[2], a[3], b[2], b[3]));
    heap.push([...ball, 0, '']); // !!! have 4 els now
    while (heap.size > 0) {
        const [x, y, aDist, aPath] = heap.pop();
        if (compare(aDist, aPath, dist[x][y], path[x][y]) > 0) {continue;}
        const moves = [[0, 1, 'r'], [0, -1, 'l'], [1, 0, 'd'], [-1, 0, 'u']];
        for (let [dx, dy, dir] of moves) {
            let newX = x;
            let newY = y;
            let newDist = aDist;
            // !!! all newX + dx, newY + dy
            let found = false;
            while (newX + dx >= 0 && newX + dx < rowLen && newY + dy >= 0 && newY + dy < colLen && maze[newX + dx][newY + dy] === 0) {
                newX += dx;
                newY += dy;
                newDist++;
                // !!!!! cannot just stop here, because you not only need to find it, but you need to find the lexically smallest
                // but you need to test here
                if (newX === hole[0] && newY === hole[1]) {
                    found = true;
                    break;
                }
            }
            // 1. compare the dist; 2. if that equal, compare the path
            const newPath = path[x][y] + dir;
            if (compare(newDist, newPath, dist[newX][newY], path[newX][newY]) < 0) { // !!!newX, newY not x, y in the 2d array !!!!
                // !!! that's because we are comparing with the prev value of same point, not values of this and prev point
                dist[newX][newY] = newDist;
                path[newX][newY] = newPath;
                if (!found) {
                    heap.push([newX, newY, newDist, newPath]);
                }
            }
        }
    }
    const val = path[hole[0]][hole[1]];
    return val === 'z' ? 'impossible' : val;
};

1023 5. Bomb Enemy

/**
* @param {character[][]} grid
* @return {number}
*/
var maxKilledEnemies = function(grid) {
        if (grid == null || grid.length === 0) {
            return 0;
        }
        const rowLen = grid.length;
        const colLen = grid[0].length;
        const create2d = () => Array(rowLen).fill().map(() => Array(colLen).fill(0));
        const left = create2d();
        const right = create2d();
        const top = create2d();
        const bottom = create2d();
        for (let i = 0; i < rowLen; i++) {
            for (let j = 0; j < colLen; j++) {
                const k = colLen - 1 - j;
                if (j === 0) {
                    left[i][j] = 0;
                    right[i][k] = 0;
                } else {
                    // for left
                    if (grid[i][j - 1] === 'W') {
                        left[i][j] = 0;
                    } else if (grid[i][j - 1] === 'E') {
                        left[i][j] = left[i][j - 1] + 1;
                    } else {
                        left[i][j] = left[i][j - 1];
                    }
                    // for right
                    if (grid[i][k + 1] === 'W') {
                        right[i][k] = 0;
                    } else if (grid[i][k + 1] === 'E') {
                        right[i][k] = right[i][k + 1] + 1; // !!! which part + 1
                    } else {
                        right[i][k] = right[i][k + 1];
                    }
                    
                }
            }
        }
        for (let j = 0; j < colLen; j++) {
            for (let i = 0; i < rowLen; i++) {
                if (i === 0) {
                    top[i][j] = 0;
                    bottom[i][j] = 0;
                } else {
                    // for top
                    if (grid[i - 1][j] === 'W') {
                        top[i][j] = 0;
                    } else if (grid[i - 1][j] === 'E') {
                        top[i][j] = top[i - 1][j] + 1;
                    } else {
                        top[i][j] = top[i - 1][j];
                    }
                    // for bottom
                    const k = rowLen - 1 - i; // !!! here it is rowLen not colLen
                    if (grid[k + 1][j] === 'W') {
                        bottom[k][j] = 0;
                    } else if (grid[k + 1][j] === 'E') {
                        bottom[k][j] = bottom[k + 1][j] + 1;
                    } else {
                        bottom[k][j] = bottom[k + 1][j];
                    }
                }
            }
        }
        let max = 0;
        for (let i = 0; i < rowLen; i++) {
            for (let j = 0; j < colLen; j++) {
                if (grid[i][j] === '0') {
                    const val = top[i][j] + bottom[i][j] + left[i][j] + right[i][j];
                    max = Math.max(val, max);
                }
            }
        }
        return max;
};

1. Array Partition I

public class Solution {
    public int arrayPairSum(int[] nums) {
        if (nums == null) {
            return 0;
        }
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums;
        }
        return sum;
    }
}
2. Number Complement

public class Solution {
    public int findComplement(int num) {
        int ones = Integer.MAX_VALUE;
        while (ones > num) {
            ones = ones >>> 1;
        }
        if (ones < num) {
            ones = (ones << 1) + 1;
        }
        return ones - num;
    }
}


This is awkward. Need a better solution.

This is a tricky one:

  1. bit-wise operation will work on all bits
  2. bit-wise operatior has low precedence
  3. integer overflow.

A better solution:

    public int findComplement(int num) {
        int one = 1;
        while ((one -1) < num) {
            one = one << 1;
        }
        return one - 1 - num;
    }

1. Reshape the Matrix

Note: index starts from 0

public class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        // assume inputs are valid
        int numRows = nums.length;
        int numCols = nums[0].length;
        if (numRows * numCols != r * c) {
            return nums;
        }
        int[][] results = new int[r][c];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                int index = i * numCols + j;
                results[index / c][index % c] = nums[i][j];
            }
        }
        return results;
    }
}[/i]

2. Reverse Words in a String III
Note: while loop step increment!!! Always the same trap.


public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }  
        String[] parts = s.split(" ");
        for (int i = 0; i < parts.length; i++) {
            parts[i] = reverse(parts[i]);
        }
        return String.join(" ", parts);
    }

    public String reverse (String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = chars.length - 1;
        while (left < right) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            left++;
            right--;
        }
        return new String(chars);
    }
}

[/i][/i]

1. Keyboard Row


public class Solution {
    public String[] findWords(String[] words) {
        char[] first = "qwertyuiop".toCharArray();
        char[] second = "asdfghjkl".toCharArray();
        char[] third = "zxcvbnm".toCharArray();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        putIntoMap(map, first, 1);
        putIntoMap(map, second, 2);
        putIntoMap(map, third, 3);
        List<String> list = new ArrayList<String>();
        for (String word : words) {
            if (valid(word, map)) {
                list.add(word);
            }
        }
        return list.toArray(new String[0]);
    }


    public void putIntoMap (Map<Character, Integer> map, char[] chars, int num) {
        for (char c : chars) {
            map.put(c, num);
        }
    }

    public boolean valid (String word, Map<Character, Integer> map) {
        if (word == null || word.length() == 0) {
            return true;
        }
        word = word.toLowerCase();
        int num = map.get(word.charAt(0));
        for (int i = 0; i < word.length(); i++) {
            int oneNum = map.get(word.charAt(i));
            if (oneNum != num) {
                return false;
            }
        }
        return true;
    }
}


Seems very stupid. Is there a cleaner solution?

sicilianee 发表于 2017-6-24 15:21
1. Keyboard Row

Don't have any elegant solution in Java. Just small improvement:
!!! NOTE:
1. Remember to convert to lower case.
2. for each loop of java is diff from js, need to declare type


public class Solution {
    public String[] findWords(String[] words) {
        if (words == null || words.length == 0) {
            return new String[0];
        }
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        put("qwertyuiop".toCharArray(), map, 0);
        put("asdfghjkl".toCharArray(), map, 1);
        put("zxcvbnm".toCharArray(), map, 2);
        List<String> results = new ArrayList<String>();
        for (String w : words) {
            if (test(w, map)) {
                results.add(w);
            }
        }
        return results.toArray(new String[0]);
    }
   
    public void put (char[] chars, Map<Character, Integer> map, int num) {
        for (char c : chars) {
            map.put(c, num);
        }
    }
   
    public boolean test (String w, Map<Character, Integer> map) {
        if (w == null || w.length() <= 0) {
            return true;
        }
        w = w.toLowerCase();
        int num = map.get(w.charAt(0));
        for (int i = 0; i < w.length(); i++) {
            if (map.get(w.charAt(i)) != num) {
                return false;
            }
        }
        return true;
    }
}

1. Distribute Candies

* we don't need a map. A set is enough.

public class Solution {
    public int distributeCandies(int[] candies) {
        // check
        // get half
        // put each into set
        // ret min
        if (candies == null || candies.length == 0) {
            return 0;
        }
        int cap = candies.length / 2;
        Set<Integer> set = new HashSet();
        for (int candy : candies) {
            set.add(candy);
        }
        return Math.min(set.size(), cap);
    }
}

2. Fizz Buzz

public class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList();
        for (int i = 1; i <= n; i++) {
            boolean fizz = (i % 3) == 0;
            boolean buzz = (i % 5) == 0;
            String s;
            if (fizz && buzz) {
                list.add("FizzBuzz");
            } else if (fizz) {
                list.add("Fizz");
            } else if (buzz) {
                list.add("Buzz");
            } else {
                list.add(String.valueOf(i));
            }
        }
        return list;
    }
}


We could just use 15

public class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList();
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                list.add("FizzBuzz");
            } else if (i % 3 == 0) {
                list.add("Fizz");
            } else if (i % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(String.valueOf(i));
            }
        }
        return list;
    }
}



- we could just use 15
- type, num -> string, String.valueOf()

3. Reverse String

Make up for last Friday's one missing problem.

- This is a classic one. Easy but I always forget to update the pointers.

public class Solution {
    public String reverseString(String s) {
        // check
        // two pointers, mv, update
        if (s == null || s.length() == 0) {
            return s;
        }
        char[] chars = s.toCharArray();
        int left = 0;
        int right = s.length() -1;
        while (left < right) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            left++;
            right--;
        }
        return new String(chars);
    }
}

1. Complex Number Multiplication

public class Solution {
    public String complexNumberMultiply(String a, String b) {
        int[] as = getNumbers(a);
        int[] bs = getNumbers(b);
        int real = as[0] * bs[0] - as[1] * bs[1];
        int virtual = as[0] * bs[1] + as[1] * bs[0];
        return real + "+" + virtual + "i";
    }
   
    public int[] getNumbers (String str) {
        String[] parts = str.split("\\+");
        return new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1].substring(0, parts[1].length() - 1))};
    }
}
Feels very stupid. Use regular expression is better?

Note: Java split accepts a regular expression string, not a normal string.


2. Battleships in a Board

public class Solution {
    public int countBattleships(char[][] board) {
        if (board == null) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (isStart(board, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isStart (char[][] board, int x, int y) {
        boolean selfGood = board[x][y] == 'X';
        boolean xGood = x == 0 || board[x - 1][y] == '.';
        boolean yGood = y == 0 || board[x][y - 1] == '.';
        return xGood && yGood && selfGood;
    }
}

1. Counting Bits
__Important__: bit-wise manipulation in Java has very low precedence. Use parentheses!


public class Solution {
    public int[] countBits(int num) {
        int[] results = new int[num + 1];
        for (int i = 0; i < num + 1; i++) {
            results = countSingle(i);
        }
        return results;
    }
   
    private int countSingle (int num) {
        int count = 0;
        while (num != 0) {
            count = count + (num & 1);
            num = num >>> 1;
        }
        return count;
    }
}


2. Average of Levels in Binary Tree
__Note__:
Double, int, double conversion.

/**
* 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<Double> averageOfLevels(TreeNode root) {
        List<Double> results = new LinkedList<Double>();
        List<Double> current = new LinkedList<Double>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        q.add(null);
        while (!q.isEmpty()) {
            TreeNode node = q.remove();
            if (node != null) {
                current.add((double) node.val);
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            } else {
                int size = current.size();
                double sum = 0;
                for (Double num : current) {
                    sum += num;
                }
                Double average = sum / size;
                current.clear();
                results.add(average);
                if (!q.isEmpty()) {
                    q.add(null);
                }
            }
        }
        return results;
    }
}




补充内容 (2017-7-21 13:17):
Need to improve the 2nd one when you have time

1. Island Perimeter

public class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[j] == 1) {
                    count += countSingle(grid, i, j);
                }
            }
        }
        return count;
    }
   
    // count only thoes islands
    private int countSingle (int[][] grid, int x, int y) {
        int count = 0;
        if (x == 0 || grid[x-1][y] == 0) {
            count++;
        }
        if (x == grid.length - 1 || grid[x + 1][y] == 0) {
            count++;
        }
        if (y == 0 || grid[x][y - 1] == 0) {
            count++;
        }
        if (y == grid[0].length - 1 || grid[x][y + 1] == 0) {
            count++;
        }
        return count;
    }
}




2. Next Greater Element I


public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Map<Integer, Integer> dict = greaterDict(nums);
        int[] results = new int[findNums.length];
        for (int i = 0; i < findNums.length; i++) {
            results[i] = dict.get(findNums[i]);
        }
        return results;
    }

    private Map<Integer, Integer> greaterDict (int[] nums) {
        Map<Integer, Integer> dict = new HashMap();
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0;
        while (i < nums.length) {
            int num = nums[i];
            if (!stack.isEmpty() && stack.peek() < num) {
                dict.put(stack.pop(), num);
            } else {
                stack.push(num);
                i++;
            }
        }
        while (!stack.isEmpty()) {
            dict.put(stack.pop(), -1);
        }
        return dict;
    }
}

1. Find Bottom Left Tree Value

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int value = 0;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.remove();
            value = node.val;
            if (node.right != null) {
                q.add(node.right);
            }
            if (node.left != null) {
                q.add(node.left);
            }
        }
        return value;
    }
}

2. Queue Reconstruction by Height

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (p1, p2) ->  p1[0] == p2[0] ? p1[1] - p2[1] : -(p1[0] - p2[0]));
        List<int[]> result = new LinkedList();
        for (int[] person : people) {
            result.add(person[1], person);
        }
        return result.toArray(new int[0][0]);
    }
}


TODO: could do without extra space. Note the idea is the same, this above solution illustrates the big picture better. The optimization is just do the insertion in place.