猿辅导算法题面经一

• • 一、二叉树中和为某一值的路径
  • 二、数组中的第K个最大元素

一、二叉树中和为某一值的路径

算法：先序遍历+回溯

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int sum) {findPath(root,sum);return result;}public void findPath(TreeNode root,int target){if(root==null){return;}path.add(root.val);target=target-root.val;//递归结束条件if(target==0&&root.left==null&&root.right==null){result.add(new ArrayList<>(path));}findPath(root.left,target);findPath(root.right,target);path.remove(path.size()-1);}
}

二、数组中的第K个最大元素

算法：快排

import java.util.Random;
class Solution { //选择数组中的第K个最大元素，也就是排序后的length-k个数//在未排序的数组中找到第 k 个最大的元素。请注意，你需要找// 的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。//示例 1://输入: [3,2,1,5,6,4] 和 k = 2//输出: 5public static void main(String[] args) {int[] nums={3,2,1,5,6,4};int result=findKthLargest(nums,2);System.out.println(result);}public static int findKthLargest(int[] nums, int k) {k= nums.length - k;int i=0,j= nums.length - 1;//从左至右开始查找while (i < j){//第一次查找的值int result = quickSelect(nums,i,j);//第一次查找的值result==kif (result == k) {break;//第一次查找的值result>k,则查找的值应该在[i,result-1]}else if (result > k) {j=result-1;//第二次查找的值result}else {i=result + 1;}}return nums[k];}public static int quickSelect(int[] nums,int left,int right){if (left>right) {return 0;}//int base=nums[left];//在下标 low 和 high 之间随机选择，然后和下标 high 元素进行交换int random_index=left + new Random().nextInt(right - left);//将nums[random_index]与nums[left]交换swap(nums,left,random_index);int base=nums[left];int i=left;int j=right;while (i != j){while (nums[j]>=base && j>i) {j--;}while (nums[i] <= base && i<j) {i++;}swap(nums,i,j);}nums[left]=nums[i];nums[i]=base;return i;}public static void swap(int[] nums, int i, int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！