LeetCode(43) -- 949, 953, 961, 965, 970, 332

P949. Largest Time for Given Digits (Easy)

给四个数字，放在一个数组里，返回能组成的最大的24小时时间。

我的思路

这四个数字里至少要有一个0，1，2放在第一位。如果用2的话，第二位还必须要有一个小于4的数。 写了半天还有bug，看答案了

答案

class Solution {
    public String largestTimeFromDigits(int[] A) {
        int ans = -1;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (j != i) {
                    for (int k = 0; k < 4; k++) {
                        if (k != i && k != j) {
                            int l = 6 - i - j - k;
                            int hours = 10 * A[i] + A[j];
                            int minutes = 10 * A[k] + A[l];
                            if (hours < 24 && minutes < 60) {
                                ans = Math.max(ans, hours * 60 + minutes);
                            }
                        }
                    }
                }

            }
        }
        return ans >= 0 ? String.format("%02d:%02d", ans / 60, ans % 60) : "";
    }
}

23% 就是暴力求解，三层for循环.

最优解

class Solution {
    public String largestTimeFromDigits(int[] A) {
        int[] count = new int[10];
        for(int a : A) count[a]++;

        for(int i=2;i>=0;i--){
            if(count[i]>0){
                count[i]--;
                for(int j=9;j>=0;j--){
                    if(count[j]>0 && i*10 + j <=23){
                        count[j]--;
                        for(int k=6;k>=0;k--){
                            if(count[k]>0){
                                count[k]--;
                                for(int l=9;l>=0;l--){
                                    if(count[l]>0 && k*10+l<=59){
                                        return i+""+j+":"+k+""+l;
                                    }
                                }
                                count[k]++;
                            }
                        }
                        count[j]++;
                    }
                }
                count[i]++;
            }
        }
        return "";
    }
}

P953. Verifying an Alien Dictionary (Easy)

在一个外国词典里，26个字母的顺序是不一样的。给一个词典顺序和一组单词，判断它们是否都是按那个顺序排列的。

我的思路

本来想类比ASCII索引的办法，给每个字母也对应一个索引，想了半天没想出来，还想过用binary search，也没成功，最后只得用了hashmap查索引了。

我的代码

public class E_953_VerifyinganAlienDictionary {
    public boolean isAlienSorted(String[] words, String order) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < 26; i++) {
            map.put(order.charAt(i), i);
        }
        if (words.length < 2) {
            return true;
        }
        for (int i = 1; i < words.length; i++) {
            String current = words[i];
            String previous = words[i - 1];
            int minLength = Math.min(current.length(), previous.length());
            int j;
            for (j = 0; j < minLength; j++) {
                if (map.get(current.charAt(j)) > map.get(previous.charAt(j))) {
                    break;
                }
                if (map.get(current.charAt(j)) < map.get(previous.charAt(j))) {
                    return false;
                }
            }
            if (j == minLength && previous.length() > minLength) {
                return false;
            }
        }
        return true;
    }
}

41%

最优解

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] map = new int[26];
        for (int i = 0; i < order.length(); i++) {
            map[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < words.length - 1; i++) {
            if (!compare(words[i], words[i + 1], map)) {
                return false;
            }
        }
        return true;
    }

    public boolean compare(String s1, String s2, int[] map) {
        int l1 = s1.length();
        int l2 = s2.length();
        for (int i = 0, j = 0; i < l1 && j < l2; i++, j++) {
            if (s1.charAt(i) != s2.charAt(j)) {
                if (map[s1.charAt(i) - 'a'] > map[s2.charAt(j) - 'a']) {
                    return false;
                } else {
                    return true;
                }
            }
        }
        if (l1 > l2) return false;
        return true;
    }
}

这是正确答案，用这个。

P961. N-Repeated Element in Size 2N Array (Easy)

在一个长度为2N的数组里，有N+1个不同的数。只有一个数重复了N次。问这个重复了N次的数字是谁。

我的思路

长度为2N，有一个数重复了N次，说明另外N个数，每个数只能出现一次。所以只要发现有重复的，必然是那个重复了N次的数。又因为范围只在0到10000，所以就做了一个长度为10000的布尔型数组，用来记录每个数是否出现过。

我的代码

class Solution {
    public int repeatedNTimes(int[] A) {
        boolean[] map = new boolean[10000];
        for (int i = 0; i < A.length; i++) {
            if (map[A[i]]) {
                return A[i];
            }
            map[A[i]] = true;
        }
        return 0;
    }
}

100%

最优解

class Solution {
    public int repeatedNTimes(int[] A) {
        int i = 0, j = 0, n = A.length;
        while (i == j || A[i] != A[j]) {
            i = (int)(Math.random() * n);
            j = (int)(Math.random() * n);
        }
        return A[i];
    }
}

这个解法很奇特，每次随机找两个数进行比较，如果不相等就接着再找两个，直到相等为止。

P965. Univalued Binary Tree (Easy)

检验一个二叉树的所有节点是否只含有完全相同的值。

我的思路

遍历树，遇到不同的值就返回false.

我的代码

class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left != null && root.val != root.left.val) {
            return false;
        }
        if (root.right != null && root.val != root.right.val) {
            return false;
        }
        return isUnivalTree(root.left) && isUnivalTree(root.right);
    }
}

100%

最优解

class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        return checkValue(root.left, root.val) && checkValue(root.right, root.val);
    }

    public boolean checkValue(TreeNode node, int value) {
        if (node == null) {
            return true;
        }
        if (node.val == value) {
            return checkValue(node.left, value) && checkValue(node.right, value);
        }
        return false;
    }
}

P970. Powerful Integers (Easy)

两个正整数x,y，如果一个整数可以表示为他们的幂的和，则这个整数叫做powerful。给一个范围，问这个范围内所有powerful的数的集合。

我的思路

依次遍历x的幂和y的幂，嵌套循环，只要他们的和小于bound，就放到set里面。

我的代码

public class E_970_PowerfulIntegers {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        HashSet<Integer> set = new HashSet<>();
        int xPower = 1;
        while (xPower < bound) {
            int yPower = 1;
            int sum = xPower + yPower;
            while (sum <= bound) {
                set.add(sum);
                if (y == 1) {
                    break;
                }
                yPower *= y;
                sum = xPower + yPower;
            }
            if (x == 1) {
                break;
            }
            xPower *= x;
        }
        return new ArrayList<>(set);
    }

    public static void main(String[] args) {
        List<Integer> integers = new E_970_PowerfulIntegers().powerfulIntegers(2, 1, 10);
        System.out.println("integers.toString() = " + integers.toString());
    }
}

99%

最优解

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        List<Integer> list = new LinkedList<>();
        for(int i = 1; i <= bound; i = i * x){
            for(int j = 1; i + j <= bound; j = j * y){
                if (!list.contains(i + j)) {
                    list.add(i + j);
                }
                if(y == 1)  break;
            }
            if(x == 1)  break;
        }
        return list;
    }
}

没用hashset，直接用list的contain方法了。思路差不多，但是代码比我的干净，值得学习。

P332. Reconstruct Itinerary (Medium)

一个数组，其中的每个元素都是一个航班的起始点和到达点。从JFK出发，构建一个路径。如果有多于一个正确的路径，返回字母顺序靠前的。

我的思路

把所有的起始点存到一个HashMap中，对应的value值用一个List表示。DFS来搜索。 有一点思路，代码写完有BUG。

最优解1

class Solution {
    Map<String, PriorityQueue<String>> map = new HashMap<>();
    LinkedList<String> result = new LinkedList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            if (!map.containsKey(ticket.get(0))) {
                map.put(ticket.get(0), new PriorityQueue<String>());
            }
            map.get(ticket.get(0)).offer(ticket.get(1));
        }

        dfs("JFK");
        return result;
    }

    public void dfs(String s) {
        PriorityQueue<String> pq = map.get(s);

        while (pq != null && !pq.isEmpty()) {
            dfs(pq.poll());
        }

        result.addFirst(s);
    }
}

最优解2

class Solution {
    HashMap<String, PriorityQueue<String>> adjacencyList = new HashMap<String, PriorityQueue<String>>();
    LinkedList<String> result = new LinkedList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {

        for (List<String> ticket: tickets){
            String source = ticket.get(0);
            String destination = ticket.get(1);
            if (adjacencyList.containsKey(source)) {
                adjacencyList.get(source).add(destination);
            } else {
                PriorityQueue<String> queue = new PriorityQueue<String>();
                queue.add(destination);
                adjacencyList.put(source, queue);
            }
        }
        dfs("JFK");
        return result;
    }

    private void dfs(String source) {
        PriorityQueue<String> destinations = adjacencyList.get(source);
        while (destinations != null && destinations.isEmpty() == false) {
            dfs(destinations.poll());
        }
        result.addFirst(source);
    }
}