例题详解Java dfs与记忆化搜索和分治递归算法的使用

/**

  * 深度优先搜索

  *

  * @param node

  * @param set

  */

public void DFS(Node node, Set<Node> set) {

     if (node == null ) {

         //当没有节点时，退出此次方法

         return ;

     }

     if (!set.contains(node)) {

         //没有搜到过就保存，并且继续向下推进

         set.add(node);

         System.out.print(node.value + " " );

         for (Node node1 : node.nexts) {

             DFS(node1, set);

         }

     }

}

public static void dfs(Node treeNode) {

         if (treeNode == null ) {

             return ;

         }

         System.out.print(treeNode.value + " " );

         // 遍历左节点

         dfs(treeNode.left);

         // 遍历右节点

         dfs(treeNode.right);

     }

public static int f( int n){

     if (n<= 1 ) return 1 ;

     return f(n- 1 )+f(n- 2 );

}

static int [] dp = new int [ 1000 ] ;

public static int f1( int n){

     if (n<= 1 ) return dp[n] = 1 ;

     if (dp[n]!= 0 ) return dp[n];

     return dp[n]=f1(n- 1 )+f1(n- 2 );

}

import java.util.*;

import java.io.*;

public class Main{

     static class Edge{

         int to;

         int weight;

         //保存子节点，与线权（传播时间）。

         Edge( int to, int weight){

             this .to = to;

             this .weight = weight;

         }

     }

     static ArrayList<Edge>[] g;

     static int maxtime;

     static int weight[];

     public static void main(String[] args) throws IOException {

         BufferedReader br = new BufferedReader( new InputStreamReader(System.in));

         int n = Integer.parseInt(br.readLine()); //n为总人数

         weight = new int [n+ 1 ];

         g = new ArrayList[n+ 1 ];

         // 每个桶中保存一个ArrayList（可达）

         //这里的i代表了第几个数（从1开始）

         for ( int i = 1 ;i<=n;i++){

             g[i] = new ArrayList();

         }

         //保存所有点权（理解时间）纪录了从2到n的点权，与数字的位子相对应。

         String[] s = br.readLine().split( " " );

         for ( int i = 0 ;i<n- 1 ;i++){

             weight[i+ 2 ] = Integer.parseInt(s[i]);

         }

         for ( int i = 0 ;i<n- 1 ;i++){

             String[] s1 = br.readLine().split( " " );

             int x = Integer.parseInt(s1[ 0 ]);

             int y = Integer.parseInt(s1[ 1 ]);

             int z = Integer.parseInt(s1[ 2 ]);

             g[x].add( new Edge(y,z));

         }

         dfs( 1 , 0 );

         System.out.println(maxtime);

     }

     static void dfs( int i , int time){

         if (maxtime<time+weight[i])maxtime = time+weight[i];

         for ( int k = 0 ;k<g[i].size();k++){

             dfs(g[i].get(k).to,time+g[i].get(k).weight);

         }

     }

}

import java.util.*;

import java.io.*;

public class Main {

     static ArrayList<Integer>[] g;

     static String[] strings;

     static int [] visited;

     public static void main(String[] args) throws Exception {

         BufferedReader br = new BufferedReader( new InputStreamReader(System.in));

         String[] firstLine = br.readLine().split( " " );

         int n = Integer.parseInt(firstLine[ 0 ]);

         int m = Integer.parseInt(firstLine[ 1 ]);

         g = new ArrayList[n+ 1 ];

         visited = new int [n+ 1 ];

         for ( int i= 1 ;i<n+ 1 ;i++) {

             g[i] = new ArrayList<Integer>();

         }

         //一个字符一个字符的读取

         strings = br.readLine().split( "" );

         for ( int i= 0 ;i<m;i++) {

             //描绘双向图

             String[] temp = br.readLine().split( " " );

             int x = Integer.parseInt(temp[ 0 ]);

             int y = Integer.parseInt(temp[ 1 ]);

             g[x].add(y);

             g[y].add(x);

         }

         int cnt = 0 ;

         StringBuilder sb = new StringBuilder();

         for ( int i= 1 ;i<n+ 1 ;i++) {

             if (visited[i] == 0 && strings[i- 1 ].equals( "R" )) {

                 cnt++;

                 sb.append(i + " " );

                 //从糖葫芦小的开始纪录，然后延深。

                 dfs(i);

             }

         }

         System.out.println(cnt);

         System.out.println(sb);

     }

     static void dfs( int x) {

         if (visited[x] == 0 && strings[x- 1 ].equals( "R" )) {

             //点亮它

             visited[x] = 1 ;

             for ( int i= 0 ;i<g[x].size();i++) {

                 dfs(g[x].get(i));

             }

         }

     }

}

import java.util.*;

import java.io.*;

public class Main{

     static boolean [] check = new boolean [ 2000 ];

     static int [] ai;

     static int n;

     static int min = Integer.MAX_VALUE;

     //判断是否为素数

     static boolean isPrime( int x){

         if (x< 2 ) return false ;

         //这是根据开根号的演化版本，提高了效率。

         for ( int i= 2 ;i*i<=x;i++){

             if (x%i== 0 ) return false ;

         }

         return true ;

     }

     static void dfs( int index, int sum){

         if (index==n){

             min=Math.min(min,sum);

             return ;

         }

         //查找这个数没有被占用的素因子。

         for ( int i= 2 ;i<=ai[index];i++){

             if (ai[index]%i== 0 &&check[i]== false &&isPrime(i)){

                 check[i]= true ;

                 dfs(index+ 1 ,sum+i);

                 //回溯的方法。

                 check[i]= false ;

             }

         }

     }

     public static void main(String[] args) throws IOException{

         BufferedReader br = new BufferedReader( new InputStreamReader(System.in));

         n = Integer.parseInt(br.readLine());

         String[] a = br.readLine().split( " " );

         //负责保存所有输入的数

         ai = new int [n];

         for ( int i= 0 ;i<n;i++){

             ai[i]=Integer.parseInt(a[i]);

         }

         dfs( 0 , 0 );

         System.out.println(min==Integer.MAX_VALUE ? - 1 :min);

         br.close();

     }

}

import java.util.*;

import java.io.*;

public class Main{

     static HashMap<Long,Long> map = new HashMap<>();

     public static void main (String[] args) throws IOException{

         BufferedReader br = new BufferedReader( new InputStreamReader(System.in));

         int num = Integer.parseInt(br.readLine());

         for ( int i = 0 ; i<num; i++){

             System.out.println(recurse(Long.parseLong(br.readLine())));

         }

     }

     static long recurse( long num){

         if (num <= 1 ) return 0 ;

         //用于保存

         if (map.containsKey(num)) return map.get(num);

         long pay = recurse(num/ 2 ) + recurse(num-num/ 2 ) +num% 2 ;

         map.put(num,pay);

         return pay;

     }

}