279. 완전 제곱수

//    
/*
      f(n)        。f(n)      ：
f(n) = 1 + min{
  f(n-1^2), f(n-2^2), f(n-3^2), f(n-4^2), ... , f(n-k^2) //(k   k^2<=n    k)
}
*/
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; //         0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; //          +1
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); //       
            }
        }
        return dp[n];
    }
}

class Solution {
    public int numSquares(int n) {
        int [] res = new int[n+1];
        for (int i = 1; i <= n; i++){
            int min = Integer.MAX_VALUE;
            for (int j = 1; j*j <= i; j++){
                min = Math.min(min, res[i-j*j]);
            }
            res[i] = min + 1;
        }
        return res[n];
    }
}

//    ：                        。                       
class Solution {
    public int numSquares(int n) {
        if(n <= 0){return 0;}
        if(check1(n)){
            return 1;
        }else if(check2(n)){
            return 2;
        }else if(check3(n)){
            return 3;
        }else{
            return 4;
        }
    }
    public boolean check1(int n){
        int tem = (int)Math.sqrt(n);
        return tem*tem == n;
    }
    public boolean check2(int n){
        for(int i = 1 ; i * i < n ; i++){
            if(check1(n-i*i))
                return true;
        }
        return false;
    }
    public boolean check3(int n){
        for(int i = 1 ; i * i < n ; i++){
            if(check2(n-i*i)){
                return true;
            }
        }
        return false;
    }
}

103. 두 갈래 나무의 톱니 모양 차원 두루

//BFS        
class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }

    List<List<Integer>> results = new ArrayList<List<Integer>>();

    LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
    // addLast(E e)：           ；
    node_queue.addLast(root);
    node_queue.addLast(null);

    LinkedList<Integer> level_list = new LinkedList<Integer>();
    boolean is_order_left = true;

    while (node_queue.size() > 0) {
      TreeNode curr_node = node_queue.pollFirst();
      if (curr_node != null) {
        if (is_order_left)
          level_list.addLast(curr_node.val);
        else
          level_list.addFirst(curr_node.val);

        if (curr_node.left != null)
          node_queue.addLast(curr_node.left);
        if (curr_node.right != null)
          node_queue.addLast(curr_node.right);

      } else {
        results.add(level_list);
        level_list = new LinkedList<Integer>();
        if (node_queue.size() > 0)
          node_queue.addLast(null);
        is_order_left = !is_order_left;
      }
    }
    return results;
  }
}

//DFS （      ）
class Solution {
  protected void DFS(TreeNode node, int level, List<List<Integer>> results) {
    if (level >= results.size()) {
      LinkedList<Integer> newLevel = new LinkedList<Integer>();
      newLevel.add(node.val);
      results.add(newLevel);
    } else {
      if (level % 2 == 0)
        results.get(level).add(node.val);
      else
        results.get(level).add(0, node.val);
    }

    if (node.left != null) DFS(node.left, level + 1, results);
    if (node.right != null) DFS(node.right, level + 1, results);
  }

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    DFS(root, 0, results);
    return results;
  }
}

계수

class Solution {
    public int countPrimes(int n) {
        boolean[] b = new boolean[n];
		int count = 0;
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (b[i])
				continue;
			for (int j = i + i; j < n; j += i)
				b[j] = true;
		}
		for (boolean c : b)
			count += !c ? 1 : 0;
		return n > 2 ? count - 2 : 0;
    }
}