Mock Interview: Amazon

1134. Armstrong Number

class Solution {
    public boolean isArmstrong(int n) {
        int power = 0;
        int powern = n;
        
        while (powern > 0) {
            power++;
            powern = powern / 10; 
        }
        
        int total = 0;
        int multn = n;
        while (multn > 0) {
            int digit = multn % 10;
            int add = 1; 
            for (int i = 0; i < power; i++) {
                add = add * digit;
            }
            multn = multn / 10;
            total += add;
        }
        
        return (n == total);
        
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Armstrong Number.
Memory Usage: 35.8 MB, less than 54.86% of Java online submissions for Armstrong Number.

시키는대로 했읍니다..

1008. Construct Binary Search Tree from Preorder Traversal

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        
        q.add(new TreeNode(preorder[0]));
        
        for (int i = 1; i < preorder.length; i++) {
            int value = preorder[i];
            while (! q.isEmpty()) {
                TreeNode root = q.poll();
                if (value < root.val) {
                    root.left = new TreeNode(value);
                    break;
                } else {
                    root.left = null;
                }
                
                if (value > )
            }
        }
    }
}

queue를 사용해서 계속 더해주려고 했는데 이게 되는지도 모르겠어요 -> 레벨이 제대로 안 잡힘

아놔 이거 쓰다가 급 생각났는데 레벨 잡으려면 그냥 쭉 보면서 숫자가 작아질때 잡는걸로 눈치게임 하면 되는거 아닌지;

루션이

public TreeNode bstFromPreorder(int[] A) {
        return bstFromPreorder(A, Integer.MAX_VALUE, new int[]{0});
    }

    public TreeNode bstFromPreorder(int[] A, int bound, int[] i) {
        if (i[0] == A.length || A[i[0]] > bound) return null;
        TreeNode root = new TreeNode(A[i[0]++]);
        root.left = bstFromPreorder(A, root.val, i);
        root.right = bstFromPreorder(A, bound, i);
        return root;
    }

Runtime: 0 ms, faster than 100.00% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.
Memory Usage: 36.9 MB, less than 74.41% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.

오 계속 보면서 작을때 잡아두는게 아니라 그냥 그 root값을 bound로 잡으면 된다!! 대박대박

class Solution {
  public TreeNode bstFromPreorder(int[] preorder) {
    int n = preorder.length;
    if (n == 0) return null;

    TreeNode root = new TreeNode(preorder[0]);
    Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
    deque.push(root);

    for (int i = 1; i < n; i++) {
      // take the last element of the deque as a parent
      // and create a child from the next preorder element
      TreeNode node = deque.peek();
      TreeNode child = new TreeNode(preorder[i]);
      // adjust the parent 
      while (!deque.isEmpty() && deque.peek().val < child.val)
        node = deque.pop();

      // follow BST logic to create a parent-child link
      if (node.val < child.val) node.right = child;
      else node.left = child;
      // add the child into deque
      deque.push(child);
    }
    return root;
  }
}

Runtime: 1 ms, faster than 27.89% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.
Memory Usage: 37.2 MB, less than 38.29% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.

이게 약간 제가 생각한 루션이랑 비슷하네요..
deque를 만들어서 다 넣어준 다음에 left에갈지 right에 갈지 비교해서 넣어주기~