拼接最大数(栈、贪心)、发奖金问题、二叉搜索树迭代器(栈、树)

标签：BSTIterator hasNext 最大数迭代 int bSTIterator next 二叉 cur

拼接最大数(栈、贪心)

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。 **说明: **请尽可能地优化你算法的时间和空间复杂度。 示例 1: 输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6, 5, 3] 示例 2: 输入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出: [6, 7, 6, 0, 4] 示例 3: 输入: nums1 = [3, 9] nums2 = [8, 9] k = 3 输出: [9, 8, 9]

解答：

class Solution {
    private int[] maxInNums(int[] nums, int k) {
        int[] max = new int[k];
        int len = nums.length;
        for (int i = 0, j = 0; i < len; ++i) {
            while (j > 0 && k - j < len - i && max[j - 1] < nums[i])
                --j;
            if (j < k)
                max[j++] = nums[i];
        }
        return max;
    }
    private boolean greater(int[] nums1Max, int i, int[] nums2Max, int j) {
        int lenNums1Max = nums1Max.length;
        int lenNums2Max = nums2Max.length;
        while (i < lenNums1Max && j < lenNums2Max && nums1Max[i] == nums2Max[j]) {
            ++i;
            ++j;
        }
        return j == lenNums2Max || (i < lenNums1Max && nums1Max[i] > nums2Max[j]);
    }
    private int[] merge(int[] nums1Max, int[] nums2Max) {
        int lenCurRes = nums1Max.length + nums2Max.length;
        int[] curRes = new int[lenCurRes];
        for (int i = 0, j = 0, m = 0; m < lenCurRes; ++m) {
            curRes[m] = greater(nums1Max, i, nums2Max, j) ? nums1Max[i++] : nums2Max[j++];
        }
        return curRes;
    }
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = null;
        for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); ++i) {
            int[] merge = merge(maxInNums(nums1, i), maxInNums(nums2, k - i));
            res = (res == null || greater(merge, 0, res, 0)) ? merge : res;
        }
        return res;
    }
}

发奖金问题

过年了，村里要庆祝。村长说，村里有一笔钱作为奖金，让每个人写一个纸条上来，谁写的数目与奖金最接近，就算猜中，这笔奖金就归谁，如果多人猜中，则平分。编写程序，算算都有哪些人得到奖金？多少？

解答：

import java.util.Collections;
import java.util.Comparator;
import java.util.Arrays;
class Q707984 {
    public static void main(String[] args) {
        int award = 100;
        String[] people = { "a", "b", "c", "d", "e", "f", "g", "h" };
        Integer[] guess = { 75, 70, 80, 120, 100, 110, 100, 45 };
        Integer[] ordered = new Integer[people.length];
        for (int i = 0; i < ordered.length; i++)
            ordered[i] = i;
        Arrays.sort(ordered, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                int x = guess[a] - award > 0 ? guess[a] - award : award - guess[a];
                int y = guess[b] - award > 0 ? guess[b] - award : award - guess[b];
                return x - y;
            }
        });
        int maxp = 0;
        int i = 0;
        while (guess[ordered[i++]] == award)
            maxp++;
        if (maxp <= 1)
            System.out.println(people[ordered[0]] + "一人得奖" + award + "元。");
        else {
            for (i = 0; i < maxp; i++)
                System.out.print(people[ordered[i]] + " ");
            System.out.println("共同得奖" + award / (float) (maxp) + "元。");
        }
    }
}

二叉搜索树迭代器(栈、树)

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入 ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] 输出 [null, 3, 7, true, 9, true, 15, true, 20, false] 
解释 BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next();    // 返回 3 bSTIterator.next();    // 返回 7 bSTIterator.hasNext(); // 返回 True bSTIterator.next();    // 返回 9 bSTIterator.hasNext(); // 返回 True bSTIterator.next();    // 返回 15 bSTIterator.hasNext(); // 返回 True bSTIterator.next();    // 返回 20 bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 105] 内
0 <= Node.val <= 106
最多调用 105 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

解答：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
class BSTIterator {
    LinkedList<TreeNode> stack = new LinkedList<>();
    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }
    public int next() {
        TreeNode n = stack.pop();
        TreeNode cur = n.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        return n.val;
    }
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}
/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

本文内容到此结束了，如有收获欢迎点赞
标签：BSTIterator,hasNext,最大数,迭代,int,bSTIterator,next,二叉,cur
From： https://blog.51cto.com/zhanjq/6251918

拼接最大数(栈、贪心)、发奖金问题、二叉搜索树迭代器(栈、树)