LeetCode(60) -- 45, 49, 103

P45. Jump Game II (Medium)

一个数组，起始点在第一个数字上。每个数字代表从该位置最多可以跳多少步。问至少需要多少步能跳可末尾？

我的思路

动态规划，每一步都有A[i]种选择，选择哪一个取决于选择这个后，从那个位置最少多少步才能跳到最后。但是实现的时候还是需要从最左边往右推进，而不是重复地计算。每个位置，都要记录下来最少多少步就可以跳到该位置。

我的代码

public class M_45_JumpGameII {
    public int jump(int[] nums) {
        int[] memo = new int[nums.length];
        memo[0] = 0;
        for (int i = 1; i < memo.length; i++) {
            memo[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            int j = i + 1;
            while (j <= i + nums[i]) {
                memo[j] = Math.min(memo[i] + 1, memo[j]);
                j++;
            }
        }
        return memo[nums.length - 1];
    }

    public static void main(String[] args) {
        int jump = new M_45_JumpGameII().jump(new int[]{2, 3, 1, 1, 4});
        System.out.println("jump = " + jump);

    }
}

18%

最优解

class Solution {
    public int jump(int[] nums) {
        if(nums.length < 2)
            return 0;
        int n = nums.length;
        int ladder = nums[0];
        int stairs = nums[0];
        int jump = 1;
        for (int i = 1; i < n - 1; i++) {
            if((i + nums[i]) > ladder) {
                ladder = i + nums[i];
            }
            stairs--;
            if(stairs == 0){
                jump++;
                stairs = ladder - i;
            }
        }
        return jump;
    }
}

讨论区

public int jump(int[] A) {
	int jumps = 0, curEnd = 0, curFarthest = 0;
	for (int i = 0; i < A.length - 1; i++) {
		curFarthest = Math.max(curFarthest, i + A[i]);
		if (i == curEnd) {
			jumps++;
			curEnd = curFarthest;
		}
	}
	return jumps;
}

用这个，简单明了。

P49. Group Anagrams (Medium)

把所有用相同字母组成的单词分成一组。

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

我的思路

用hashmap存所有的字母组合。把相同的字母组合归为一类。

我的代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<Statistic, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int[] table = new int[26];
            for (char c : s.toCharArray()) {
                table[c - 'a']++;
            }
            Statistic statistic = new Statistic(table);
            List<String> list = map.getOrDefault(statistic, new ArrayList<>());
            list.add(s);
            map.put(statistic, list);
        }
        return new ArrayList<>(map.values());
    }

    class Statistic{
        int[] table;

        public Statistic(int[] table) {
            this.table = table;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Statistic statistic = (Statistic) o;
            return Arrays.equals(table, statistic.table);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(table);
        }
    }
}

97%

最优解

class Solution {
    // idea here is to
    public List<List<String>> groupAnagrams1(String[] strs) {
        if(strs == null || strs.length == 0)
            return new ArrayList<>();

        Map<String, List<String>> map = new HashMap<>();

        for(String s: strs){
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String str = new String(charArray);
            map.putIfAbsent(str, new ArrayList<>());
            map.get(str).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList();
        Map<String, List<String>> codeMap = new HashMap();
        for (String current : strs) {
            String charRepresentation = getCharRepresentation(current);
            if (codeMap.containsKey(charRepresentation)) {
                codeMap.get(charRepresentation).add(current);
            } else {
                List<String> codeValues = new ArrayList();
                codeValues.add(current);
                codeMap.put(charRepresentation, codeValues);
                result.add(codeValues);
            }
        }

        return result;
    }

    private String getCharRepresentation(String value) {
        char[] freq = new char[26];
        for (char c : value.toCharArray()) {
            freq[c - 'a']++;
        }

        return new String(freq);
    }
}

P103. Binary Tree Zigzag Level Order Traversal (Medium)

二叉树，之字形遍历。第一行从左向右，第二行从右向左，第三行从左向右……

我的思路

层级遍历时用一个Queue， 但因为要换方向，所以每次放入下一层节点以前，先把所有节点放进stack中。弹出的时候，再根据是从左向右或者从右向左，决定先放左子节点还是先放右子节点。

我的代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean leftToRight = true;
        Stack<TreeNode> stack = new Stack<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                level.add(node.val);
                stack.push(node);
            }
            while (!stack.isEmpty()) {
                TreeNode pop = stack.pop();
                if (leftToRight) {
                    if (pop.right != null) {
                        queue.add(pop.right);
                    }
                    if (pop.left != null) {
                        queue.add(pop.left);
                    }
                } else {
                    if (pop.left != null) {
                        queue.add(pop.left);
                    }
                    if (pop.right != null) {
                        queue.add(pop.right);
                    }
                }
            }
            leftToRight = !leftToRight;
            ans.add(level);
        }
        return ans;
    }
}

98%

最优解

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean isOdd = true;
        while(!q.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            int size = q.size();
            for(int i = 0; i < size; ++i) {
                TreeNode n = q.poll();
                if(isOdd) {
                    tmp.add(n.val);
                } else {
                    tmp.addFirst(n.val);
                }
                if(n.left != null) q.add(n.left);
                if(n.right != null) q.add(n.right);
            }
            res.add(tmp);
            isOdd = !isOdd;
        }
        return res;
    }
}

用linkedList活用，可以加在前面或者加在后面。