牛客网算法——名企高频面试题143题（8）

题目描述

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：

每一行的数字都从左到右排序

每一行的第一个数字都比上一行最后一个数字大

例如：

对于下面的矩阵：

package 名企高频面试题143;

import java.util.Arrays;

/**
 * @Classname 矩阵查找
 * @Description TODO
 * @Date 2020/12/16 10:57
 * @Created by xjl
 */
public class 矩阵查找 {
    /**
     * @description TODO 主要是的使用的二分查找的算法
     * @param: matrix
     * @param: target
     * @date: 2020/12/16 11:02
     * @return: boolean
     * @author: xjl
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
        for (int[] arr : matrix) {
            //采用的是的数组的二分查找
            int index = Arrays.binarySearch(arr, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }
}

题目描述

给出一组候选数 C 和一个目标数 T，找出候选数中起来和等于 T 的所有组合。 C 中的每个数字在一个组合中只能使用一次。

注意：

• 题目中所有的数字（包括目标数 T\ T T ）都是正整数
• 组合中的数字 (a1,a2,…,aka_1, a_2, … , a_ka1​,a2​,…,ak​) 要按非递增排序 (a1≤a2≤…≤aka_1 \leq a_2 \leq … \leq a_ka1​≤a2​≤…≤ak​).
• 结果中不能包含重复的组合
• 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

package 名企高频面试题143;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Classname 目标值的和
 * @Description TODO
 * @Date 2020/12/16 10:55
 * @Created by xjl
 */
public class 目标值的和 {

    @Test
    public void test() {
        ArrayList ans = combinationSum3(new int[]{100, 10, 20, 70, 60, 10, 50}, 80);
        for (ArrayList lists : ans) {
            for (int i : lists) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    /**
     * @description TODO
     * @param: num
     * @param: target
     * @date: 2020/12/16 10:55
     * @return: java.util.ArrayList>
     * @author: xjl
     */
    ArrayList ans = new ArrayList();

    public ArrayList combinationSum3(int[] num, int target) {
        ArrayList list = new ArrayList();
        boolean[] vis = new boolean[num.length];
        Arrays.sort(num);
        dfs(num, 0, target, list, vis);
        return ans;
    }

    private void dfs(int[] num, int index, int target, ArrayList list, boolean[] vis) {
        //保证的是剪枝的情况
        if (target < 0) {
            return;
        }
        //终止条件
        if (target == 0 && !ans.contains(list)) {
            ans.add(new ArrayList(list));
            return;
        }
        for (int i = index; i < num.length; i++) {
            if (vis[i] == false) {
                //这个状态
                list.add(num[i]);
                vis[i] = true;
                //下一个转态
                dfs(num, i + 1, target - num[i], list, vis);
                list.remove(list.size() - 1);
                vis[i] = false;
            }
        }
    }
}

 题目描述

给定一个二叉树和一个值 sum，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径，  

package 名企高频面试题143;

import java.util.ArrayList;

/**
 * @Classname 二叉树的路径和III
 * @Description TODO
 * @Date 2020/12/18 9:46
 * @Created by xjl
 */
public class 二叉树的路径和III {
    /**
     * @description TODO 二叉树的定义
     * @param: null
     * @date: 2020/12/18 9:46
     * @return:
     * @author: xjl
     */
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    ArrayList res = new ArrayList(); //用于存储结果
    ArrayList temp = new ArrayList(); //用于存储路径

    public ArrayList pathSum(TreeNode root, int sum) {
        dfs(root, sum, 0);
        return res;
    }

    public void dfs(TreeNode root, int sum, int cnt) {
        // 如果节点为空结束当前递归
        if (root == null) return;
        //将当前节点加入tmp数组
        temp.add(root.val);
        //把当前节点加入到路径和中
        cnt += root.val;
        //当递归到没有子树的时候就需要判断
        if (root.left == null && root.right == null) {
            //如果当前节点的路径和等于sum，那么就在res中插入tmp
            if (cnt == sum) { 
                res.add(temp);
            }
        } else {
            dfs(root.left, sum, cnt); //递归左子树
            dfs(root.right, sum, cnt); //递归右子树
        }
        temp.remove(temp.size() - 1);
    }
}