系列文章目录
前言
一、移除元素
1.题目描述
- 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
- 说明:为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
2.解题思路
- 思路1:定义变量如果当前元素 j 与移除元素 val 相同，那么跳过该元素。如果当前元素 xj与移除元素 val 不同，那么我们将其放到下标 j的位置，并让 j自增右移,最终得到的 j 即是答案。
代码如下：
int removeElement(int* nums, int numsSize, int val)
{
int i=0;
int j=0;
for(i=0;i<numsSize;i++)
{
if(nums[i]!=val)
{
nums[j]=nums[i];
j++;
}
}
return j;
- 思路2:定义两个下标，如果val不等于下标所在的值，则两下标同时加加，否则一个下标加加,返回只加一个下标的值。
代码如下：
int removeElement(int* nums, int numsSize, int val)
{
int dest=0;
int src=0;
while(src<numsSize)
{
if(nums[src]==val)
{
src++;
}
else
{
nums[dest]=nums[src];
dest++;
src++;
}
}
return dest;
}
二、删除有序数组中的重复项
1.题目描述
- 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
- 说明:为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
2.解题思路
- 思路1:定义index值为0，用for循环遍历一次，里面用if条件判断，如果数组中的值不等于下标index的值，则index往前一步，最后返回index+1
代码如下：
int removeDuplicates(int* nums, int numsSize)
{
if (numsSize < 2)
{
return numsSize;
}
int index = 0;
for (int i = 1; i < numsSize; i++)
{
if (nums[i] != nums[index])
{
nums[++index] = nums[i];
}
}
return index + 1;
}
- 思路2:定义三个下标next=1,prev=0;cur=0。
代码如下：
int removeDuplicates(int* nums, int numsSize)
{
if(numsSize==0)
{
return 0;
}
int dest=0;
int cur=0;
int next=1;
while(next<numsSize)
{
if(nums[cur]!=nums[next])
{
nums[dest]=nums[cur];
cur++;
next++;
dest++;
}
else
{
while(next<numsSize && nums[cur]==nums[next])
{
next++;
}
nums[dest]=nums[cur];
dest++;
cur=next;
next++;
}
}
if(cur<numsSize)
{
nums[dest]=nums[cur];
dest++;
}
return dest;
}
三、合并两个有序数组
1.题目描述
- 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
2.解题思路
- 定义数组长度为num1数组长度加num2数组长度，如果num1数组的值大于num2数组的值，则把num1数组的值放到下标为m+n-1的num1中反之把num2的值放进去。
代码如下：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int end1=m-1;
int end2=n-1;
int end=m+n-1;
while(end1 >= 0 && end2 >=0)
{
if(nums1[end1]>nums2[end2])
{
nums1[end]=nums1[end1];
end1--;
end--;
}
else
{
nums1[end]=nums2[end2];
end2--;
end--;
}
}
while(end2 >= 0)
{
nums1[end]=nums2[end2];
end2--;
end--;
}
}
四、旋转数组
1.题目描述
- 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
2.解题思路
思路三代码:
代码如下：
void reverse(int* arr,int left,int right)
{
while(left<right)
{
int tmp=0;
tmp=arr[left];
arr[left]=arr[right];
arr[right]=tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k=k%numsSize;
reverse(nums,0,numsSize-k-1);
reverse(nums,numsSize-k,numsSize-1);
reverse(nums,0,numsSize-1);
}
五、数组形式的整数加法
1.题目描述
- 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
2.解题思路
代码如下：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* addToArrayForm(int* num, int numSize, int k, int* returnSize)
{
int kSize=0;
int n=k;
while(n)
{
++kSize;
n=n/10;
}
int len=kSize>numSize?kSize+1:numSize+1; //求出最后相加数的位数
int* retArr=(int*)malloc(sizeof(int)*len);
int Ai=numSize-1;
int Ki=0;
int next=0;
int reti=0;
while(Ai>=0||Ki<kSize)
{
int aval=0;
if(Ai>=0) //把num数组的元素放到aval中
{
aval=num[Ai];
Ai--;
}
int KVal=k%10;
k=k/10;
Ki++; //算出k的每一位的值
int ret=aval+KVal+next; //相同的位加起来
if(ret>=10)
{
next=1;
ret=ret-10;
}
else
{
next=0;
}
retArr[reti]=ret; //反着过来放数据
reti++;
}
if(next==1) //如果数进了位
{
retArr[reti]=1;
reti++;
}
int begin=0;
int end=reti-1;
while(begin<end)
{
int tmp=retArr[begin];
retArr[begin]=retArr[end];
retArr[end]=tmp;
begin++;
end--;
}
*returnSize=reti;
return retArr;
}
总结
以上就是今天要讲的内容，本文仅仅简单介绍了数组中常见的几道面试题，对于以后面试我们可能会遇到，希望大家掌握。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。
转载：https://blog.csdn.net/qq_44918090/article/details/116566187
查看评论