415. Add Strings

需要改进的地方是求carry

应该用

int value = (x1 + x2 + carry) % 10;

            carry = (x1 + x2 + carry) / 10;

 class Solution {

    public String addStrings(String num1, String num2) {

        // Assuming num1 is longer.

        if (num1.length() < num2.length()) {

            Solution s = new Solution();

            return s.addStrings(num2, num1);

        }

        StringBuilder sb = new StringBuilder();

        int l1 = num1.length(), l2 = num2.length();

        int carry = 0;

        for (int i = 0; i < l1; i++) {

            int v1 = num1.charAt(l1 - 1 - i) - '0';

            int v2 = i >= l2 ? 0: num2.charAt(l2 - 1 - i) - '0';

            int sum = v1 + v2 + carry;

            if (sum >= 10) {

                carry = 1;

                sum -=10;

            } else {

                carry = 0;

            }

            sb.append((char)('0' + sum));

        }

        if (carry != 0) {

            sb.append('1');

        }

        return sb.reverse().toString();

    }

    

}

953. Verifying an Alien Dictionary

 二刷 07/2022

Version #2 HashMap

Time O(MN)

Space O(26) ~ O(1)

Runtime: 2 ms, faster than 36.78% of Java online submissions for Verifying an Alien Dictionary.

Memory Usage: 43.1 MB, less than 9.85% of Java online submissions for Verifying an Alien Dictionary.

class Solution {

    public boolean isAlienSorted(String[] words, String order) {

        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < order.length(); i++) {

            map.put(order.charAt(i), i);

        }

        for (int i = 1; i < words.length; i++) {

            if (!smaller(words[i - 1], words[i], map)) {

                return false;

            }

        }

        return true;

    }

    

    private boolean smaller(String a, String b, Map<Character, Integer> map) {

        int pa = 0, pb = 0;

        while (pa < a.length() && pb < b.length()) {

            char ca = a.charAt(pa);

            char cb = b.charAt(pb);

            if (ca == cb) {

                pa++;

                pb++;

                continue;

            }

            if (map.get(ca) < map.get(cb)) {

                return true;

            } else {

                return false;

            }

        }

        return a.length() <= b.length();

    }

}

一刷

Version #1 Array as HashMap

Runtime: 0 ms, faster than 100.00% of Java online submissions for Verifying an Alien Dictionary.

Memory Usage: 37.3 MB, less than 94.58% of Java online submissions for Verifying an Alien Dictionary. 

一开始想复杂了

其实只要比较相邻的word就可以了, 因为smaller than是transitive的

if a < b && b < c we can infer that a < c

Time O(word count * avg word length)

Space O(1) 

class Solution {

    public boolean isAlienSorted(String[] words, String order) {

        char[] map = new char[26];

        for (int i = 0; i < order.length(); i++) {

            map[order.charAt(i) - 'a'] = (char)('a' + i); 

        }

        String prev = null;

        for (String word : words) {

            if (prev != null && !smaller(prev, word, map)) {

                return false;

            }

            prev = word;

        }

        return true;

    }

    

    private boolean smaller(String a, String b, char[] map) {

        int i = 0;

        for (i = 0; i < a.length() && i < b.length(); i++) {

            char ca = map[a.charAt(i) - 'a'];

            char cb = map[b.charAt(i) - 'a'];

            if (ca != cb) {

               return ca < cb;

            }

            // continue comparing if ca == cb

        }

        // apple

        // app

        if (i < a.length()) {

            return false;

        }

       // Can be optimized to: return a.length() <= b.length()

        return true;

    }

}

621. Task Scheduler

Version #1 

好久没写java了，自己磕磕绊绊写了一版

用到了hashmap，没有利用tasks[i] is upper-case English letter这个条件

Time O(n)

Space O(1)

class Solution {

    public int leastInterval(char[] tasks, int n) {

        // A -> x -> x -> A -> x -> x -> A

        // (count(max chars) - 1) * (n + 1) + #chars that have max count

        if (n == 0) {

            return tasks.length;

        }

        int maxCount = 0;

        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < tasks.length; i++) {

            int cnt = map.getOrDefault(tasks[i], 0) + 1;

            maxCount = Math.max(maxCount, cnt);

            map.put(tasks[i], cnt);

        }

        int maxTasks = 0;

        for (Integer cnt : map.values()) {

            if (maxCount == cnt) {

                maxTasks++;

            }

        }

        return Math.max((maxCount - 1) * (n + 1) + maxTasks, tasks.length);

    }

}

Version #2 Optimized solution

Time O(n)

Space O(1)

这个testcase两次都错了

["A","A","A","B","B","B", "C","C","C", "D", "D", "E"]

2

class Solution {

    public int leastInterval(char[] tasks, int n) {

        // calculate the characters with max count

        int[] counts = new int[26];

        int maxCount = 0;

        int maxCountCharNum = 0;

        for (char task : tasks) {

            int i = task - 'A';

            counts[i]++;

            if (counts[i] > maxCount) {

                maxCountCharNum = 1;

                maxCount = counts[i];

            } else if (counts[i] == maxCount) {

                maxCountCharNum++;

            }

        }

        // n = 2

        // maxCountCharNum

        // (A B C) _divider_ (A B C) _ (A B C)

        // maxChars need (maxCount - 1) dividers to be seaparated

        // divider length = n - maxCountCharNum + 1

        // e.g. n = 2, maxCountCharNum = 1

        // A _ _ A _ _  divider = 2-1+1=2

        // if divider length <= 0 it means we don't need idle

        // e.g. n = 1, maxCountCharNum = 2

        // A B A B

        // so divider length = Math.max(0, n - maxCountCharNum + 1)

        // left chars = total chars - maxCountCharNum * maxCount

        // white spaces = divider length * (maxCount - 1) - left chars

        int idleCount = Math.max(0, n - maxCountCharNum + 1) * (maxCount - 1) - (tasks.length - maxCountCharNum * maxCount);

        return tasks.length + Math.max(0, idleCount);

    }

}