Mock Interview: Google #4

実行時間は本当に...どうしてこうなるの

Height Checker

class Solution {
    public int heightChecker(int[] heights) {
        int[] target = heights.clone();
        Arrays.sort(target);
        int count = 0;
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] != target[i]) {
                count++;
            }
        }
        
        return count;
    }
}

Runtime: 1 ms, faster than 75.67% of Java online submissions for Height Checker.
Memory Usage: 39.1 MB, less than 6.56% of Java online submissions for Height Checker.
これを解くのに3分しかかからなかった.

私はわざと、ほほほ
これって10分以内に終わるんじゃないですかね?^
やったけど…^^...

class Solution {
    public int heightChecker(int[] heights) {
        int[] heightToFreq = new int[101];
        
        for (int height : heights) {
            heightToFreq[height]++;
        }
        
        int result = 0;
        int curHeight = 0;
        
        for (int i = 0; i < heights.length; i++) {
            while (heightToFreq[curHeight] == 0) {
                curHeight++;
            }
            
            if (curHeight != heights[i]) {
                result++;
            }
            heightToFreq[curHeight]--;
        }
        
        return result;
    }
}

Long Pressed Name

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int[] c = new int[26];
        
        for (int i = 0; i < typed.length(); i++) {
            c[typed.charAt(i) - 'a']++;
        }
        
        for (int j = 0; j < name.length(); j++) {
            if (c[name.charAt(j) - 'a'] == 0) {
                return false;
            } else {
                c[name.charAt(j) - 'a']--;
            }
        }
        
        return true; 
    }
}

75/94 test cases passed
問題を読み間違えたのでdpを書こうと思ったのですが、順序を考えていることに気づきました.

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        Queue<Character> n = new LinkedList<Character>();
        Queue<Character> t = new LinkedList<Character>();
        
        for (int i = 0; i < name.length(); i++) {
            n.add(name.charAt(i));
        }
        
        for (int j = 0; j < typed.length(); j++) {
            t.add(typed.charAt(j));
        }
        
        while (! n.isEmpty() && ! t.isEmpty()) {
            if (n.peek() == t.peek()) {
                n.remove();
                t.remove();
            } else {
                t.remove();
            }
        }
        
        return n.isEmpty();
    }
}

87/94 test cases passed.
最近ハマっている列...
これには、エンディングでニコニコしたり、真ん中に新しい字があると無視したりする欠点があります.

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        Queue<Character> n = new LinkedList<Character>();
        Queue<Character> t = new LinkedList<Character>();
        
        for (int i = 0; i < name.length(); i++) {
            n.add(name.charAt(i));
        }
        
        for (int j = 0; j < typed.length(); j++) {
            t.add(typed.charAt(j));
        }
        
        while (! n.isEmpty() && ! t.isEmpty()) {
            if (n.peek() == t.peek()) {
                int cur = n.peek();
                int nnum = 0;
                int tnum = 0;
                
                while (! n.isEmpty() && n.peek() == cur) {
                    n.remove();
                    nnum++;
                }
                
                while (! t.isEmpty() && t.peek() == cur) {
                    t.remove();
                    tnum++;
                }
                
                if (tnum < nnum) {
                    return false; 
                }
            } else {
                return false; 
            }
        }
        
        
        return (n.isEmpty() && t.isEmpty());
    }
}

Runtime: 4 ms, faster than 6.87% of Java online submissions for Long Pressed Name.
Memory Usage: 39.2 MB, less than 5.11% of Java online submissions for Long Pressed Name.
汚れたコード&レスポンスなし実行時..^^
でも解けてよかった.
two-pointerを使うために、while loopをむやみに投げて、いくつか数えてください.
真ん中に雑物があれば捨てます~~

class Solution {
    public boolean isLongPressedName(String name, String typed) {

        // two pointers to the "name" and "typed" string respectively
        int np = 0, tp = 0;
        // convert the string to array of chars, for ease of processing later.
        char[] name_chars = name.toCharArray();
        char[] typed_chars = typed.toCharArray();

        // advance two pointers, until we exhaust one of the strings
        while (np < name_chars.length && tp < typed_chars.length) {
            if (name_chars[np] == typed_chars[tp]) {
                np += 1;
                tp += 1;
            } else if (tp >= 1 && typed_chars[tp] == typed_chars[tp - 1]) {
                tp += 1;
            } else {
                return false;
            }
        }

        // if there is still some characters left *unmatched* in the origin string,
        // then we don't have a match.
        // e.g. name = "abc" typed = "aabb"
        if (np != name_chars.length) {
            return false;
        } else {
            // In the case that there are some redundant characters left in typed
            // we could still have a match.
            // e.g. name = "abc" typed = "abccccc"
            while (tp < typed_chars.length) {
                if (typed_chars[tp] != typed_chars[tp - 1])
                    return false;
                tp += 1;
            }
        }

        // both strings have been consumed.
        return true;
    }
}

two pointerより簡潔なverソリューション
上は同じですが、最後にwhile(tpRuntime: 1 ms, faster than 48.56% of Java online submissions for Long Pressed Name.
Memory Usage: 38.5 MB, less than 17.73% of Java online submissions for Long Pressed Name.