C语言leetcode刷题笔记1

第1题：136.只出现一次的数字
- 两次遍历（O(numsSize^2)）
- 位运算
第2题：202.快乐数
- 快慢指针
- 记录历史数据
第3题：53.最大子数组和
- 暴力求解（超时）
- 动态规划
- 分治

第1题：136.只出现一次的数字

一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例：
输入：nums = [2,2,1]
输出：1

两次遍历（O(numsSize^2)）

记录次数，输出只有一次的元素


int singleNumber(int* nums, int numsSize) {
    for(int i=0;i<numsSize;i++)
    {
        int count=0;
        for(int j=0;j<numsSize;j++)
        {
            if(nums[i]==nums[j])count++;

        }
        if(count==1)return nums[i];//只有一次的输出
    }
    return -1;
    
}

位运算

异或运算，二进制数相同为0，不同为1

int singleNumber(int* nums, int numsSize) {
    int a=nums[0];
    for(int i=1;i<numsSize;i++)
    {
        a^=nums[i];
    }
    return a;    
}

第2题：202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

快慢指针

如果有出现的历史值，就会有环形结构。当慢指针追上快指针就代表有环形

int Pinfang(int x)
{
    int tem=x,ge,sum=0;
    while(tem!=0)
    {
        ge=tem%10;
        sum+=(ge*ge);
        tem/=10;

    }
    return sum;
}
bool isHappy(int n) {
    int t=n;
    int a=Pinfang(n),b=Pinfang(a);
    while(b!=1)
    {
        if(a==b)return false;
        a=Pinfang(a);
        b=Pinfang(b);b=Pinfang(b);
        
    }
    return true;
    
}

记录历史数据

int Pinfang(int x)
{
    int tem=x,ge,sum=0;
    while(tem!=0)
    {
        ge=tem%10;
        sum+=(ge*ge);
        tem/=10;
    }
    return sum;
}
int history[10001];
bool contain(int * his,int len,int val)
{
    for(int i=0;i<len;i++)
    {
        if(val==his[i])return true;
    }
    return false;
}
bool isHappy(int n) {
    if(n==1)return true;
    int t=n;
    int count=0;
    history[count++]=n;
    while(!contain(history,count,Pinfang(t)))
    {
        if(Pinfang(t)==1)return true;
        t=Pinfang(t);
        history[count++]=t;
        count++;
    }      
    return false;
    
}

第3题：53.最大子数组和

一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

暴力求解（超时）

计算所有的和，返回历史最大值

int maxSubArray(int* nums, int numsSize) {
    //起点 终点，三层for优化为2层
    int sum=0;
    int max=nums[0];
    for(int i=0;i<numsSize;i++)
    {
        sum=0;
        for(int j=i;j<numsSize;j++)
        {
            sum+=nums[j];
            if(max<sum)max=sum;

        }
    }
    return max;
    
}

在这里插入图片描述

动态规划

规律：对于任意长度为n的数组，最大连续子数组取前n-1的最大连续子数组、nums[n-1]和前n项之和的最大值
思路：每次记录最大值，留下历史最大值

int maxSubArray(int* nums, int numsSize) {
    int pre = 0, maxAns = nums[0];
    for (int i = 0; i < numsSize; i++) {
        pre = fmax(pre + nums[i], nums[i]);
        maxAns = fmax(maxAns, pre);
    }
    return maxAns;
}

分治

int fc(int* nums, int l,int r,int mid)//最大和正好经过mid
{
    
    int m1=nums[mid],m2=nums[mid+1],sum=0;
    for(int i= mid;i>=l;i--)//l~mid 
    {
        sum+=nums[i];
        m1=sum>m1?sum:m1;
    }
    sum=0;
    for(int i= mid+1;i<=r;i++)// mid+1~r
    {
        sum+=nums[i];
        m2=sum>m2?sum:m2;
    }
    return m1+m2;

}
//在l和r之间（包括l,r）的最大连续子数组
int f(int* nums, int l,int r)
{
    if(l==r)return nums[l];
    else
    {
        int mid=(l+r)/2;
        int le=f(nums,l,mid);//最大连续子数组在左边
        int ri=f(nums,mid+1,r);//最大连续子数组在右边
        int max=le>ri?le:ri;
        return max>fc(nums,l,r,mid)?max:fc(nums,l,r,mid);
    }

}
int maxSubArray(int* nums, int numsSize) {
    return f(nums, 0,numsSize-1);
    
}