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

目录

1. 二叉树中和为某一值的路径(二)

2. 字符串的排列

3. 最小的K个数

【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞，关注一下吧，后续会一直分享题目与算法思路】

1. 二叉树中和为某一值的路径(二)

描述

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22

则合法路径有[[10,5,7],[10,12]]

解题思路：

1. 思路一：由题意可知，我们需要找出有几条路径使得该路径的节点值和为expectNumber。这是一个典型的DFS回溯的算法。

我们可以先定义一个结果集ArrayList> result 和 一个待选集ArrayList list。

1. 先在待选集中添加一个值（当前root节点）

2. 判断是否满足条件（该路径的节点值和为expectNumber）

（如果满足，则将当前待选集合list 添加到结果集result 中）

3. DFS递归（继续添加左右子树的节点到待选集中）

4. 回退（每判断一条路径list后，将当前路径list中最后一个节点删除，返回上一层，判断其上一层右子树路径是否满足条件）

思路一：代码如下：  

import java.util.ArrayList;

public class FindPath_21 {
    public ArrayList> FindPath(TreeNode root, int expectNumber) {
        // 结果集
        ArrayList> result = new ArrayList>();
        // 待选集
        ArrayList list = new ArrayList();

        FindPathHelper(root,result,list,expectNumber);
        return result;
    }
    private void FindPathHelper(TreeNode root,ArrayList> result,ArrayList 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(list));
        }
        
        // 3.DFS（继续添加左右子树的节点到待选集中）
        FindPathHelper(root.left, result, list, expectNumber);
        FindPathHelper(root.right, result, list, expectNumber);
        
        // 4.回退（每判断一条路径list后，将当前路径list中最后一个节点删除，返回上一层，判断其上一层右子树路径是否满足条件）
        list.remove(list.size()-1);
    }
}

2. 字符串的排列

描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如

1. 输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

2.输入字符串ab

解题思路：

1. 思路一：全排列问题，可以看做如下多叉树形态:

很明显，我们想要得到合适的排列组合，一定是深度优先的

该问题可以把目标串理解成两部分：

第一部分：以哪个字符开头，第二部分：剩下的是子问题 

所以，我们要让每个字符都要做一遍开头(fori遍历)，然后在求解子问题

（每一步的操作请见代码注释）

思路一：代码如下：  

import java.util.ArrayList;
import java.util.Collections;

public class Permutation_22 {
    public ArrayList Permutation(String str) {
        ArrayList 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 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 result) {
        return result.contains(String.valueOf(str));
    }
}

3. 最小的K个数

描述 

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。 

例：

解题思路：

1. 思路一：首先想到最简单的排序，排序数组后，返回前k个值即可。

2. 思路二：见到topk 问题，第一时间想到可以用优先级队列（找前k个最小值，用大根堆）解决问题。

最小堆（小根堆）：树中每个非叶子结点都不大于其左右孩子结点的值，也就是根节点最小的堆

最大堆（大根堆）：树中每个非叶子结点大于其左右孩子结点的值，也就是根节点最大的堆

ps:有关优先级队列与堆的概念详见：《Java 堆 & 优先级队列（下）》

1. 先创建一个容量为k的大根堆queue

2. 遍历数组，使所有元素进行入队操作

2.1 先将前k个元素先入队

2.2 在进行后面元素入队时，要先比较根节点值是否大于当前元素，如果根节点值>当前元素，就将根节点出队，当前元素入队

3. 当所有元素入队结束后，大根堆queue中存储的就是前k个最小的数

思路二：代码如下： 

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

public class GetLeastNumbersTopK_24 {
    public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList result = new ArrayList<>();
        // 判断传入的参数是否合法
        if(input.length == 0 || k <= 0 || k > input.length){
            return result;
        }

        //1. 先创建一个容量为k的大根堆queue
        // k 为容量；Collections.reverseOrder() 指按大根堆排序
        PriorityQueue 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;
    }
}