本文主要是介绍力扣爆刷第174天之TOP200五连刷136=140(最小k数、字典序、跳跃游戏),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第174天之TOP200五连刷136=140(最小k数、字典序、跳跃游戏)
文章目录
- 力扣爆刷第174天之TOP200五连刷136=140(最小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, i+1, 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为21,k为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(n+1, 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;}
}
这篇关于力扣爆刷第174天之TOP200五连刷136=140(最小k数、字典序、跳跃游戏)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!