🙂回顾一下前面。随便整理复习一下。抽空再做做。
消失的数字
一个数组中只有两个数字出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。
#include<stdio.h> int main() { int arr[] = { 1,2,3,4,6,1,2,3,4,5 };//5 6 int sz = sizeof(arr) / sizeof(arr[0]); int i = 0; int ret = 0; //1.全部^到一起 for (i = 0; i < sz; i++) { ret ^= arr[i]; } //2.找到为1的n位 int n = 0;//n是为1的位数 for (n = 0; n < 32; n++)//4个字节32个bite位 { if (((ret>>n) & 1 )== 1) { break;//n是移动几位，第几位 } } //3.分组 int r1 = 0; int r2 = 0; for (i = 0; i < sz; i++) { if (((arr[i] >> n)&1) == 1) { r1 ^= arr[i]; } if (((arr[i] >> n) & 1) == 0) { r2 ^= arr[i]; } } printf("r1=%d r2=%d\n", r1, r2); //返回下标 int j = 0; for (j = 0; j < sz; j++) { if (arr[j] == r1) printf("r1下标：%d\n", j); if (arr[j] == r2) printf("r2下标：%d\n", j); } return 0; }
消失的数字Ⅱ
数组
nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？动手写一写。
int missingNumber(int* nums, int numsSize){ int ret=0; int i=0; for(i=0;i<numsSize;i++)//先把数组全部数组异或 0~N缺少一个数字所以是N+1-1个数字即N个数字 { ret^=nums[i]; } for(i=0;i<=numsSize;i++)//得到的结果再次异或0~N数字 0~N有N+1个数字 { ret^=i; } return ret; }
删除两个有序数组中的重复项
给你一个 非严格递增排列 的数组
nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回nums中唯一元素的个数。
int removeDuplicates(int* nums, int numsSize) { int dst=1; int src=0; while(dst<numsSize) { if(nums[src] != nums[dst]) { src++; nums[src]=nums[dst]; dst++; } else { dst++; //为什么这里src++移动到需要覆盖的位置，因为dst和src还要比较 //可以想下三指针怎么搞！ } } return src+1;//易错 } //数据下标 //指针呢？ //三个指针？ //用辅助数组也可以但是没必要
右旋转字符串结果
字符串旋转结果
写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如：
给定s1= AABCD和s2 = BCDAA，返回1
给定s1=abcd和s2=ABCD，返回0
#include<stdio.h> #include<string.h> #include<assert.h> int is_left_move(char* arr1, const char* arr2) { assert(arr1 && arr2); int len1 = strlen(arr1); int len2 = strlen(arr2); if (len1 != len2) { return 0; } int len = strlen(arr1); strncat(arr1, arr1, len); if (strstr(arr1, arr2) == NULL) return 0; else return 1; } int main() { char arr1[] = "ABCDEF"; char arr2[] = "CDEFAB"; int ret=is_left_move(arr1, arr2); if (ret == 1) { printf("YES"); } else { printf("NO"); } return 0; }
左旋转字符串
字符串左旋
实现一个函数，可以左旋字符串中的k个字符
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
#include<stdio.h> //逆序字符串函数 void reverse(char* begin, char* end) { while (begin < end) { char tmp = 0; tmp = *begin; *begin = *end; *end = tmp; begin++; end--; } } int main() { char arr[] = "ABCDEF"; int sz = sizeof(arr)/sizeof(arr[0]); int k = 0; scanf_s("%d", &k); k = k % (sz - 1);//必须有不然会数组越界 reverse(arr, arr + k-1); reverse(arr + k, arr + sz - 2); reverse(arr, arr + sz - 2); printf("%s", arr); return 0; }
轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
void rotate(int* nums, int numsSize, int k) { int tmp[numsSize]; int i=0; k%=numsSize;//就这个代码卡了我一下午，有时候真的很无助 for(i=0;i<k;i++) { *(tmp+i)=*(nums+numsSize-k+i); } for(i=0;i<numsSize-k;i++) { *(tmp+k+i)=*(nums+i); } for(i=0;i<numsSize;i++) { *(nums+i)=*(tmp+i); } }
移除数组元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
int removeElement(int* nums, int numsSize, int val) { int src=0; int dst=0; while(src<numsSize) { if(nums[src] != val) { nums[dst++]=nums[src++]; } else { src++; } } return dst; } //这里使用的是下标 //那指针呢？ //用辅助数组也可以，具体情况看题目要求
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int p1=m-1; int p2=n-1;//下标和元素个数的关系 int j=m+n-1; while(p2>=0&&p1>=0) { if(nums1[p1]<nums2[p2]) { nums1[j--]=nums2[p2]; p2--; } else//p1>p2 { nums1[j--]=nums1[p1]; p1--; } } while(p2>=0) { nums1[j--]=nums2[p2--]; } }
