运营网站销售队伍建设与管理,济阳网站建设,网络广告投放形式,东莞网站建设公司制作网站力扣爆刷第174天之TOP200五连刷136140#xff08;最小k数、字典序、跳跃游戏#xff09; 文章目录 力扣爆刷第174天之TOP200五连刷136140#xff08;最小k数、字典序、跳跃游戏#xff09;一、LCR 159. 库存管理 III二、450. 删除二叉搜索树中的节点三、440. 字典序的第K小…力扣爆刷第174天之TOP200五连刷136140最小k数、字典序、跳跃游戏 文章目录 力扣爆刷第174天之TOP200五连刷136140最小k数、字典序、跳跃游戏一、LCR 159. 库存管理 III二、450. 删除二叉搜索树中的节点三、440. 字典序的第K小数字四、LCR 127. 跳跃训练五、45. 跳跃游戏 II 一、LCR 159. 库存管理 III
题目链接https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/ 思路本题让求数组中最小的前k个数这类题目是比较常见的一般的有求最大的k个数最小的k个数做法还是比较多的。 1、总体思想是需要排序哪一种都可以但是要兼顾时间复杂度、空间复杂度。 2、一般的做法要么是使用堆排序要么是使用快排。 3、如果是堆排就是维护大顶堆或者小顶堆如果是快排可以利用快排的特性。 4、下面的解法就是利用快排快排的特性就是每次都把一个元素移动到最终的位置上去且让该元素左边的都小于它右边的都大于它。 5、那么我们就可以不全部排序只需要不断的用快排划分区间一旦划分到了k就可以返回了因为划分到了k以后k左边的都小于它右边的都大于它。
class Solution {public int[] inventoryManagement(int[] stock, int cnt) {if(cnt stock.length) return stock;quickSort(stock, 0, stock.length-1, cnt);return Arrays.copyOf(stock, cnt);}void quickSort(int[] stock, int left, int right, int cnt) {if(left right) return;int mid stock[left], i left, j right;while(i j) {while(i j stock[j] mid) j--;while(i j stock[i] mid) i;swap(stock, i, j);}swap(stock, left, i);if(i 1 cnt) quickSort(stock, left, i-1, cnt);if(i 1 cnt) quickSort(stock, i1, right, cnt);}void swap(int[] stock, int left, int right) {int t stock[left];stock[left] stock[right];stock[right] t;}
}二、450. 删除二叉搜索树中的节点
题目链接https://leetcode.cn/problems/delete-node-in-a-bst/description/ 思路本题让删除二叉搜索树中的指定元素值的节点其实思路很简答。 1、首先明确应该分为两个步骤第一个是找到找到对应的节点第二个是删除对应的节点并且维持二叉搜索树的特性。 2、首先考虑遍历方式需要利用二叉搜索树的特性从上往下搜索处理完以后需要递归返回节点所以采用后序遍历的遍历方式。 3、搜索到以后该如何删除可以分为几种情况进行讨论 3.1、如果本身就是叶子节点那么可以直接返回null把该节点删除。 3.2、如果该节点的左子树或者右子树为null也可以直接返回不空的子树。 3.3、只有左右子树都不为null的情况下需要考虑维护二叉搜索树的特性可以找到该节点左子树中最大的节点然后把右子树给拼接过去或者找到该节点右子树中最小的节点然后把左子树给拼接过去。 class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root null) return root;if(key root.val) {root.left deleteNode(root.left, key);}else if(key root.val) {root.right deleteNode(root.right, key);}else{if(root.left null root.right null) return null;if(root.left null) return root.right;if(root.right null) return root.left;TreeNode temp root.left;while(temp.right ! null) temp temp.right;temp.right root.right;return root.left;}return root;}
}三、440. 字典序的第K小数字
题目链接https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/ 思路本题让求字典序的第K小数字所谓字典序也就是如有1-10共10个数字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]。 画出来如下图所示那么让寻找第K小的数字其实对于下面的数结构来说也就是通过前序遍历的方式就可以找到第K小的数字。 1、如何遍历其实对于这个问题因为我们要求是第K小的数字可以把问题转变为统计以某个节点为前缀判断该前缀下节点的数量。 2、通过节点的数量与K的大小判断是继续横向遍历还是纵向遍历。 3、如果总数N为21k为15以1为前缀下的节点数量只有11个即1和10-19.这个数是小于k的所以要横向遍历计算前缀为2下面的节点数量。2下面只有20,21.加和一共13个数是小于15的所以继续横向拓展。
class Solution {public int findKthNumber(int n, int k) {long root 1;k--;while(k 0) {int count countNum(n, root);if(count k) {root;k - count;}else{k--;root * 10;}}return (int)root;}int countNum(int n, long root) {long total 0;long next root 1;while(root n) {total Math.min(n1, next) - root;root * 10;next * 10;}return (int) total;}
}四、LCR 127. 跳跃训练
题目链接https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/description/ 思路本题求跳跃种数也就是每次只能跳一步或者两步其实就是斐波那契数列这么说就好求了不要使用递归递归会有大量的重复计算可以采用动态规划用dp数组记录下前两个所依赖的位置即可。
class Solution {public int trainWays(int num) {long a 1, b 1, c 1;for(int i 2; i num; i) {c a b;c c % 1000000007;a b;b c;}return (int)c;}
}五、45. 跳跃游戏 II
题目链接https://leetcode.cn/problems/jump-game-ii/description/ 思路给定一个数组数组中的每一个数表示可以可以往前跳跃的距离问从Nums[0]开始跳跳越到尾部所需的最小次数。 1、其实很简答只需要从Nums[0]开始维护一个右边界然后在遍历抵达右边界的过程中记录最远可以跳跃到的距离。 2、当抵达到了右边界就把跳跃次数加1把右边界设置为在此过程中记录的最远距离。 3、以此往复就可以。
class Solution {public int jump(int[] nums) {int end 0, max 0, count 0;for(int i 0; i nums.length; i) {if(end nums.length-1) return count;max Math.max(max, i nums[i]);if(end i) {end max;count;}}return count;}
}
