数组 + 数学

day1

1523. 在区间范围内统计奇数数目 简单

法一
int countOdds(int low, int high){
    int n=0;
    for(int i=low;i<=high;i++)
        if(i%2)n++;
    return n;
}
时间复杂度O(n)
空间复杂度O(1)
法二
int countOdds(int low, int high){
    if(low%2==0)low++;
    if(high%2==0)high--;
    return (high-low)/2+1;
}
时间复杂度O(1)
空间复杂度O(1)

1491. 去掉最低工资和最高工资后的工资平均值 简单

int max(int a,int b)
{
    return a>b?a:b;
}
int min(int a,int b)
{
    return a<b?a:b;
}
double average(int* salary, int salarySize) {
    int maxv=-1;
    int minv=0x3f3f3f3f;
    int sum=0;
    for(int i=0;i<salarySize;i++)
    {
        maxv=max(salary[i],maxv);
        minv=min(salary[i],minv);
        sum+=salary[i];
    }
    return (sum-maxv-minv)*1.0/(salarySize-2);
}
时间复杂度O(n)
空间复杂度O(1)

day2

1281. 整数的各位积和之差 简单

int subtractProductAndSum(int n){
    int a=1,b=0;
    while(n)a=a*(n%10),b+=n%10,n/=10;
    return a-b;
}
时间复杂度O(logn)
空间复杂度O(1)

1822. 数组元素积的符号 简单

int arraySign(int* nums, int numsSize) {
    int n=1;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]>0)n*=1;
        else if(nums[i]<0)n*=-1;
        else n=0;
    }
    return n;
}
时间复杂度O(n)
空间复杂度O(1)

day3

896. 单调数列 简单

bool isMonotonic(int* nums, int numsSize) {
    bool f=false;
    bool s=false;
    for(int i=1;i<numsSize;i++)
    {
        if(nums[i]==nums[i-1])continue;
        if(!s)f=nums[i]>nums[i-1],s=true;
        if(f!=nums[i]>nums[i-1])return false;
    }
    return true;
}
时间复杂度O(n)
空间复杂度O(1)

121. 买卖股票的最佳时机 简单

int dp[100001][2];
int min(int a,int b)
{
    return a<b?a:b;
}
int max(int a,int b)
{
    return a>b?a:b;
}
int maxProfit(int* prices, int pricesSize) {
    dp[0][0]=-prices[0];
    for(int i=1;i<pricesSize;i++)
    {
        dp[i][0]=max(dp[i-1][0],-prices[i]);
        dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);
    }
    return dp[pricesSize-1][1];
}
时间复杂度O(n)
空间复杂度O(n)

二维数组 + 数学

day4

1672. 最富有客户的资产总量 简单

int max(int a,int b)
{
    return a>b?a:b;
}
int maximumWealth(int** accounts, int accountsSize, int* accountsColSize) {
    int maxv=0;
    int s=0;
    for(int i=0;i<accountsSize;i++)
    {
        s=0;
        for(int j=0;j<accountsColSize[0];j++)
            s+=accounts[i][j];
        maxv=max(s,maxv);
    }
    return maxv;
}
时间复杂度O(n^2)
空间复杂度O(1)

1572. 矩阵对角线元素的和 简单

int diagonalSum(int** mat, int matSize, int* matColSize){
    int s=0;
    for(int i=0;i<matSize;i++)
        s+=mat[i][i]+mat[i][matSize-i-1];
    int number=mat[matSize/2][matSize/2];
    if(matSize%2==0)number=0;
    return s-number;
}
时间复杂度O(n)
空间复杂度O(1)

数组 + 计数法或散列表

day5

169. 多数元素 简单 2013

int majorityElement(int* nums, int numsSize) {
    int a=nums[0],b=0;
    for(int i=0;i<numsSize;i++)
    {
        if(a==nums[i])b++;
        else b--;
        if(b==-1)a=nums[i],b=1;
    }
    return a;
}
时间复杂度O(n)
空间复杂度O(1)

41. 缺失的第一个正数 困难 2019