Mock Interview: Microsoft #4

Majority Element II

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        
        
        for (int i = 0; i < nums.length; i++) {
            m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
            
            if (m.get(nums[i]) > nums.length / 3) {
                result.add(nums[i]);
                m.remove(nums[i]);
            }
        }
        
        return result;
    }
}

Wrong Answer
80/82 test cases passed
最初は地図を書く方法と地図を消す方法で...小さな方法では通じません^^

メモリはO(1)

ではない.

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        int i = 0;
        
        Arrays.sort(nums);
        int cur = nums[0];
        int count = 0; 
        while (i < nums.length) {
            cur = nums[i];
            while (i < nums.length && nums[i] == cur) {
                count++;
                i++;
            }
            
            if (count > nums.length / 3) {
                result.add(cur);
            }
            count = 0;
        }
        
        return result; 
    }
    
}

Runtime: 5 ms, faster than 41.36% of Java online submissions for Majority Element II.
Memory Usage: 46.3 MB, less than 11.05% of Java online submissions for Majority Element II.
O(1)
ここで一行を変えたら.

while (i < nums.length - nums.length / 3)

Runtime: 3 ms, faster than 51.67% of Java online submissions for Majority Element II.
Memory Usage: 46.7 MB, less than 5.11% of Java online submissions for Majority Element II.
少し上へ
+++ソリューション
本当に小さくなりました~^^
Boyer-Moore Voting Algorithm

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;
    }
}

3分の1以上なので、最大2つの候補を利用することになります
top 2 multistと同じ値が表示されると、その値のcountは向上し、他の値は変わらないままになります.両方がそうでない場合は、両方とも1を減算して0になり、次の値で置き換えます.最後に残った2値で本当に多数なのか確認してArraylistに入れればいいです本当に天才じゃないの?

Rotate String

//여러개가 같을 수도 있음...ㅠㅠㅠㅠㅠ
class Solution {
    public boolean rotateString(String A, String B) {
        
        if (A.length() == 0 || B.length() == 0) {
            return A.equals(B); 
        }
        char start = A.charAt(0);
        int diff = 0;
        
        for (int i = 0; i < B.length(); i++) {
            if (B.substring(i).equals(A.substring(0, A.length() - i))) {
                diff = i; 
                break; 
            }
        }
        
        String newB = B.substring(diff) + B.substring(0, diff);
        
        return A.equals(newB);
    }
}

Runtime: 1 ms, faster than 35.17% of Java online submissions for Rotate String.
Memory Usage: 38.8 MB, less than 12.66% of Java online submissions for Rotate String.
後ろに残っているサブストリングは同じ点を見つけて、前も同じかどうか見てみましょう~
+++ソリューション

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

これは少し理解できますが、私の頭の中では出てくるような方法です.^^