文章目录
leetcode 14天算法入门 C语言实现
第一天 二分查找
二分法讲解 : 把答案所在的区间逐渐缩小，直到区间内只有答案。
图解:
思路:二分思想,不用解释直接上手
代码:
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]<target)
{
left=mid+1;
}
else
{
right=mid-1;
}
}
return -1;
}
思路:还是基本的二分思想,当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<right)
{
int mid=(right-left)/2+left;
bool tmp=isBadVersion(mid);
if(!tmp)
{
left=mid+1;
}
else
{
right=mid;
}
}
return left;
}
思路:*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;
}
第二天 双指针
双指针法讲解:双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
思路: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;
}
思路: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<right)
{
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);
}
第三天 双指针
思路:注释部分是我第一次写的,使用的两个指针来记录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<numsSize&&zeroloc<numsSize)
// {
// while(zeroloc<numsSize&&nums[zeroloc]!=0)
// {
// zeroloc++;
// }
// if(zeroloc==numsSize)
// {
// break;
// }
// //numloc=zeroloc+1;
// while(numloc<numsSize&&nums[numloc]==0)
// {
// 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++;
}
}
思路:左指针,右指针,大于目标数,右指针左移.小于目标数,左指针右移.
代码:
/**
* 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]<target)
{
left++;
}
else
{
right--;
}
}
return answer;
}
第四天 双指针
思路:就左指针与右指针交换即可
代码:
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<right)
{
swap(s + left, s + right);
left++;
right--;
}
}
思路:难点就在于寻找每一个单词
代码:
void swap(char *a,char *b)
{
char tmp=*a;
*a=*b;
*b=tmp;
}
void revers(char *arr,int begin,int end)
{
while(begin<end)
{
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;
}
第五天 双指针
思路:一个快指针一次走两步(最后一次可能走一步,因为两个中间节点的第二个),一个慢指针一次走一步,当快指针的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;
}
思路:找到该节点,删除即可.
代码:
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;
}
第六天 滑动窗口
思路:采用滑动窗口,判断窗口中的数量是否与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<n;i++)
{
s1_arr[*(s1+i)-'a']++;
}
for(int i=0;i<n;i++)
{
s2_arr[*(s2+i)-'a']++;
}
if(check(s1_arr,s2_arr))
{
return true;
}
for(int i=n;i<m;i++)
{
s2_arr[*(s2+i)-'a']++;
s2_arr[*(s2+i-n)-'a']--;
if(check(s1_arr,s2_arr))
{
return true;
}
}
return false;
}
思路:计算窗口的最大值即可
代码:
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<len;i++)
while(right<len)
{
if(left<right)
{
//判断是否重复
same=0;
for(j=left;j<right;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;
}
第七天 广度优先搜索 / 深度优先搜索
思路:先修改最初的起点,再在修改起点上下左右的点,再然后再把四个点都作为起点,依次进行.
代码:
void dfs(int **image,int color,int curcolor,int row,int col,int sr,int sc)
{
if(sr<row&&sr>=0&&sc<col&&sc>=0)
{
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<row;i++)
{
(*returnColumnSizes)[i]=col;
}
int curcolor=image[sr][sc];
if(curcolor!=color)
{
dfs(image,color,curcolor,row,col,sr,sc);
}
return image;
}
思路:深度递归即可,每次遍历到1就修改为0.选出最大值即可
代码:
int dfs(int **grid,int gr,int gc,int row, int col)
{
if(gr<row&&gr>=0&&gc<col&&gc>=0)
{
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<gridSize;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;
}
第八天 广度优先搜索 / 深度优先搜索
思路:遍历每一个节点即可.
代码:
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;
}
思路:根据图可以理解,最难的部分是判断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;
}
第九天 广度优先搜索 / 深度优先搜索
思路:这题代码写不出来 参考https://leetcode.cn/problems/01-matrix/solution/54201ju-zhen-zhong-deng-cyu-yan-dfsjie-f-r8gt/
代码:
#define MIN(a,b)(a<b?a:b)
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<matSize;i++){
ans[i]=(int*)calloc(matColSize[0],sizeof(int));
//i代表行，每行分配matrixColSize[i]这么多空间并初始化0，dp已经建立完毕
for(int j=0;j<matColSize[i];j++){
if(mat[i][j]!=0)
ans[i][j]=9999;
//9999是最大的数，在测试用例中体现，需要返回9999
}
}
//比较自己左边的上面的邻接元素，如果是0，就会因为自身和（0+1）比较而直接返回1不然则会根据对方带的数（代表了对方距离最近的0多远）和自身比较
for(int x=0;x<matSize;x++){
for(int y=0;y<matColSize[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<matSize)
ans[x][y]=MIN(ans[x][y],ans[x+1][y]+1);
if(y+1<matColSize[x])
ans[x][y]=MIN(ans[x][y],ans[x][y+1]+1);
}
}
return ans;
}
思路:这题代码也写不出, 参考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;
}
}
第十天 递归 / 回溯
思路:归并思想,每次取两个对比.排序
代码:
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<list2->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;
}
思路:每次进行一个尾插尾删即可.
代码:
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;
}
第十一天 递归 / 回溯
思路:参考官方 :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;
}
思路:参考代码 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;
}
思路:参考代码: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;
}
第 十二 天 动态规划
思路:爬一节楼梯方法数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;
}
思路:最小路径和,即每次选最小的值即可
举例:
每次选两个数中的最小值,加到上一行,依次进行,最顶层的数一定是最小数.
代码:
int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){
for(int i=0;i<triangleSize;i++)
{
triangleColSize[i]=i+1;
}
int *answer=(int *)malloc(sizeof(int)*triangleSize);
for(int i=0;i<triangleSize;i++)
{
answer[i]=triangle[triangleSize-1][i];
}
for(int i=triangleSize-1-1;i>=0;i--)
{
for(int j=0;j<triangleColSize[i];j++)
{
answer[j]=answer[j]<answer[j+1]?triangle[i][j]+answer[j]:triangle[i][j]+answer[j+1];
}
}
return answer[0];
}
第 十三天 位运算
思路:如果是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;
}
思路:特殊解法: n&(n-1)的次数即为1的个数.
代码:
int hammingWeight(uint32_t n) {
int count=0;
while(n)
{
n=n&(n-1);
count++;
}
return count;
}
第 十四天 位运算
思路:分治思想,一次分为两部分进行倒置.
代码:
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;
}
思路:两个相同的按位异或=0;
代码:
int singleNumber(int* nums, int numsSize){
int a=nums[0];
for(int j=1;j<numsSize;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;
}
第 十四天 位运算
思路:分治思想,一次分为两部分进行倒置.
代码:
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;
}
思路:两个相同的按位异或=0;
代码:
int singleNumber(int* nums, int numsSize){
int a=nums[0];
for(int j=1;j<numsSize;j++)
{
a=a^nums[j];
}
return a;
}
第九天,第十天的代码没有写出来,等下一次补一篇博客 思路与代码. 欢迎各位博主多多点评,希望各位大佬提出给优秀的建议或思路.