少儿教育网站建设价格,百度为什么会k网站,手机兼职免费加入不需要任何费用,得物app公司怎么样主页#xff1a;HABUO#x1f341;主页#xff1a;HABUO 1.两数之和返回两数下标
题目#xff1a;给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可以假设每种输…
主页HABUO主页HABUO 1.两数之和返回两数下标
题目给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
示例
输入nums [2,7,11,15], target 9输出[0,1]解释因为 nums[0] nums[1] 9 返回 [0, 1]
输入nums [3,2,4], target 6 输出[1,2]
输入nums [3,3], target 6 输出[0,1]
分析以我们现在的知识水平最容易想到的就是暴力枚举因为我们之前写过冒泡排序类比思想固定一个数据不动遍历其它数据如果和等于target返回这两个数据的下标如果遍历完了还没有那么固定的那个数据1从而固定下一个数据再进行遍历这我们就能感受到这个时间复杂度是不是O(N^2)不太好但知识水平有限我们先这样做随着学习的深入之后我们再以优越的方法解决此题。整体思路见下图 int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{int rest 0;for(rest 0; rest numsSize;rest){//for(int move rest 1 ; move numsSize; move){if(nums[rest]nums[move] target){int* sz (int*)malloc(2*sizeof(int));sz[0] rest;sz[1] move;*returnSize 2;return sz;} }}return NULL;
}
需要注意的是题目中要求是返回两个数据的下标我们都知道return只能返回一个值那怎么办很容易想到以一个数组去返回函数中有一个参数是 int* returnSize这个叫做输出型参数什么意思呢你看我们既然开辟了一个数组函数外需要访问但是不知道数组大小难道一直访问下去吗这肯定会导致越界因此我们需要告诉函数外这个数组的大小是什么returnSize就是完成这个事你看它传的是地址解引用就可以对外部这个数值进行修改因此我们通过此来返回数组的大小。
2.大数相加数组形式整数相加
题目整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。
例如对于 num 1321 数组形式是 [1,3,2,1] 。给定 num 整数的 数组形式 和整数 k 返回 整数 num k 的 数组形式 。
示例
输入num [1,2,0,0], k 34 输出[1,2,3,4] 解释1200 34 1234
输入num [2,7,4], k 181 输出[4,5,5] 解释274 181 455
输入num [2,1,5], k 806 输出[1,0,2,1] 解释215 806 1021
分析
首先我们应该想一下为什么会有这样的一种题背景是什么无论我们的int unsigned int 就是long long 它们所能存储的数据是不是有限那像我们导弹、航空航天的一些数据它可能相当巨大这样的一个类型是不是不能存所以有了数组存大数的这样一种形式。但万变不离其宗你要计算数据是不是要拿到每一位的数对应位进行相加这就是总的思想。所以每步分析见下
第一步题中要求返回的数据以数组形式那我们首先要知道这个数组要设置多大吧所以我们先来分析这个结果数组我们都知道3位数与3位数相加你最大也就是4位数因此呢最终结果数组就是两组数中最大的数再多一位所以我们应该要知道哪组数最大。 //求k的位数int Ksize 0;int Knum k;while(knum){Ksize;Knum / 10;}//求两组数位数最大int len (numSize Ksize ? numSize : Ksize);//建立结果数组int* retArr (int*)malloc(sizeof(int) * (len 1));
第二步是不是就是进入一个循环拿到两组数的每一位然后相加但这里需要考虑一些细节我们算加法时都是从最低位开始算起再一个需要考虑进位的问题还有得到的结果怎么放到数组的一个问题如果我们从后往前方这就存在假设最终没有进位那我们是按照最大的再加一位进行建立的数组那数组第一位是就空着了当然用之前我们所学的顺序表的一些知识可以往前挪这就麻烦了我们可以正着放最终逆置一下就可以达到我们所想要的目的了。 整体思路见下图 这里相应的产出一个问题这是数组大k数值小那如果是k大数组小呢是不是极有可能造成越界访问因此需要解决这样的问题的话进行如下操作如果Ni还有值我们就让nnum[Ni]如果没有值了自然也不会进入到if语句当中我们直接对n定义为0即可。 int n 0;
if (Ni 0)
{n num[Ni];
}
进位的问题我们用一个next值进行保存即可 有进位就让next置1没有进位就让它置0需要注意没有进位的时候要主动置0防止因为上一位的计算所保留的进位影响到该位的计算。具体思想见下
int ret n k % 10 next;
if (ret 9)
{next 1;retArr[Ai] ret - 10;Ai;
}
else
{next 0;retArr[Ai] ret;Ai;
}
当计算走到最后的时候又会出现一个问题即len已经减到0了但是我们如果还有一位进位那么循环进入不进去那这个进位就不会放到数组当中就会导致丢失一个最高位1的 情况怎么解决呢思想就是在最后一步如果产生进位主动的把进位补上即可思想见下 if (len 0 ret 9)
{retArr[Ai] next;retSize retSize 1;
}
所以计算部分整体思路见下
int Ni numSize - 1;
int Ai 0;
int next 0;
while (len--)
{//处理k大数组小导致数组越界访问的情况int n 0;if (Ni 0){n num[Ni];}int ret n k % 10 next;Ni--;k / 10;if (ret 9){next 1;retArr[Ai] ret - 10;Ai;}else{next 0;retArr[Ai] ret;Ai;}//处理最后一步有进位的情况if (len 0 ret 9){retArr[Ai] next;retSize retSize 1;}
}
前面提到我们在建立新的数组中放置数据是正着放的这不是我们所想要的计算结果我们需要对数组进行逆置逆置就相对比较简单只需要建立leftright两个标记进行来回赋值即可 //逆置结果数组
int left 0;
int right retSize - 1;
while (left right)
{int temp retArr[left];retArr[left] retArr[right];retArr[right] temp;left;right--;
}
总代码见下
int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {//求k的位数int Ksize 0;int Knum k;while (Knum){Ksize;Knum / 10;}//求两组数位数最大int len (numSize Ksize ? numSize : Ksize);//建立结果数组int* retArr (int*)malloc(sizeof(int) * (len 1));int retSize len;//结果数组大小//计算过程int Ni numSize - 1;int Ai 0;int next 0;while (len--){//处理k大数组小导致数组越界访问的情况int n 0;if (Ni 0){n num[Ni];}int ret n k % 10 next;Ni--;k / 10;if (ret 9){next 1;retArr[Ai] ret - 10;Ai;}else{next 0;retArr[Ai] ret;Ai;}//处理最后一步有进位的情况if (len 0 ret 9){retArr[Ai] next;retSize retSize 1;}}//逆置结果数组int left 0;int right retSize - 1;while (left right){int temp retArr[left];retArr[left] retArr[right];retArr[right] temp;left;right--;}*returnSize retSize;//返回数组大小return retArr;//返回数组
}
