Mock Interview: Amazon #8

Longest Palindrome

class Solution {
    public String longestPalindrome(String s) {
        
        if (s.length() <= 1) {
            return s;
        }
        
        String rev = new StringBuilder(s).reverse().toString();
        
        String res = "";
        String temp = "";
        int count = 0;
        int mcount = 0;
        
        for (int i = 1; i < s.length(); i++) {
            if (rev.charAt(i) == s.charAt(i)) {
                count++;
                temp += rev.charAt(i);
            } else {
                if (count > mcount) {
                    res = temp;
                    mcount = count;
                }
                count = 0;
                temp = "";
            }
        }
        
        if (res.length() == 0) {
            return "" + s.charAt(0);
        } else {
            return res;
        }
    }
}

10 / 176 test cases passed.

저번에 풀었을 때 reverse 를 사용하는 방법이 나왔던 걸 기억해 내서 reverse로 풀려고 했는데
이때는 몰랐죠...^^ 내가 reverse로 만들고 똑같은걸 비교 못 할 줄은....^^.....

public String longestPalindrome(String s) {
        String rs = new StringBuilder(s).reverse().toString();
        int maxCommonLen = 0;
        String palindrome = "";
        int[][] memo = new int[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
        	for(int j = 0; j < rs.length(); j++) {
        		if(s.charAt(i) == rs.charAt(j)) {
        			memo[i][j] = i > 0 && j > 0 ? 1+memo[i-1][j-1] : 1;
        		}
        		if(memo[i][j] > maxCommonLen) {
        			int si = i-memo[i][j]+1;
        			int sj = j-memo[i][j]+1;
        			if(si+j+1 == s.length() && sj+i+1 == s.length()) {
        				maxCommonLen = memo[i][j];
        				palindrome = s.substring(si, i+1);
        			}
        		}
        	}
        }
        return palindrome;
    }

reverse로 푼 루션이 찾아보니깐 저는 1중 포문이면 될 줄 알았는데 이중포문이 필수였네요^^

private int lo, maxLen;

public String longestPalindrome(String s) {
	int len = s.length();
	if (len < 2)
		return s;
	
    for (int i = 0; i < len-1; i++) {
     	extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
     	extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
	//같은 걸 죄다 뒤져주기
	while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
		j--;
		k++;
	}
    //maxlen을 업데이트 할지 말지 고민하기
	if (maxLen < k - j - 1) {
		lo = j + 1;
		maxLen = k - j - 1;
	}
}

죽어도 생각 안나던 재귀 solution~
냅 다 외 워

K Closest Points to Origin

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<Integer> mh = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
        Map<Integer, int[]> m = new HashMap<Integer, int[]>();
        
        int[][] result = new int[k][2];
        
        for (int i = 0; i < points.length; i++) {
            int length = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            m.put(length, points[i]);
            mh.add(length);
        }
        
        for (int j = 0; j < k; j++) {
            int distance = mh.poll();
            result[j] = m.get(distance);
        }
        
        return result; 
    }
}

82 / 84 test cases passed.

처음에는 쉬맵이 + minheap이를 이용~
근데 쉬맵이가 중복 된 것들을 못잡아줌...

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> mh = new PriorityQueue<int[]>((n1, n2) -> 
            n1[0] * n1[0] + n1[1] * n1[1] - n2[0] * n2[0] - n2[1] * n2[1]);
        
        //Map<Integer, int[]> m = new HashMap<Integer, int[]>();
        
        int[][] result = new int[k][2];
        
        for (int i = 0; i < points.length; i++) {
            mh.add(points[i]);
            //if (mh.size() > k) {
        
            //}
        }
        
        for (int j = 0; j < k; j++) {
            result[j] = mh.poll();
        }
        
        return result; 
    }
}

Runtime: 19 ms, faster than 73.27% of Java online submissions for K Closest Points to Origin.
Memory Usage: 47.8 MB, less than 39.95% of Java online submissions for K Closest Points to Origin.

제 사랑 쉬맵이를 버리고 minheap이와만 함께했읍니다..
sort는 어제 배운거 반신반의 하면서 써먹었는데 됐다는 감동 실화 story^^

중간에 코멘트는 k 이상의 사이즈가 필요가 없어서 좀 빼려고 했는데.. minheap이어서 poll하면 작은 것들이 사라저 버리고 뒤에것을 뺄 방도가 없어서 걍 내비뒀읍니다
maxheap을 썼다면 냅다 버려도 됐을듯