Mock Interview: Microsoft #8

Rotate String

class Solution {
    public boolean rotateString(String A, String B) {
        
        if (A.length() != B.length()) {
            return false;
        } 
        return helper(A, B, 0);
    }
    
    private boolean helper(String A, String B, int times) {
        if (A.equals(B)) {
            return true;
        }
        
        if (times >= A.length()) {
            return false; 
        }
        
        String newA = A.substring(1) + A.substring(0, 1);
        
        return helper(newA, B, times + 1);
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate String.
Memory Usage: 37.4 MB, less than 23.53% of Java online submissions for Rotate String.
ルソンは明確だと思っていたのですが・・・RG?^^
不気味な物語
私の面接時間はきついです.

class Solution {
    public boolean rotateString(String A, String B) {
        
        if (A.length() != B.length()) {
            return false;
        } 
        
        if (A.length() == 0) {
            return true; 
        }
        return helper(A, B, 0);
    }
    
    private boolean helper(String A, String B, int times) {
        if (times >= A.length()) {
            return false; 
        }
        
        if (A.equals(B)) {
            return true;
        }
        
        String newA = A.substring(1) + A.substring(0, 1);
        
        return helper(newA, B, times + 1);
    }
}

このように置いたのですか?
でも提出してA.Equals(B)が先に来たらA.length()==0でも大丈夫なので運行時間も遅いので変えてみました?
結果は30%から100%に変わった.
これは驚くべき真実の物語だ.
運転時:O(n^2)
ソリューション

class Solution {
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && (A + A).contains(B);
    }
}

O(n^2)
^^

KMP ALGORITHM

class Solution {
    private int[] getLPS(String a){
        int i = 1, j = 0;
        int n = a.length();
        int[] lps = new int[n];
        while(i < n){
            if(a.charAt(j) == a.charAt(i)){
                lps[i] = j + 1;
                i++;
                j++;
            }
            else{
                if(j == 0)lps[i++] = 0;
                else j = lps[j-1];
            }
        }
        return lps;
    }
    private boolean contains(String a, String b){
        int[] lps = getLPS(b);
        int i = 0, j = 0;
        int n = a.length(), m = b.length();
        while(i < n && j < m){
            if(a.charAt(i) == b.charAt(j)){
                i++;
                j++;
            }
            else{
                if(j == 0) i++;
                else j = lps[j-1];
            }
        }
        return j == m;
    }
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && contains(A+A, B);
    }
}

Majority Element 2

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        //아 이거 한칸 띄우기 어쩌구 있었는데
        //at max 2 majority element!!
        
        List<Integer> result = new ArrayList<Integer>();
        
        int maj1 = nums[0];
        int count1 = 1;
        while (count1 < nums.length && nums[count1] == maj1) {
            count1++;
        }
        
        if (count1 == nums.length) {
            result.add(maj1);
            return result; 
        }
        
        int maj2 = nums[count1];
        int count2 = 1;
        
        for (int i = count1 + 1; i < nums.length; i++) {
            if (nums[i] == maj1) {
                count1++;
            } else if (nums[i] == maj2) {
                count2++;
            } else if (count2 <= 0) {
                maj2 = nums[i];
                count2 = 1;
            } else if (count1 <= 0) {
                maj1 = nums[i];
                count1 = 1; 
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == maj1) {
                count1++;
            } else if (nums[j] == maj2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(maj1);
        }
        
        if (count2 > nums.length / 3) {
            result.add(maj2); 
        }
        
        return result; 

    }
}

Runtime: 1 ms, faster than 99.82% of Java online submissions for Majority Element II.
Memory Usage: 43.2 MB, less than 21.76% of Java online submissions for Majority Element II.
この解決策がショックだったのを覚えていたので解けました^^
1/3以上歩けるのはせいぜい2つあるので、その点を利用してマイナスしてさらにプラスする方式~
ソリューション

class Solution {
    public List < Integer > majorityElement(int[] nums) {

        // 1st pass
        int count1 = 0;
        int count2 = 0;

        Integer candidate1 = null;
        Integer candidate2 = null;

        for (int n: nums) {
            if (candidate1 != null && candidate1 == n) {
                count1++;
            } else if (candidate2 != null && candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1++;
            } else if (count2 == 0) {
                candidate2 = n;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }

        // 2nd pass
        List result = new ArrayList <> ();

        count1 = 0;
        count2 = 0;

        for (int n: nums) {
            if (candidate1 != null && n == candidate1) count1++;
            if (candidate2 != null && n == candidate2) count2++;
        }

        int n = nums.length;
        if (count1 > n/3) result.add(candidate1);
        if (count2 > n/3) result.add(candidate2);

        return result;
    }
}

JIN LUSEONの方が清潔です
私は候補者を選んでから始めましたが、Luceneは候補者を安定させ、一周~
運転時:O(N)