交友系统网站建设,做网站图片表情,免费网址推荐,做搜狗手机网站快速排LeetCode第358场周赛 数组中的最大数对和翻倍以链表形式表示的数字限制条件下元素之间的最小绝对差 数组中的最大数对和
给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数#xff0c;且这两个数数位上最大的数字相等。 返回最大和#xff0c;如果不存在满… LeetCode第358场周赛 数组中的最大数对和翻倍以链表形式表示的数字限制条件下元素之间的最小绝对差 数组中的最大数对和
给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数且这两个数数位上最大的数字相等。 返回最大和如果不存在满足题意的数字对返回 -1 。 示例 1 输入nums [51,71,17,24,42] 输出88 解释 i 1 和 j 2 nums[i] 和 nums[j] 数位上最大的数字相等且这一对的总和 71 17 88 。 i 3 和 j 4 nums[i] 和 nums[j] 数位上最大的数字相等且这一对的总和 24 42 66 。 可以证明不存在其他数对满足数位上最大的数字相等所以答案是 88 。 示例 2 输入nums [1,2,3,4] 输出-1 解释不存在数对满足数位上最大的数字相等。 提示 2 nums.length 100 1 nums[i] 104
思路 首先根据nums.length可以知道数据范围并不大因此我们可以直接暴力枚举整数数组nums中的两个数判断这两个数数位上最大的数字是否相等。维护一个maxx用于存储最大和若满足条件即这两个数数位上最大的数字相等则更新maxx。 代码
class Solution {
public:int maxSum(vectorint nums) {int maxx-1;for(int i0;inums.size();i){for(int ji1;jnums.size();j){int ma10,ma20,tmp1nums[i],tmp2nums[j];while(tmp1){ma1max(ma1,tmp1%10);tmp1/10;}while(tmp2){ma2max(ma2,tmp2%10);tmp2/10;}if(ma1ma2)maxxmax(maxx,nums[i]nums[j]);}}return maxx;}
};翻倍以链表形式表示的数字
给你一个 非空 链表的头节点 head 表示一个不含前导零的非负数整数。 将链表 翻倍 后返回头节点 head 。 示例 1 输入head [1,8,9] 输出[3,7,8] 解释上图中给出的链表表示数字 189 。返回的链表表示数字 189 * 2 378 。 示例 2 输入head [9,9,9] 输出[1,9,9,8] 解释上图中给出的链表表示数字 999 。返回的链表表示数字 999 * 2 1998 。 提示 链表中节点的数目在范围 [ 1 , 1 0 4 ] [1, 10^4] [1,104] 内 0 N o d e . v a l 9 0 Node.val 9 0Node.val9 生成的输入满足链表表示一个不含前导零的数字除了数字 0 本身。
思路 这道题主要考察的是对链表的操作既然要对链表翻倍那么我们一定要考虑到进位如何表示可以先将链表进行翻转翻转之后对链表的各个数字进行翻倍的操作会变得简单一些。最后再将链表翻转回来即可。 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode *reverse(ListNode *p){ListNode *qNULL;while(p){//链表翻转ListNode *x(ListNode*)malloc(sizeof(ListNode));x-valp-val;if(qNULL){qx;q-nextNULL;}else{x-nextq;qx;}pp-next;}return q;}ListNode* doubleIt(ListNode* head) {int num0;ListNode *p,*x,*q;phead;qreverse(p);ListNode *hq;int pre0;while(q){//将链表进行翻倍int kq-val;k*2;q-valk%10pre;prek/10;//加在下一位上qq-next;}hreverse(h);if(pre){//如果最高位也需要进位x(ListNode*)malloc(sizeof(ListNode));x-valpre;x-nextNULL;x-nexth;hx;}return h;}
};限制条件下元素之间的最小绝对差
给你一个下标从 0 开始的整数数组 nums 和一个整数 x 。 请你找到数组中下标距离至少为 x 的两个元素的 差值绝对值 的 最小值 。 换言之请你找到两个下标 i 和 j 满足 abs(i - j) x 且 abs(nums[i] - nums[j]) 的值最小。 请你返回一个整数表示下标距离至少为 x 的两个元素之间的差值绝对值的 最小值 。 示例 1 输入nums [4,3,2,4], x 2 输出0 解释我们选择 nums[0] 4 和 nums[3] 4 。 它们下标距离满足至少为 2 差值绝对值为最小值 0 。 0 是最优解。 示例 2 输入nums [5,3,2,10,15], x 1 输出1 解释我们选择 nums[1] 3 和 nums[2] 2 。 它们下标距离满足至少为 1 差值绝对值为最小值 1 。 1 是最优解。 示例 3 输入nums [1,2,3,4], x 3 输出3 解释我们选择 nums[0] 1 和 nums[3] 4 。它们下标距离满足至少为 3 差值绝对值为最小值 3 。 3 是最优解。 提示 1 n u m s . l e n g t h 1 0 5 1 nums.length 10^5 1nums.length105 1 n u m s [ i ] 1 0 9 1 nums[i] 10^9 1nums[i]109 0 x n u m s . l e n g t h 0 x nums.length 0xnums.length
思路 看到数据范围知道暴力枚举方法必定会时间超限看到两个下标我第一眼想到的就是双指针滑动窗口的方法。当我们处理第i个数的时候如果ix以及之后的数是有序的那么我们可以通过二分很快计算出最接近与nums[i]的数。 如何维护这个有序的序列呢。数据结构set可以保证集合的有序使用multiset可以保证序列中存在重复的数字。 所以我们初始化一个multiset命名ms一开始将从x位置往后的所有数字都插入ms中。从下标为0的位置i开始逐一枚举找到和其下标距离大于等于x且与其最相近的一个数可以使用lower_bound找到第一个大于等于该数的数a。但是与此同时我们还需要考虑这个数字a的前一个数字(即小于该数的最大的数)计算这两个数和nums[i]的差值维护最小值即可。 然后开始移动窗口往右移动一格则第ix的数需要移出因为距离小于x了。然后还需要将i1-x位置的数移入因为该位置距离为x。 代码
class Solution {
public:int minAbsoluteDifference(vectorint nums, int x) {if(x0)return 0;multisetintms;//用来维护一个有序的集合int nnums.size();for(int ix;in;i)ms.insert(nums[i]);int ans1e9;for(int i0;in;i){auto itms.lower_bound(nums[i]);//找到后面的大于等于nums[i]的最小的数字if(it!ms.end())ansmin(ans,*it-nums[i]);if(it!ms.begin())ansmin(ans,nums[i]-*prev(it));//找到该数字的前一个数字//移动窗口if(ixn)ms.erase(ms.find(nums[ix]));//往后移动移除if(i1-x0)ms.insert(nums[i1-x]);//这个位置的数也符合要求了}return ans;}
};
