网站设计工作内容,wordpress 国内最好主题,莱芜网站制作公司,淘宝店铺首页设计模板难度#xff1a;中等题目#xff1a;给你一个按升序排序的整数数组 num(可能包含重复数字)#xff0c;请你将它们分割成一个或多个长度为 3 的子序列#xff0c;其中每个子序列都由连续整数组成。如果可以完成上述分割#xff0c;则返回 true #xff1b;否则#xff0c… 难度中等题目 给你一个按升序排序的整数数组 num(可能包含重复数字)请你将它们分割成一个或多个长度为 3 的子序列其中每个子序列都由连续整数组成。 如果可以完成上述分割则返回 true 否则返回 false 。------------------------------------------------------思考 题目要求把数组分割成一或多个连续的子串那就是要把尽可能多的数字弄成子串看着有点像可以贪心。 如果用贪心的话例如实例2先尽可能多的从1开始把12345排成一个子序列然后剩下345排成另一个子序列。 诶好像可以。 但是到了示例1这种就8行了。先拿出12345然后就会只剩下3不成立但其实他却是成立的。 其实上面解释这种只是普通的一般的贪心我们可以改变一下升级一下非一般的贪心。 一个一个地贪心。 思路先用两个hashMap一个countNum用来记录数字出现次数一个tail记录以每个数字num结尾的子序列数。然后遍历数组从头开始先判断countNum的对应数字(例如X)数量是否0如果是则再去查找有没有以数字X-1为结尾的子X序列有则把数字X续上tail的X-1结尾的序列数量-1X结尾的1countNum中的X数量-1。继续判断下一位。如果全部都能连上就是成功。否则有一个不能连上就是失败。以示例1来说 首先看1先去countNum查找1的数量如果0个则再去查找tail。如果有以1前一位(也就是0)结尾的就在后面再续上然后countNum的num的对应数量-1tail的前一位的数量-11结尾的1如果tail没有以前一位结尾话就去看后两位2和3的countNum是不是同时0如果是则连成子串对应的123的countNum-1tail对应的3数量1。 然后看2因为上面123连成了123都-1countNum的2数量0. 再看3上面减了1countNum的3数量为1同样查找tail没有以前一位(2)结尾的直接查看后两位有连成子序列345countNum各个数-1tail为5的1。 最后都可以连上成功。代码public boolean isPossible(int[] nums) { // 用一个哈希表统计每个数字出现的次数 Map countNum new HashMap(); for (int num : nums) countNum.put(num, countNum.getOrDefault(num, 0) 1); // 定义一个哈希表记录最长的子序列 Map tail new HashMap(); for (int num : nums) { int count countNum.getOrDefault(num, 0); if (count 0) {//当前元素已经用完直接跳过 continue; } else if (tail.getOrDefault(num - 1, 0) 0) {//前面还有数字可以构成以num结尾的子序列 countNum.put(num, count - 1); tail.put(num - 1, tail.get(num - 1) - 1);//覆盖当前最长的子序列 tail.put(num, tail.getOrDefault(num, 0) 1);//当前以num结尾的子序列1 } else if (countNum.getOrDefault(num 1, 0) 0 countNum.getOrDefault(num 2, 0) 0) {//前面无数字构成子序列后判断能不能跟后面的构成子序列 countNum.put(num, count - 1); countNum.put(num 1, countNum.get(num 1) - 1); countNum.put(num 2, countNum.get(num 2) - 1); tail.put(num 2, tail.getOrDefault(num 2, 0) 1);//当前以num2结尾的子序列1 } else return false;//前后不能构成子序列则不成立 } return true;}时间复杂度两个独立的循环一个记录各个数字个数一个遍历数字情况。所以是O(n)空间复杂度两个独立的哈希表存储数字个数和子序列数所以是O(n)----------------------------------完--------------------------------淦里良欸
