[数据结构与算法]每周leetcode - leetcode144/94/145/215/剑指Offer 40/牛客NC119/88

leetcode -144 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
方法1： 递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        dfs(list,root);
        return list;
    }

    private void dfs(List<Integer> list,TreeNode root) {
        if(root == null){
            return;
        }
        list.add(root.val);
        dfs(list,root.left);
        dfs(list,root.right);
    }
}

方法2：迭代

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()){
            // 首先把当前节点pop出来并暂存
            TreeNode node = stack.pop();
            if(node!=null){
                // 判断是否是左右子节点，并添加进栈中
                if(node.right!=null) stack.push(node.right);
                if(node.left!=null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else{
                list.add(stack.pop().val);
            }
        }
        return list;
    }
}

leetcode - 94 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

方法1：递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        dfs(list,root);
        return list;
    }

    private void dfs(List<Integer> list, TreeNode root) {
        if(root==null) return;
        dfs(list,root.left);
        list.add(root.val);
        dfs(list,root.right);
    }
}

方法2：迭代

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node!=null){
                if(node.right!=null){
                    stack.push(node.right);
                }
                stack.push(node);
                stack.push(null);
                if(node.left!=null){
                    stack.push(node.left);
                }
            }else{
                list.add(stack.pop().val);
            }
        }
        return list;
    }
}

leetcode - 145 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。
方法1：递归

class Test {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        dfs(list,root);
        return list;
    }

    private void dfs(List<Integer> list, TreeNode root) {
        if(root==null) return;
        dfs(list,root.left);
        dfs(list,root.right);
        list.add(root.val);
    }
}

方法2：迭代

class Test {
	public List<Integer> postorderTraversal(TreeNode root) {
	    List<Integer> list = new ArrayList<>();
	    if(root==null) return list;
	    Stack<TreeNode> stack = new Stack<>();
	    stack.push(root);
	    while (!stack.isEmpty()){
	        TreeNode node = stack.pop();
	        if(node!=null){
	            stack.push(node);
	            stack.push(null);
	            if(node.right!=null) stack.push(node.right);
	            if(node.left!=null) stack.push(node.left);
	        }else{
	            list.add(stack.pop().val);
	        }
	    }
	    return list;
	}
}

剑指 Offer - 40 最小的k个数

/**
 * 输入整数数组 arr ，找出其中最小的 k 个数。
 * 例如，输入4、5、1、6、2、7、3、8这8个数字，
 * 则最小的4个数字是1、2、3、4。
 *
 * 示例 1：
 *
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 *
 * 示例 2：
 *
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 *  
 */

方法1：

/**
 *  我们可以维护一个有K个元素的大顶堆：
 *  大顶堆堆顶的元素比其他元素都大，是第K个最小的数，大顶堆维护的最小的K个数
 *  PriorityQueue默认实现的是小顶堆，小顶堆是升序队列，大顶堆是降序队列
 */
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
    	// 这些条件一个都不能少
        if(arr==null || arr.length==0 || k<=0){
            return new int[]{};
        }
        // 1、创建一个大顶堆,自定义排序规则
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int index = 0;
        // 先把前k个数加入优先队列中
        while (index<k){
            queue.add(arr[index]);
            index++;
        }
        while (index<arr.length){
            // 如果遍历到的元素小于堆顶的元素，将堆顶的元素弹出，然后将该元素加入堆中
            if(arr[index]<queue.peek()){
                queue.poll();
                queue.add(arr[index]);
                index++;
            }else{
                index++;
            }
        }
        int[] result = new int[queue.size()];
        for(int i=0;i<result.length;i++){
            result[i] = queue.poll();
        }
        return result;
    }
}

方法2：

class Test {
    public int[] getLeastNumbers(int[] arr, int k) {
    	// 这些条件一个都不能少
        if(arr==null || arr.length==0 || k<=0){
            return new int[]{};
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int i=0;i<arr.length;i++){
           if(queue.size()<k){
               queue.add(arr[i]);
           }else if(arr[i]<queue.peek()){
               queue.poll();
               queue.add(arr[i]);
           }
        }
        int[] result = new int[queue.size()];
        for(int i=0;i<result.length;i++){
            result[i] = queue.poll();
        }
        return result;
    }
}

补充int compare(Integer o1, Integer o2) 方法的使用：

class Test {
    public static void main(String[] args) {
        Integer[] nums = new Integer[]{6, 8, 3, 0, 2};
        // 0  2  3  6  8
        asc(nums);
        // 8  6  3  2  0
        dsc(nums); 
    }

    private static void asc(Integer[] nums) {
        Arrays.sort(nums, new Comparator<Integer>() {
            // 6, 8, 3, 0, 2
            // 如果返回-1，不交换顺序，
            // 如果返回1和0，交换顺序
            // o1 和 o2 比较，如果o1-o2<0,说明前面的数比后面的数小，返回-1,不交换顺序
            // 6和8比较，6-8<0,不交换顺序（o1-o2）
            // 8和3比较，8-3>0,交换顺序 3 8
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for (Integer i : nums) {
            System.out.print(i + " ");  
        }
    }
    
    private static void dsc(Integer[] nums) {
        Arrays.sort(nums, new Comparator<Integer>() {
            // 6, 8, 3, 0, 2
            // 如果返回-1,不交换顺序
            // 如果返回0和1,交换顺序
            // 6和8比较，8-6>0，交换顺序为 8 6 (o2-o1)
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for (Integer i : nums) {
            System.out.print(i + " ");
        }
    }
}

牛客 - NC119 最小的K个数

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

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input==null || input.length<0 || k<=0){
            return list;
        }
        // 实现一个大顶堆，维护k个最小的元素
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int i=0;i<input.length;i++){
            if(queue.size()<k){
                queue.add(input[i]);
            }else if(queue.peek()>input[i]){
                queue.poll();
                queue.add(input[i]);
            }
        }
        int size = queue.size();
        for(int i=0;i<size;i++){
             list.add(queue.poll());
        }
        return list;
    }
}

牛客 - NC88 寻找第K大

/**
 * 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
 * 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，
 * 请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
 *
 * 输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3
 * 输出：9
 * 说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9
 */

方法1：优先队列

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        if(a==null || a.length<0 || K<=0){
            return 0;
        }
        // 实现一个小顶堆，维护k个最大的数
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0;i<a.length;i++){
            if(queue.size()<K){
                queue.add(a[i]);
            }else if(queue.peek()<a[i]){
                queue.poll();
                queue.add(a[i]);
            }
        }
        return queue.peek();
    }
}

方法2 ：快速排序

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        if(a==null || a.length<0 || K<=0){
            return 0;
        }
        // 快速排序算法：思路就是为每一个基准数找到它在顺序排序中的位置
        int low = 0;
        int high = a.length-1;
        // 定义一个函数，递归的寻找基准数的位置
        quickSort(low,high,a);
        return a[a.length-K];
    }

    private void quickSort(int low, int high, int[] a) {
        // 递归终止的条件，当low和high指向同一个位置时，该位置就是基准数的位置
        if(low>high) {
            return;
        }
        int index = getIndex(low,high,a);
        quickSort(low,index-1,a);
        quickSort(index+1,high,a);
    }

    private int getIndex(int low, int high, int[] a) {
        // 假设基准数为第一个数
        int temp = a[low];
        // 若条件是while (low<=high)将进入一个死循环
        while (low<high){
            while (low<high && a[high]>=temp){
                high--;
            }
            a[low] = a[high];
            while (low<high && a[low]<=temp){
                low++;
            }
            a[high] = a[low];
        } 
        a[low] = temp;
        return low;
    }
}

leetcode - 215 数组中的第K个最大元素

/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 */

方法1 ：优先队列

class Test {
    public int findKthLargest(int[] nums, int k) {
    	// 这些条件一个都不能少
        if(nums==null || nums.length<0 || k<=0){
            return 0;
        }
        // 实现一个小顶堆，维护k个最大的元素
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0;i<nums.length;i++){
            if(queue.size()<k){
                queue.add(nums[i]);
            }else if(queue.peek()<nums[i]){
                queue.poll();
                queue.add(nums[i]);
            }
        }
        return queue.peek();
    }
}

方法2：快速排序

public class Test {
    public int findKthLnumsrgest(int[] nums, int k) {
        if(nums==null || nums.length<0 || k<=0){
            return 0;
        }
        int low = 0;
        int high = nums.length-1;
        quickSort(low,high,nums);
        return nums[nums.length-k];
    }
    private void quickSort(int low, int high, int[] nums) {
        // 递归终止的条件，当low和high指向同一个位置时，该位置就是基准数的位置
        if(low>high) {
            return;
        }
        int index = getIndex(low,high,nums);
        quickSort(low,index-1,nums);
        quickSort(index+1,high,nums);
    }

    private int getIndex(int low, int high, int[] nums) {
        // 假设基准数为第一个数
        int temp = nums[low];
        // 若条件是while (low<=high)将进入一个死循环
        while (low<high){
            while (low<high && nums[high]>=temp){
                high--;
            }
            nums[low] = nums[high];
            while (low<high && nums[low]<=temp){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = temp;
        return low;
    }
}