文章目录
leetcode 14天算法入门 C语言实现第一天 二分查找第二天 双指针第三天 双指针第四天 双指针第五天 双指针第六天 滑动窗口第七天 广度优先搜索 / 深度优先搜索第八天 广度优先搜索 / 深度优先搜索第九天 广度优先搜索 / 深度优先搜索第十天 递归 / 回溯第十一天 递归 / 回溯第 十二 天 动态规划第 十三天 位运算第 十四天 位运算第 十四天 位运算
leetcode 14天算法入门 C语言实现
第一天 二分查找
二分法讲解 : 把答案所在的区间逐渐缩小，直到区间内只有答案。
图解:
704. 二分查找
思路:二分思想,不用解释直接上手
代码:
int search(int* nums, int numsSize, int target){
int left=0;
int right=numsSize-1;
while(left<=right)
{
int mid=(right-left)/2+left;
if(nums[mid]==target)
{
return mid;
}
if(nums[mid] { left=mid+1; } else { right=mid-1; } } return -1; } 278. 第一个错误的版本 思路:还是基本的二分思想,当mid是真时,说明mid处为真,则left=mid+1,如此不断缩小间距,当left>=right时left处指的一定是第一个错误版本(此处不在证明) 代码: // The API isBadVersion is defined for you. //bool isBadVersion(int version); int firstBadVersion(int n) { int left=1; int right=n; while(left { int mid=(right-left)/2+left; bool tmp=isBadVersion(mid); if(!tmp) { left=mid+1; } else { right=mid; } } return left; } 35. 搜索插入位置 思路:*nums*[*p**o**s*−1]<*target*≤*nums*[*p**o**s*]只要需要理解这个概念就ok了 代码: int searchInsert(int* nums, int numsSize, int target){ int left=0; int right=numsSize-1; int mid=0; while(left<=right) { mid=(right-left)/2+left; if(nums[mid]==target) { return mid; } if(nums[mid]>target) { right=mid-1; } else { left=mid+1; } } return left; } 第二天 双指针 双指针法讲解:双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。 977. 有序数组的平方 思路:1.每个数都平方,平方后在排序,当然这就和双指针以及题目的非递减条件无关了. 2.最大的平方数一定出自左端或右端,所以使用双指针,一个左端一个右端,左右交替选最大平方值. 代码: int mul(int a) { return a*a; } int* sortedSquares(int* nums, int numsSize, int* returnSize){ int left=0; int right=numsSize-1; *returnSize=numsSize; int *answer=(int *)malloc(sizeof(int)*numsSize); int loc=numsSize-1; while(left<=right) { if(mul(nums[left])>mul(nums[right])) { answer[loc]=mul(nums[left]); left++; } else { answer[loc]=mul(nums[right]); right--; } loc--; } return answer; } 189. 轮转数组 思路:k的左边反转,k的右边反转,最后对于数组整体反转,即可以完成实现 代码: void swap(int *a,int *b) { int tmp=*a; *a=*b; *b=tmp; } void exchange(int *nums,int left,int right) { while(left { swap(nums+left,nums+right); left++; right--; } } void rotate(int* nums, int numsSize, int k){ k=k%numsSize; exchange(nums,0,numsSize-1-k); exchange(nums,numsSize-k,numsSize-1); exchange(nums,0,numsSize-1); } 第三天 双指针 283. 移动零 思路:注释部分是我第一次写的,使用的两个指针来记录0和非0的位置,进行移动操作 非注释时对该代码的简化 代码: void swap(int *a,int *b) { int tmp=*a; *a=*b; *b=tmp; } void moveZeroes(int* nums, int numsSize){ // int numloc=0; // int zeroloc=0; // while(numloc // { // while(zeroloc // { // zeroloc++; // } // if(zeroloc==numsSize) // { // break; // } // //numloc=zeroloc+1; // while(numloc // { // numloc++; // } // if(numloc>=numsSize||zeroloc>=numsSize) // { // break; // } // if(numloc>zeroloc) // swap(nums+zeroloc,nums+numloc); // //zeroloc++; // numloc++; // } int left = 0, right = 0; while (right < numsSize) { if (nums[right]) { swap(nums + left, nums + right); left++; } right++; } } 167. 两数之和 II - 输入有序数组 思路:左指针,右指针,大于目标数,右指针左移.小于目标数,左指针右移. 代码: /** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){ int left=0; int right=numbersSize-1; int *answer=(int *)malloc(sizeof(int)*2); *returnSize=2; while(1) { if(numbers[left]+numbers[right]==target) { answer[0]=left+1; answer[1]=right+1; break; } else if(numbers[left]+numbers[right] { left++; } else { right--; } } return answer; } 第四天 双指针 344. 反转字符串 思路:就左指针与右指针交换即可 代码: void swap(char *a, char *b) { char t = *a; *a = *b, *b = t; } void reverseString(char* s, int sSize){ int left=0,right=sSize-1; while(left { swap(s + left, s + right); left++; right--; } } 557. 反转字符串中的单词 III 思路:难点就在于寻找每一个单词 代码: void swap(char *a,char *b) { char tmp=*a; *a=*b; *b=tmp; } void revers(char *arr,int begin,int end) { while(begin { swap(arr+begin,arr+end); begin++; end--; } } char * reverseWords(char * s){ int begin=0; int last=0; int len=strlen(s); while(last<=len) { while(s[begin]==' ') { begin++; } while(s[last]!=' '&&s[last]!='\0') { last++; } revers(s,begin,last-1); if(s[last]=='\0') { break; } begin=last+1; last+=1; } return s; } 第五天 双指针 876. 链表的中间结点 思路:一个快指针一次走两步(最后一次可能走一步,因为两个中间节点的第二个),一个慢指针一次走一步,当快指针的next=null时,此时慢指针指向中间节点. 代码: struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow=head; struct ListNode*fast=head; while(fast->next&&fast->next->next) { fast=fast->next->next; slow=slow->next; } if(fast->next) { slow=slow->next; } return slow; } 19. 删除链表的倒数第 N 个结点 思路:找到该节点,删除即可. 代码: struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ struct ListNode*fast=head; struct ListNode*guard=(struct ListNode*)malloc(sizeof( struct ListNode)); int i=1; struct ListNode* slow=guard; slow->next=head; while(fast->next) { if(i>=n) { slow=slow->next; } i++; fast=fast->next; } struct ListNode*tmp=slow->next; slow->next=tmp->next; head=guard->next; free(tmp); free(guard); return head; } 第六天 滑动窗口 567. 字符串的排列 思路:采用滑动窗口,判断窗口中的数量是否与s1相同 代码: bool check(int s1_arr[],int s2_arr[]) { for(int i=0;i<26;i++) { if(s1_arr[i]!=s2_arr[i]) { return false; } } return true; } bool checkInclusion(char * s1, char * s2){ int n=strlen(s1); int m=strlen(s2); if(n>m) { return false; } int s1_arr[26]; int s2_arr[26]; memset(s1_arr,0,sizeof(s1_arr)); memset(s2_arr,0,sizeof(s2_arr)); for(int i=0;i { s1_arr[*(s1+i)-'a']++; } for(int i=0;i { s2_arr[*(s2+i)-'a']++; } if(check(s1_arr,s2_arr)) { return true; } for(int i=n;i { s2_arr[*(s2+i)-'a']++; s2_arr[*(s2+i-n)-'a']--; if(check(s1_arr,s2_arr)) { return true; } } return false; } 3. 无重复字符的最长子串 思路:计算窗口的最大值即可 代码: int lengthOfLongestSubstring(char * s){ int left=0; int right=0; int max=0; int len=strlen(s); int j=0,i=0; int same=0; //for(int i=0;i while(right { if(left { //判断是否重复 same=0; for(j=left;j { if(s[j]==s[right]) { same=1; break; } } if(same) left=j+1; } max=max>(right-left+1)?max:(right-left+1); right++; } return max; } 第七天 广度优先搜索 / 深度优先搜索 733. 图像渲染 思路:先修改最初的起点,再在修改起点上下左右的点,再然后再把四个点都作为起点,依次进行. 代码: void dfs(int **image,int color,int curcolor,int row,int col,int sr,int sc) { if(sr { if(image[sr][sc]==curcolor) { image[sr][sc]=color; dfs(image,color,curcolor,row,col,sr-1,sc); dfs(image,color,curcolor,row,col,sr+1,sc); dfs(image,color,curcolor,row,col,sr,sc-1); dfs(image,color,curcolor,row,col,sr,sc+1); } } return ; } int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes){ int row =imageSize; int col=imageColSize[0]; //行数 *returnSize=row; //列数 *returnColumnSizes=(int *)malloc(sizeof(int)*row); for(int i=0;i { (*returnColumnSizes)[i]=col; } int curcolor=image[sr][sc]; if(curcolor!=color) { dfs(image,color,curcolor,row,col,sr,sc); } return image; } 695. 岛屿的最大面积 思路:深度递归即可,每次遍历到1就修改为0.选出最大值即可 代码: int dfs(int **grid,int gr,int gc,int row, int col) { if(gr { if(grid[gr][gc]==1) { grid[gr][gc]=0; int tmp1=dfs(grid,gr-1,gc,row,col); int tmp2=dfs(grid,gr+1,gc,row,col); int tmp3=dfs(grid,gr,gc-1,row,col); int tmp4=dfs(grid,gr,gc+1,row,col); return 1+tmp1+tmp2+tmp3+tmp4; } else { return 0; } } return 0; } int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){ int max=0; int row=gridSize; int col=*gridColSize; for(int i=0;i { for(int j=0;j<*gridColSize;j++) { if(grid[i][j]==1) { int tmp = dfs(grid,i,j,row,col); max=max>tmp?max:tmp; } } } return max; } 第八天 广度优先搜索 / 深度优先搜索 617. 合并二叉树 思路:遍历每一个节点即可. 代码: struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){ if(!root1&&!root2) { return NULL; } if(!root1) { return root2; } if(!root2) { return root1; } struct TreeNode* head=(struct TreeNode*)malloc(sizeof(struct TreeNode)); head->val=root1->val+root2->val; head->left= mergeTrees(root1->left,root2->left); head->right= mergeTrees(root1->right,root2->right); return head; } 116. 填充每个节点的下一个右侧节点指针 思路:根据图可以理解,最难的部分是判断5->6,使用 if(root->next&&root->right) root->right->next=root->next->left;即可解决. 代码: // void connectTwoNode (struct Node* a, struct Node* b){ // if (a == NULL || b == NULL) // return; // a->next = b; // connectTwoNode(a->left,a->right); //连接a子树的左右结点 // connectTwoNode(b->left,b->right); //连接b子树的左右结点 // connectTwoNode(a->right,b->left); //连接相邻子树的相邻结点 // } struct Node* connect(struct Node* root) { if (root == NULL||root->left==NULL) return root; root->left->next=root->right; if(root->next&&root->right) { root->right->next=root->next->left; } root->left=connect(root->left); root->right=connect(root->right); //connectTwoNode(root->left,root->right); return root; } 第九天 广度优先搜索 / 深度优先搜索 542. 01 矩阵 思路:这题代码写不出来 参考https://leetcode.cn/problems/01-matrix/solution/54201ju-zhen-zhong-deng-cyu-yan-dfsjie-f-r8gt/ 代码: #define MIN(a,b)(a int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes){ *returnSize=matSize; int** ans=(int**)malloc(matSize*sizeof(int*)); (*returnColumnSizes)=(int*)malloc(sizeof(int*)*matSize); //给returnC0lmunSizes分配空间，因为matrixSize代表行数，而ColumnSizes数组个数就是行数 memcpy(*returnColumnSizes,matColSize,matSize*sizeof(int)); //定义ans(返回数组) for(int i=0;i ans[i]=(int*)calloc(matColSize[0],sizeof(int)); //i代表行，每行分配matrixColSize[i]这么多空间并初始化0，dp已经建立完毕 for(int j=0;j if(mat[i][j]!=0) ans[i][j]=9999; //9999是最大的数，在测试用例中体现，需要返回9999 } } //比较自己左边的上面的邻接元素，如果是0，就会因为自身和（0+1）比较而直接返回1不然则会根据对方带的数（代表了对方距离最近的0多远）和自身比较 for(int x=0;x for(int y=0;y if(x-1>=0) ans[x][y]=MIN(ans[x][y],ans[x-1][y]+1); if(y-1>=0) ans[x][y]=MIN(ans[x][y],ans[x][y-1]+1); } } //第二次遍历比较自己下面和右边的邻接元素，同理，就可以得出自己上下左右最接近0的方位并确定那个数。 for(int x=matSize-1;x>=0;x--){ for(int y=matColSize[x]-1;y>=0;y--){ if(x+1 ans[x][y]=MIN(ans[x][y],ans[x+1][y]+1); if(y+1 ans[x][y]=MIN(ans[x][y],ans[x][y+1]+1); } } return ans; } 994. 腐烂的橘子 思路:这题代码也写不出, 参考https://leetcode.cn/problems/rotting-oranges/solution/by-nirvana-10-djc3/ 代码: #define MAX 100 // 判断给定行列号是否在grid中 bool IsInArea(int row, int col, int rowSize, int colSize) { // printf("row = %d, col = %d\n", row, col); if (row >= 0 && row < rowSize && col >= 0 && col < colSize) { return true; } return false; } int orangesRotting(int** grid, int gridSize, int* gridColSize){ // 申请一个与输入矩阵等大的矩阵辅助存储最小分钟数，初始化为-1，表示未腐烂 int **dis = (int **)malloc(sizeof(int *) * gridSize); for (int i = 0; i < gridSize; i++) { dis[i] = (int *)malloc(sizeof(int) * gridColSize[i]); for (int j = 0; j < gridColSize[i]; j++) { dis[i][j] = -1; } } // 申请一个辅助队列 int **q = (int **)malloc(sizeof(int *) * MAX); for (int i = 0; i < MAX; i++) { q[i] = (int *)malloc(sizeof(int) * 2); } int front = 0; int rear = 0; // 初始腐烂的橘子入队，顺便新鲜橘子完成计数 int freshCnt = 0; for (int i = 0; i < gridSize; i++) { for (int j = 0; j < gridColSize[i]; j++) { if (grid[i][j] == 2) { q[rear][0] = i; q[rear][1] = j; rear++; // 已腐烂的橘子，腐烂时间为0 dis[i][j] = 0; } else if (grid[i][j] == 1) { // 算出新鲜橘子总数 freshCnt++; } } } // 广度优先搜索 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int ans = 0; while (front < rear) { // 逐个出队腐烂橘子，对它的上下左右方向考查 int r = q[front][0]; int c = q[front][1]; front++; for (int i = 0; i < 4; i++) { int x = r + dir[i][0]; int y = c + dir[i][1]; // 如果这个方向上下标越界，或者橘子已经腐烂，或者是空单元格，无需考查，看下一个方向 if (IsInArea(x, y, gridSize, gridColSize[0]) == false || dis[x][y] >= 0 || grid[x][y] == 0) { continue; } // 如果这个方向上是新鲜橘子，那么它将被传染腐烂 dis[x][y] = dis[r][c] + 1; // 记录在第几分钟被传染腐烂，即上一橘子被腐烂的时间+1 // 记录当前分钟数，如果此时已全部腐烂，那么它就是最短时间 ans = dis[x][y]; // 将被腐烂的橘子入队，它将是下一轮的传染源 q[rear][0] = x; q[rear][1] = y; rear++; // 剩余新鲜橘子数量减1 freshCnt--; // 如果新鲜橘子都没了，说明已全被腐烂，无需再看下去了 if (freshCnt == 0) { break; } } } // 释放辅助队列内存 for (int i = 0; i < MAX; i++) { free(q[i]); } free(q); for (int i = 0; i < gridSize; i++) { free(dis[i]); } free(dis); // 如果还剩下有新鲜橘子，表明不可能腐烂掉所有橘子，否则返回被腐烂时间 if (freshCnt > 0) { return -1; } else { return ans; } } 第十天 递归 / 回溯 21. 合并两个有序链表 思路:归并思想,每次取两个对比.排序 代码: struct ListNode* mergeTwoLists1(struct ListNode* list1, struct ListNode* list2,struct ListNode*tmp) { if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } if(list1->val { tmp=list1; tmp->next=mergeTwoLists1(list1->next,list2,tmp->next); } else { tmp=list2; tmp->next=mergeTwoLists1(list1,list2->next,tmp->next); } return tmp; } struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode*guard=(struct ListNode*)malloc(sizeof(struct ListNode)); guard->next=NULL; struct ListNode*tmp=guard; tmp->next=mergeTwoLists1(list1,list2,tmp->next); tmp=guard->next; free(guard); return tmp; } 206. 反转链表 思路:每次进行一个尾插尾删即可. 代码: struct ListNode* reverseList(struct ListNode* head){ struct ListNode*tmp=head,*tail;; if(tmp==NULL||tmp->next==NULL) { return head; } struct ListNode *guard=(struct ListNode *)malloc(sizeof(struct ListNode)); guard->next=NULL; tail=guard->next; while(tmp!=NULL) { tail=tmp; tmp=tmp->next; tail->next=guard->next; guard->next=tail; } head=guard->next; free(guard); return head; } 第十一天 递归 / 回溯 77. 组合 思路:参考官方 :https://leetcode.cn/problems/combinations/solution/zu-he-by-leetcode-solution/ 代码: int* temp; int tempSize; int** ans; int ansSize; void dfs(int cur, int n, int k) { // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp if (tempSize + (n - cur + 1) < k) { return; } // 记录合法的答案 if (tempSize == k) { int* tmp = malloc(sizeof(int) * k); for (int i = 0; i < k; i++) { tmp[i] = temp[i]; } ans[ansSize++] = tmp; return; } // 考虑选择当前位置 temp[tempSize++] = cur; dfs(cur + 1, n, k); tempSize--; // 考虑不选择当前位置 dfs(cur + 1, n, k); } int** combine(int n, int k, int* returnSize, int** returnColumnSizes) { temp = malloc(sizeof(int) * k); ans = malloc(sizeof(int*) * 10001); tempSize = ansSize = 0; dfs(1, n, k); *returnSize = ansSize; *returnColumnSizes = malloc(sizeof(int) * ansSize); for (int i = 0; i < ansSize; i++) { (*returnColumnSizes)[i] = k; } return ans; } 784. 字母大小写全排列 思路:参考代码 https://leetcode.cn/problems/letter-case-permutation/solution/c-by-eeeugene-0i5o/ 代码: /** * Note: The returned array must be malloced, assume caller calls free(). */ char ** letterCasePermutation(char * s, int* returnSize){ /*创建长度，开辟ret空间*/ int len = strlen(s); char **ret = malloc(sizeof(char *)* pow(2,len)); ret[0] = malloc(sizeof(char) * len + 1); /*将s复制进去，第一个肯定为答案*/ strcpy(ret[0],s); int i,j,k; int size = 1; for(i = 0;i < len;i++){ k = size; /*如果是字母的话*/ if(isalpha(s[i])){ /*k为行数，j用来控制移动到下行*/ for(j = 0;j < k;j++){ ret[k + j] = malloc(sizeof(char) * (len+1)); /*基于j - j+k行，每次只改变一个字符*/ strcpy(ret[j + k],ret[j]); /*如果是小写，转换大写，反之小写*/ ret[k + j][i] = (isupper(s[i]) != 0) ? s[i] + 32 : s[i] - 32; size++; } } } *returnSize = size; return ret; } 46. 全排列 思路:参考代码:https://leetcode.cn/problems/permutations/solution/quan-pai-lie-cyu-yan-xiang-jie-chao-ji-x-pywy/ 代码: void swap(int * nums,int indexA,int indexB) { int temp = nums[indexA]; nums[indexA]= nums[indexB]; nums[indexB]= temp; } void prem(int* nums, int numsSize, int* returnSize, int** returnColumnSizes,int** returnNums,int offset) { if(offset == numsSize) { //遍历到末尾了 //申请returnNums returnNums[*returnSize] = (int *)malloc(sizeof(int ) * numsSize); //拷贝内容到returnNums memcpy(returnNums[*returnSize],nums,sizeof(int) * numsSize ); //记录当前拷贝内容的长度 (*returnColumnSizes)[*returnSize] = numsSize; *returnSize = *returnSize + 1; } else { //回溯算法的核心 int i; for(i = offset; i < numsSize; i++) { swap(nums,i,offset);//i 和 offset 交换 prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,offset+1); swap(nums,i,offset);//i 和 offset 交换 } } } int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { //不重复的数字的全排序 //组合次数为 n！= n *( n - 1) *( n - 2) ...... 2 * 1 //这样的方法适合回溯的方法 //取值范围1 <= nums.length <= 6 = 6 * 5 * 4 * 3 *2 * 1 = 720中可能 int **returnNums = (int **)malloc(sizeof(int *) * 721); *returnColumnSizes= (int *)malloc(sizeof(int ) * 721); *returnSize = 0; prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,0); return returnNums; } 第 十二 天 动态规划 70. 爬楼梯 思路:爬一节楼梯方法数1 爬两节楼梯方法数2,爬3=爬1+爬2, 爬4=爬2+爬3;以此类推 代码: int climbStairs(int n){ if(n==1) { return 1; } if(n==2) { return 2; } int a=1; int b=2; int sum=0; while(n>2) { sum=a+b; a=b; b=sum; n--; } return sum; } 120. 三角形最小路径和 思路:最小路径和,即每次选最小的值即可 举例: 每次选两个数中的最小值,加到上一行,依次进行,最顶层的数一定是最小数. 代码: int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){ for(int i=0;i { triangleColSize[i]=i+1; } int *answer=(int *)malloc(sizeof(int)*triangleSize); for(int i=0;i { answer[i]=triangle[triangleSize-1][i]; } for(int i=triangleSize-1-1;i>=0;i--) { for(int j=0;j { answer[j]=answer[j] } } return answer[0]; } 第 十三天 位运算 231. 2 的幂 思路:如果是2的次方数,则2进制序列中一定只有一个1,判断1的个数即可. 代码: bool isPowerOfTwo(int n){ if(n<=0) { return false; } int count=0; while(n) { n=n&(n-1); count++; } if(count==1) { return true; } return false; } 191. 位1的个数 思路:特殊解法: n&(n-1)的次数即为1的个数. 代码: int hammingWeight(uint32_t n) { int count=0; while(n) { n=n&(n-1); count++; } return count; } 第 十四天 位运算 190. 颠倒二进制位 思路:分治思想,一次分为两部分进行倒置. 代码: const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101 const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011 const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111 const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111 uint32_t reverseBits(uint32_t n) { n = n >> 1 & M1 | (n & M1) << 1; n = n >> 2 & M2 | (n & M2) << 2; n = n >> 4 & M4 | (n & M4) << 4; n = n >> 8 & M8 | (n & M8) << 8; return n >> 16 | n << 16; } 136. 只出现一次的数字 思路:两个相同的按位异或=0; 代码: int singleNumber(int* nums, int numsSize){ int a=nums[0]; for(int j=1;j { a=a^nums[j]; } return a; } 95041221e6.png) 思路:特殊解法: n&(n-1)的次数即为1的个数. 代码: int hammingWeight(uint32_t n) { int count=0; while(n) { n=n&(n-1); count++; } return count; } 第 十四天 位运算 190. 颠倒二进制位 思路:分治思想,一次分为两部分进行倒置. 代码: const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101 const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011 const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111 const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111 uint32_t reverseBits(uint32_t n) { n = n >> 1 & M1 | (n & M1) << 1; n = n >> 2 & M2 | (n & M2) << 2; n = n >> 4 & M4 | (n & M4) << 4; n = n >> 8 & M8 | (n & M8) << 8; return n >> 16 | n << 16; } 136. 只出现一次的数字 思路:两个相同的按位异或=0; 代码: int singleNumber(int* nums, int numsSize){ int a=nums[0]; for(int j=1;j { a=a^nums[j]; } return a; } 第九天,第十天的代码没有写出来,等下一次补一篇博客 思路与代码. 欢迎各位博主多多点评,希望各位大佬提出给优秀的建议或思路.
发表评论