【迎战蓝桥】 算法·每日一题（今日详解）-- day7

import java.util.ArrayList;
public class FindPath_21 {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        // 结果集
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        // 待选集
        ArrayList<Integer> list = new ArrayList<Integer>();
        FindPathHelper(root,result,list,expectNumber);
        return result;
    }
    private void FindPathHelper(TreeNode root,ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,int expectNumber) {
        // 当前节点为空说明当前路径已经走到叶子结点，已走完，return
        if (root == null) {
            return;
        }
        // 每次遇到新节点，将expectNumber减去该root.val，当expectNumber减到0时，该路径就是所求路径
        expectNumber -= root.val;
        // 1.先在待选集中添加一个值（当前root节点）
        list.add(root.val);
        // 2.判断是否满足条件（该路径的节点值和为expectNumber）
        if (root.left == null && root.right == null && expectNumber == 0) {
            // 如果满足，则将当前待选集合list 添加到结果集result 中
            // 进行深拷贝
            result.add(new ArrayList<Integer>(list));
        }
        // 3.DFS（继续添加左右子树的节点到待选集中）
        FindPathHelper(root.left, result, list, expectNumber);
        FindPathHelper(root.right, result, list, expectNumber);
        // 4.回退（每判断一条路径list后，将当前路径list中最后一个节点删除，返回上一层，判断其上一层右子树路径是否满足条件）
        list.remove(list.size()-1);
    }
}

import java.util.ArrayList;
import java.util.Collections;
public class Permutation_22 {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        // 如果字符串不为空进行后续的操作
        if(str != null || str.length() != 0){
            PermutationHelper(str.toCharArray(),0,result);
            // 按字典序排列
            Collections.sort(result);
        }
        return result;
    }
    private void PermutationHelper(char[] str, int start,ArrayList<String> result) {
        // 如果start为末尾索引，就是走到最后一个字符，说明已经得到了一个排列后的字符串，判断是否符合要求，然后return
        if(start == str.length - 1){
            // 判断result中是否已经存在当前的字符串
            if(!isExist(str,result)){
                // 如果result中不存在存在当前字符串，进行添加操作
                result.add(new String(str));
            }
            return;
        }
        // 1.让每个字符都要做一遍开头(fori遍历)
        for (int i = start; i < str.length; i++) {
            // 第一层 分别以 a,b,c 为根节点
            swap(str,i,start);
            // 2.然后在求解子问题(子问题中也是让start+1开始的字符都要做一遍开头(fori遍历))
            PermutationHelper(str,start+1,result);
            // 在进行后续遍历之前，要把刚刚已经改变的str还原
            swap(str,i,start);
        }
    }
    // 交换三连
    private void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
    // 判断result中是否已经存在当前的字符串
    private boolean isExist(char[] str, ArrayList<String> result) {
        return result.contains(String.valueOf(str));
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
public class GetLeastNumbersTopK_24 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        // 判断传入的参数是否合法
        if(input.length == 0 || k <= 0 || k > input.length){
            return result;
        }
        //1. 先创建一个容量为k的大根堆queue
        // k 为容量；Collections.reverseOrder() 指按大根堆排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());
        // 2. 遍历数组，使所有元素进行入队操作
        for (int i = 0; i < input.length; i++) {
            if(i < k){
                // 2.1 先将前k个元素先入队
                queue.add(input[i]);
            }else {
                // 2.2 入队k 后面的元素
                if(queue.peek() > input[i]){
                    // 如果根节点值>当前元素，就将根节点出队，当前元素入队
                    queue.poll();
                    queue.add(input[i]);
                }
            }
        }
        // 3. 当所有元素入队结束后，大根堆queue中存储的就是前k个最小的数
        // 传入到result中
        for (int i = 0; i < k; i++) {
            result.add(queue.poll());
        }
        return result;
    }
}