1、链表中倒数第k个结点
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
这道题依然利用双指针法，具体解题思路如下：
1、创建两个指针 fast 和 slow 并让它们开始时指向同一个位置
2、使用一个循环将 fast 指针向前移动 k 步。这样，在循环结束后，如果整个链表长度小于等于 k，则说明无法找到倒数第 k 个节点，直接返回空指针
3、接下来使用另一个循环，在每次迭代中将 fast 和 slow 指针同时向前移动一步，直到达到链表末尾（即 fast 指针为空）
4、最后返回 slow 指针所指向的位置即可得到倒数第 k 个节点
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast = pListHead,*slow = pListHead; while(k--) { if(fast == NULL) return NULL; fast = fast->next; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }
这道题的思路在做题的时候感觉有点不太好想[也有可能是我太废物了🤡]
2、消失的数字
面试题 17.04. 消失的数字 - 力扣（LeetCode）
令完整数组与不完整数组进行异或运算，两个数组中的数字基本都是两两配对的，它们异或后的结果都为零，而两个数组异或的结果必然是那个没有成对的数字，它就是我们要找的消失的数字
异或运算的规则是：相同为0，不同为1
题目中给的数组是包含从0到n的所有整数，但其中缺了一个，这就证明它是一个没有重复数字的数组，这样我们就可以直接定义一个变量num并初始化为0，用num与完整数组循环异或运算后得到的结果再与不完整数组进行循环异或，这里的num起到一个连接两次异或的作用，同时初始化为0也能保证它在异或过程中不会成为干扰因素（因为0与完整数组中的0异或后结果仍未0）
int missingNumber(int* nums, int numsSize) { //异或的办法是相同为0不同为1 int num = 0; //这里要以后n+1次，表示与完整数组进行异或 for(int i = 0;i<=numsSize;i++) { num^=i; } //这里要异或n次，表示与不完整数组进行异或 for(int i = 0;i<numsSize;++i) { num^=nums[i]; } return num; }
3、轮转数组
在这里我们可以发现当数组旋转六次时的情况与数组旋转一次时的情况是一样的，即使旋转次数可以随意增加，但是实际上它们旋转后的结果与旋转1、2、3、4、5次是没有区别的，所以为了减少代码执行时间我们利用取余的办法获取数组的真实旋转次数：k = k % numSize，其中k为数组旋转次数，numSize为数组实际长度
确定了实际旋转的次数后，就可以进行数组轮转操作，具体过程如下图所示：
1、翻转整个数组
这是因为我们发现每次的轮转都是将后面的数字轮转到前面然后前面的数字向后移动，所以我们直接将靠后的与靠前的元素位置来一个完全大反转，让靠后的数组元素全都跑到前面来
2、先将[0,k-1]范围的数组元素翻转，后将[k,sumSize-1]范围的数组元素翻转
先翻转的部分其实就是我们轮转数组时真正要操作的数组元素，而后翻转的其实就是不用操作的数组元素，由于我们之前进行了一次大翻转，现在我们只需要让它们重归原位即可
至于如何进行局部的反转请看下图：
最终代码如下：
//换位函数 void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } //伪双指针一前一后成对交换数组元素 void reverse(int* nums, int start, int end) { while (start < end) { swap(&nums[start], &nums[end]); start += 1; end -= 1; } } //规定要翻转的数组范围 void rotate(int* nums, int numsSize, int k) { k %= numsSize; reverse(nums, 0, numsSize - 1); reverse(nums, 0, k - 1); reverse(nums, k, numsSize - 1); }
4、合并两个有序数组
最讨巧的方法就是直接将一个数组合并至另一个数组的尾部，然后直接利用qsort函数对整个数组进行排序，关于qsort函数的使用请看Qsort函数实现对各类型数组中元素的排序
int cmp(int* a, int* b) { return *a - *b; } void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { for (int i = 0; i != n; ++i) { nums1[m + i] = nums2[i]; } qsort(nums1, nums1Size, sizeof(int), cmp); }
它的时间复杂度为 O((m + n) log (m + n)) 较高，我们还有另外一种更简单的方式来解决该问题：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { while(n) nums1[m+n]=(m==0 || nums1[m-1]<nums2[n-1]) ? nums2[--n] : nums1[--m]; }
这段代码的时间复杂度为O(n)，该函数使用了一个 while 循环来进行逆向合并操作，我们令两个数组在每次循环迭代中，根据比较当前两个数组末尾元素的大小关系，选择将较大的元素放入 nums1 数组末尾，并相应地更新索引。由于nums1.length == m + n 所以不用担心新放入的数组元素会覆盖掉原来的数组元素，提供的数组除了边界情况下都会有多个零来占位。
需要注意的是：长语句的执行顺序是先进行三元运算符的判断，如果不满足条件则m会先执行减减操作后再使用，所以不用担心[m+n]会产生数组越界的问题，此外由于0<=m，n<=200 所以还需要考虑m=0时的情况。
5、数组串联
摘选自评论区的一句话："题库 - 通过率倒序排列 - 点第一个 - 提交 ： 我又行了！"
具体解题思路如下：
1、利用malloc开辟一个原来数组内存空间的两倍大小的空间
2、利用两侧for循环将原数组两次放入新开辟的内存空间中，第一层for循环控制要拷贝数组的次数，第二层for循环控制每一个数组元素的拷贝
3、返回指向申请的内存空间起始地址的指针变量connect前，还需要将串联后数组的大小传递给调用者也就是* returnSize = numSize * 2
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* getConcatenation(int* nums, int numsSize, int* returnSize) { int* connect = malloc (sizeof(int)*numsSize*2); int p = 0; for(int i = 0;i<2;i++) { for(int j = 0;j<numsSize;j++) { connect[p++] = nums[j]; } } * returnSize = numsSize*2; return connect; }
6、序列中删除指定数字
序列中删除指定数字_牛客题霸_牛客网 (nowcoder.com)
这道题就当提升自信了......
#include<stdio.h> int main() { int i,j; int n,m; //创建一个新的数组arr1用于存放未删除后的数组元素 int arr1[50]; //创建一个新的数组arr2用于存放删除后的数组元素 int arr2[50]; //选择创建新数组的大小 scanf("%d",&n); //创建该新数组 for(i=0;i<n;i++) { scanf("%d",&arr1[i]); } //选择要删除的数字 scanf("%d",&m); //利用循环将值不等于m的数字放入新的数组中 for(i=0,j=0;i<n;i++) { if(m!=arr1[i]) { arr2[j]=arr1[i]; j++; } } //打印新数组 for(i=0;i<j;i++) { printf("%d ",arr2[i]); } return 0; }
~over~
