【LeetCode】極客時間アルゴリズム方法とコードテンプレートのまとめ(更新中)

一、コードテンプレート
1、再帰

// Java
public void recur(int level, int param) {
      

  // terminator 
  if (level > MAX_LEVEL) {
      
    // process result 
    return; 
  }

  // process current logic 
  process(level, param); 

  // drill down 
  recur( level: level + 1, newParam); 

  // restore current status 

2、分治

private static int divide_conquer(Problem problem, ) {
     
  // terminator 
  if (problem == NULL) {
     
    int res = process_last_result();
    return res;     
  }
  
  // process current logic：split the big problems
  subProblems = split_problem(problem)
  
  // drill down：conquer subproblems, merge subresults
  res0 = divide_conquer(subProblems[0])
  res1 = divide_conquer(subProblems[1])
  result = process_result(res0, res1);

  // revert the current level states
  
  return result;
}

3、BFS

public class TreeNode {
     
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
     
        val = x;
    }
}

public List<List<Integer>> levelOrder(TreeNode root) {
     
    List<List<Integer>> allResults = new ArrayList<>();
    if (root == null) {
     
        return allResults;
    }
    Queue<TreeNode> nodes = new LinkedList<>();
    nodes.add(root);
    while (!nodes.isEmpty()) {
     
        int size = nodes.size();
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < size; i++) {
     
            TreeNode node = nodes.poll();
            results.add(node.val);
            if (node.left != null) {
     
                nodes.add(node.left);
            }
            if (node.right != null) {
     
                nodes.add(node.right);
            }
        }
        allResults.add(results);
    }
    return allResults;
}

4、DFS
4.1再帰
DFSテンプレート:

voidDFS ( Vertex V ) 
{
     
	visited[V] = true;  
	for( V       W )
		if( !visited[W] )
	DFS( W );
}

public List<List<Integer>> levelOrder(TreeNode root) {
     
 	
	if(root==null)  return allResults;
	List<List<Integer>> allResults = new ArrayList<>();
	travel(root, 0, allResults);
	return allResults;
}


private void travel(TreeNode root, int level, List<List<Integer>> results){
     
    // process current node here. 
    if(results.size()==level)  results.add(new ArrayList<>());
    results.get(level).add(root.val);
    
    if(root.left!=null)  travel(root.left, level+1, results);
    if(root.right!=null)  travel(root.right, level+1, results);
}

4.2反復(非再帰表記)

void dfs(TreeNode root) {
     

  if(root!=null) return ;
  
  Set<Integer> visited = new HashSet<>();
  stack<TreeNode> stackNode;
  stackNode.push(root);

  while (!stackNode.isEmpty()) {
     
    TreeNode node = stackNode.pop();
    if(visited.contains(node.val))  continue;  // already visited 
    visited.add(node.val);

    for (int i = node.children.length() - 1; i >= 0; --i) {
     
        stackNode.push(node.children[i]);
    }
  }

  return ;
}

5、二叉木
層順遍歴テンプレートは、上のBFSを参照することができる.
二、問題の書き方
三、参考
1、再帰コードテンプレート2、分治コードテンプレート3、BFSコードテンプレート4、DFSコードテンプレート(再帰表記、非再帰表記)