Mock Interview: Facebook #4

velog 하이루~~^^

진심 오랜만

ㅎ

345. Reverse Vowels of a String

class Solution {
    public String reverseVowels(String s) {
        int begin = 0;
        int end = s.length();
        
        Set<Character> c = new HashSet<Character>();
        
        c.add('a');
        c.add('e');
        c.add('i');
        c.add('o');
        c.add('u');
        c.add('A');
        c.add('E');
        c.add('I');
        c.add('O');
        c.add('U');
        
        StringBuilder sb = new StringBuilder();
        
        Deque<Character> stack = new ArrayDeque<Character>();
        
        //StringBuilder vowels = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            if (c.contains(s.charAt(i))) {
                //vowels.append(s.charAt(i));
                stack.push(s.charAt(i));
            }
        }
        
        //int num = vowels.length();
        
        for (int j = 0; j < s.length(); j++) {
            if (c.contains(s.charAt(j))) {
                sb.append(stack.remove());
                //num--; 
            } else {
                sb.append(s.charAt(j));
            }
        }
        
        return sb.toString();
        
//         while (begin <= end) {
//             if (c.contains(s.charAt(begin))) {
//                 while (c.contains(s.charAt(end))) {
//                     end--;
//                 }
                
//                 char change = s.charAt(end);
                
                
//             }
            
//             sb.
//         }
    }
}

Runtime: 8 ms, faster than 28.39% of Java online submissions for Reverse Vowels of a String.
Memory Usage: 40 MB, less than 29.01% of Java online submissions for Reverse Vowels of a String.

public String reverseVowels(String s) {
    if(s == null || s.length()==0) return s;
    String vowels = "aeiouAEIOU";
    char[] chars = s.toCharArray();
    int start = 0;
    int end = s.length()-1;
    while(start<end){
        
        while(start<end && !vowels.contains(chars[start]+"")){
            start++;
        }
        
        while(start<end && !vowels.contains(chars[end]+"")){
            end--;
        }
        
        char temp = chars[start];
        chars[start] = chars[end];
        chars[end] = temp;
        
        start++;
        end--;
    }
    return new String(chars);
}

처음에 생각했던 two pointer
근데 빠르진 않다..

515. Find Largest Value in Each Tree Row

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        helper(root, res, 0);
        return res;
    }
    private void helper(TreeNode root, List<Integer> res, int d){
        if(root == null){
            return;
        }
       //expand list size
        if(d == res.size()){
            res.add(root.val);
        }
        else{
        //or set value
            res.set(d, Math.max(res.get(d), root.val));
        }
        helper(root.left, res, d+1);
        helper(root.right, res, d+1);
    }
}

Runtime: 2 ms, faster than 37.11% of Java online submissions for Find Largest Value in Each Tree Row.
Memory Usage: 42.1 MB, less than 7.49% of Java online submissions for Find Largest Value in Each Tree Row.

DFS를 쓰는 방식

public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        List<Integer> values = new ArrayList<Integer>();
        
        if(root != null) q.offer(root);
        
        while(!q.isEmpty()) {
            int max = Integer.MIN_VALUE, n = q.size();
            for(int i = 0; i < n; i++) {
                TreeNode node = q.poll();
                max = Math.max(max, node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            values.add(max);
        }
        
        return values;
    }

Runtime: 4 ms, faster than 9.30% of Java online submissions for Find Largest Value in Each Tree Row.
Memory Usage: 41.8 MB, less than 12.75% of Java online submissions for Find Largest Value in Each Tree Row.

BFS 를 쓰는 방식

트리 다 까먹었어요,,