Mock Interview: Facebook #4
6475 ワード
お誕生日おめでとう~^^
本当にお久しぶりです.
ほほほ
Memory Usage: 40 MB, less than 29.01% of Java online submissions for Reverse Vowels of a String.
でも不快...
Memory Usage: 42.1 MB, less than 7.49% of Java online submissions for Find Largest Value in Each Tree Row.
DFSの書き込み方法
Memory Usage: 41.8 MB, less than 12.75% of Java online submissions for Find Largest Value in Each Tree Row.
BFSへの書き込み方法
クリスマスツリーを忘れてしまい、
本当にお久しぶりです.
ほほほ
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);
}
最初に思いついた2つのポインタでも不快...
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への書き込み方法
クリスマスツリーを忘れてしまい、
Reference
この問題について(Mock Interview: Facebook #4), 我々は、より多くの情報をここで見つけました https://velog.io/@jwade/Mock-Interview-Facebook-4テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol