蓝桥杯复习重点-算法套路模板

一时失言乱红尘 2022-12-15 12:51 139阅读 0赞

### 迭代 ###

for while

### 递归 ###

void function(int level){ 
        // 终止条件
        if(level > MAX_LEVEL)
            return;
        // 处理过程
        process();
        // 进入下一层
        this.function(level+1);
        //清除当前状态
        return;
    }

### 分治 ###

void function(Problem p){ 
        // 终止条件
        if(level > MAX_LEVEL)
            return;
        // 处理过程
        process();
        Problem[] subproblems = split_problem(p);
        // 进入下一层
        result1 = function(subproblems[0]);
        result2 = function(subproblems[1]);
        result3 = function(subproblems[2]);
        // 返回值
        return get_result(result1,result2,result3);
    }

### 回溯 ###

基于深度优先搜索实现

### 动态规划 ###

### 贪心算法 ###

### 深度优先搜索 ###

void function(Node node){ 
        if(node = null)
        return null;
        // 如果不是二叉树，采用遍历子节点的方式
        function(node.left);
        function(node.right);
        return;
    }

### 广度优先搜索 ###

public List<List<Integer>> levelOrderBottom(TreeNode root) { 
        List<List<Integer>> list = new LinkedList();
    
        if(root==null){ 
            // 不要返回null，因为如果空数组格式为 []
            return list;
        }
    
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
    
        while(!queue.isEmpty()){ 
            List levelList = new ArrayList();
            int size = queue.size();
            
            for(int i=0;i<size;i++){ 
                TreeNode node = queue.poll();
                TreeNode left = node.left;
                TreeNode right = node.right;
                if(left!=null){ 
                    queue.offer(left);
                }
                if(right!=null){ 
                    queue.offer(right);
                }
                levelList.add(node.val);
            }
    
            list.add(0,levelList);
        }
    
        return list;
    
    }

### 排列基于数组 ###

public class T_排列 { 
    	static int[] array = { 1,2,3};
    	public static void f(int index) { 
    		// 结束条件，达到最终长度
    		if(index == array.length-1) { 
    			for (int i = 0; i < array.length; i++) { 
    				System.out.print(array[i]);
    			}
    			System.out.println();
    		}
    		else { 
    			for (int i = index; i < array.length; i++) { 
    				{ int temp = array[i];array[i] = array[index]; array[index] = temp;}
    				f(index+1);
    				{ int temp = array[i];array[i] = array[index]; array[index] = temp;}
    			}
    		}
    	}
    	public static void main(String[] args) { 
    		f(0);
    	}
    }

### 排列基于栈 ###

public class Main { 
         
        public static Stack<Integer> stack = new Stack<Integer>();
        public static void main(String[] args) { 
            int shu[] = { 1,2,3,4};
            f(shu,4,0);
        }
        /** * * @param shu 待选择的数组 * @param targ 要选择多少个次 * @param cur 当前选择的是第几次 */
        
        private static void f(int[] shu, int targ, int cur) { 
            // TODO Auto-generated method stub
            if(cur == targ) { 
                System.out.println(stack);
                return;
            }
             
            for(int i=0;i<shu.length;i++) { 
                if(!stack.contains(shu[i])) { 
                    stack.add(shu[i]);
                    f(shu, targ, cur+1);
                    stack.pop();
                }
                 
            }
        }

### 组合基于数组 ###

public class T_组合 { 
    	static int[] array = { 1,2,3,4,5};
    	public static void dfs(int[] out,int level,int index) { 
    		// 代表out满了
           if(level==out.length) { 
        	   for (int i = 0; i < out.length; i++) { 
        		   System.out.print(out[i]);
        	   }
        	   System.out.println();
           }
           else { 
        	   // 传入level代表现在传入第几层，index代表现在使用该层的值，以后每一层只能使用这一层往后的值
        	   for (int i = index; i < array.length; i++) { 
        		   out[level] = array[i];
        		   dfs(out,level+1,i+1);
        	   }
           }
        }
    
        public static void main(String[] args) { 
        	//n代表取出几个值
        	int n = 3;
            int[] out = new int[n];
            
            dfs(out,0,0);
            
        }
    }

### 组合基于栈 ###

import java.util.Stack;
     
    public class Main { 
         
        public static Stack<Integer> stack = new Stack<Integer>();
        public static void main(String[] args) { 
            int shu[] = { 1,2,3,4};
             
            f(shu,3,0,0); // 从这个数组4个数中选择三个
        }
         
        /** * * @param shu 元素 * @param targ 要选多少个元素 * @param has 当前有多少个元素 * @param cur 当前选到的下标 * * 1 2 3 //开始下标到2 * 1 2 4 //然后从3开始 */
         
        private static void f(int[] shu, int targ, int has, int cur) { 
            if(has == targ) { 
                System.out.println(stack);
                return;
            }
             
            for(int i=cur;i<shu.length;i++) { 
                if(!stack.contains(shu[i])) { 
                    stack.add(shu[i]);
                    f(shu, targ, has+1, i);
                    stack.pop();
                }
            }
             
        }
    }