2024.9.9 中等 难度评分 1333
链接:2181. 合并零之间的节点
(1)题目描述:
(2)示例
(3)分析
整体来说,描述还算清晰的题目,找到0节点所框定的区域,进行加和即可。
思路:从0开始逐个遍历所有节点,进行加和,如果存在0节点,结束本次加和,开启新节点再次加和。(如下,但此代码非常不规范,只作为思维描述)
//代码思路。当然这么写肯定不规范public ListNode mergeNodes(ListNode head) {ListNode node = new ListNode();while (head.next != null) {while (head.next.val != 0) {head = head.next;node.val += head.val;}node.next = node;}return node;}
注意,在链表中,node本身不断变化的 node.next = node,最终指向的,是它的尾节点,是不符合要求的。所以最好新建一个ListNode,next指向node,或者:两者同时指向一个对象。具体如下
(4)代码
class Solution9_9_1 {public ListNode mergeNodes(ListNode head) {ListNode node = new ListNode();ListNode result = new ListNode();result.next=node;//优化后:
// ListNode result = new ListNode();
// ListNode node =result;
// ListNode node = dummy; 并不会改变 dummy 本身的值,
// 而是让 node 和 dummy 都引用同一个对象。
// 通过 node 修改对象的属性(例如 node.next),
// dummy 也会“看到”这些修改,因为它们指向同一个对象。ListNode head1 = head.next;//去除头节点int sum = 0;//统计结果。while (head1 != null) {if (head1.val == 0)//创建新节点{node.next = new ListNode(sum);node = node.next;// 移动到下一个节点sum = 0;// 重置累加器} else {sum += head1.val;//累加}head1 = head1.next;//移动到下一个节点}
// return node; 这里有个易错点,直接返回node,在循环中,
// node本身不断变化 node = node.next,最终指向的,是它的尾节点,是不符合要求的。
// 所以最好新建一个ListNode,next指向node,return result.next.next;//因为我们写的,开头会默认两个0节点,所以两个next
// 优化后:
// return result.next;}
}
(5)碎碎念
其实,还是说,对链表这种不太熟悉,有时总会忘记他循环的特性,直接用,老是报错。
2024.9.10 困难 难度评分 2433
链接:2552. 统计上升四元组
(1)题目描述:
(2)示例
(3)分析
题目越短,事儿越大。依据题目要求,这次给我们的实际上找一个:满足”波浪式“的四个元素:小小 大 小 大大,最大值在最右侧。很明显,最大值的存在必须在第3位之后,所以我们不妨拿出最大值。
观察 “波浪式” 数据:2个数大小定后,再加一位定三元组,再加后定四元组。而这个过程是类似的,于是可以抽象出来:
(1)满足2元组【小,大】后,判断大和接下来值大小,
① 如果大,此前所有二元组皆可换为三元组,(指:大 > 接下来的值)
② 如果小,很难直接决定
(2)满足三元组【小小 大 小】后,判断大和接下来值大小
① 如果大,很难直接决定
② 如果小,二元组备选量+1,此前所有三元组皆可换为四元组
大家一定注意:题目中所有数字皆不同,并且我们发现,通过右侧和下一个值的比对,我们可以确定的,分别是对二元组、三元组的确定。但同时我么知道:每一个组得到皆有前一个获得,或间接决定。(这是我的一开始思路,但没写出来,直接复制灵神的了。)
(4)代码
class Solution {public long countQuadruplets(int[] nums) {long cnt4 = 0;int[] cnt3 = new int[nums.length];for (int l = 2; l < nums.length; l++) {// l从2开始,是为了算上开头三个就符合排序的// 外层循环:作为四元组中的第四个元素,遍历数组的每一个可能位置int cnt2 = 0;for (int j = 0; j < l; j++) {// 内层循环:j 从 0 开始到 l-1,//对于每一个 l,通过 j 遍历之前的元素,尝试找到符合条件的三元组 (i, j, k)。// cnt2:用于计数在当前循环中,满足 nums[i] < nums[k] 的二元组的数量。//每当发现一个这样的组合时,它将帮助更新 cnt3[j]。if (nums[j] < nums[l]) { // 3 < 4,当接下来的符合时,直接把全部的三元组的数量加和到,就是符合条件的四元组cnt4 += cnt3[j];// 把 j 当作 i,把 l 当作 k,现在 nums[i] < nums[k],即 1 < 2cnt2++;} else {// 如果 nums[j] > nums[l],则表示 j 可以成为四元组中第2大的元素,// 因此将 cnt2(当前符合 nums[i] < nums[k] 的二元组数量)累加到 cnt3[j] 中,表示形成了新的三元组。cnt3[j] += cnt2;}}}return cnt4;}
}
(5)碎碎念
有些抽象的……,花了非常多的时间。
2024.9.11 中等 难度评分 2081
链接:2555. 两个线段获得的最多奖品
(1)题目描述:
(2)示例
(3)分析
首先呢,做一个解释:x轴上放了一些奖品,现在把放奖品的坐标告诉我们了,并且是2个间段内获得奖品,那么:只要两个间段大于奖品区间大小,即可全部获得。
接下来,逐步判断即可,因为给的是坐标,所以,差值不大于k,即可包揽。
于是:prizePositions[i]-prizePositions[0]>k为临界点,此时最大获得为i个, 这是第一次判断,但判断的不只是以0来判断,换为标识符start ,最大获得为:i-start,但为了下一次循环,strat得++。那么,很显然i-start+1 为当此获得的最大个数(已经++了),我们需要一个值来存储它。最后,sum就由:sum本身或(i-start+1 + 和距他k单位统计的值 )的最大值来决定。
(4)代码
class Solution {public int maximizeWin(int[] prizePositions, int k) {int len=prizePositions.length;//做一个解释:x轴上放了一些奖品,现在把放奖品的坐标告诉我们了,并且是2个间段内获得奖品//那么:只要两个间段大于奖品区间大小,即可全部获得。if(2*k>prizePositions[len-1]-prizePositions[0]){return len;}//接下来,是逐步判断,可取得奖品的条件是:长度小于等于k内的,//因为给的是坐标,所以,差值即可,差值不大于k,即可包揽.int sum=0;int start=0;int[] getTotall=new int[len+1];for(int i=0;i<len;i++){// 于是:prizePositions[i]-prizePositions[0]>k为临界点,此时最大获得为i个,// 这是第一次判断,但判断的不只是以0来判断,换为标识符start ==》 最大获得为:i-start,但为了下一次循环,strat得++// 于是:i-start+1 为当此获得的最大个数,我们需要来存储它。getTotall就是,// 那么,sum就由:sum本身或(i-start+1 + 和距他k单位统计的值 )的最大值 来决定// start指定这是哪一次,while(prizePositions[i]-prizePositions[start]>k){start++;}sum = Math.max(sum,getTotall[start]+i-start+1);getTotall[i+1] = Math.max(getTotall[i],i-start+1);}return sum;}
}
(5)碎碎念
这几天,写的都有些折磨……
2024.9.12 中等 难度评分 1843
链接:2576. 求出最多标记下标
(1)题目描述:
(2)示例
(3)分析
根据题目:我们返回的并非是标注的下标,而是数目。涉及到大小比较,所以对数据进行排序比较好,排好序后,便可对其拆分区域。
一个len长度的数组,最少比对len/2次。其中,最多表记数为len。
我们举个例子:2 3 5 7 11 16,要想最大,就需要拆开划分一半低,一般高用于被比对。
在比较时,很明显,最优的情况,第一位 和 第(len/2+1)位比对,然后依次判断。
(4)代码
class Solution {//我们返回的并非是标注的下标,而是数目。涉及到大小比较,所以对数据进行排序比较好public int maxNumOfMarkedIndices(int[] nums) {Arrays.sort(nums);int len=nums.length;int sum=0;// 一个len长度的数组,最少比对len/2次。其中,最多表记数为len//我们举个例子:2 3 5 7 11 16,要想最大,就需要拆开划分一半低,一般高用于被比对。//在比较时,很明显,最优的情况,第一位 和 第(len/2+1)位比对,然后依次判断。int right= len/2;int left = 0;while (left <len/2 && right<len) {if (2*nums[left]<=nums[right]){sum+=2;left++;} right++;}return sum;}
}
(5)碎碎念
这个还行,没费太多时间。