【每日刷题】Day75

【每日刷题】Day75

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 1833. 雪糕的最大数量 - 力扣（LeetCode）

2. 面试题 17.14. 最小K个数 - 力扣（LeetCode）

3. 面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

1. 1833. 雪糕的最大数量 - 力扣（LeetCode）

//思路：记数排序。

//记数排序

void CountSort(int* arr,int size)

{

    int* hash = (int*)calloc(100001,sizeof(int));

    int max = 0;

    int count = 0;

    for(int i = 0;i<size;i++)

    {

        hash[arr[i]]+=1;

        if(arr[i]>max)

            max = arr[i];

    }

    for(int i = 1;i<=max;i++)

    {

        while(hash[i])

        {

            arr[count++] = i;

            hash[i]--;

        }

    }

}

int maxIceCream(int* costs, int costsSize, int coins)

{

    int ans = 0;

    CountSort(costs,costsSize);

    for(int i = 0;i<costsSize;i++)

    {

        if(coins-costs[i]>=0)

        {

            coins-=costs[i];

            ans++;

        }

        else

            break;

    }

    return ans;

}

2. 面试题 17.14. 最小K个数 - 力扣（LeetCode）

//思路：TopK问题。采用堆排序将所求的K个数排入堆底。

//交换

void Swap(int* x, int* y)

{

    int tmp = *x;

    *x = *y;

    *y = tmp;

}

//向下调整

void AdjustDown(int* arr, int parents, int size)

{

    int child = parents * 2 + 1;

    while (child < size)

    {

        if (child + 1 < size && arr[child + 1] < arr[child])

            child++;

        if (arr[child] < arr[parents])

            Swap(&arr[child], &arr[parents]);

        else

            break;

        parents = child;

        child = parents * 2 + 1;

    }

}

void TopK(int* arr, int size, int k)

{

    for (int i = (size - 2) / 2; i >= 0; i--)

    {

        AdjustDown(arr, i, size);

    }

    while (k)//循环K次，每次将最小的数排入堆底

    {

        Swap(&arr[0], &arr[size - 1]);

        k--;

        size--;

        AdjustDown(arr, 0, size);

    }

}

int* smallestK(int* arr, int arrSize, int k, int* returnSize)

{

    TopK(arr,arrSize,k);

    int* ans = (int*)malloc(sizeof(int)*100000);

    int count = 0;

    for(int i = arrSize-1;i>=arrSize-k;i--)

    {

        ans[count++] = arr[i];//拿取堆底的K个数

    }

    *returnSize = count;

    return ans;

}

3. 面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

//思路①：哈希

bool isUnique(char* astr)

{

    int hash[27] = {0};

    for(int i = 0;i<strlen(astr);i++)

    {

        hash[astr[i]-'a']+=1;

    }

    for(int i = 0;i<27;i++)

    {

        if(hash[i]>1)

            return false;

    }

    return true;

}

//思路②：排序+一次遍历。选用插入排序，不需要开辟额外的空间，效率也不错。

//插入排序

void Insert(char* arr)

{

    for(int i = 0;i<strlen(arr)-1;i++)

    {

        int end = i+1;

        char tmp = arr[end];

        while(end-1>=0)

        {

            if(arr[end-1]>tmp)

                arr[end] = arr[end-1];

            else

                break;

            end--;

        }

        arr[end] = tmp;

    }

}

 

bool isUnique(char* astr)

{

    if(!strlen(astr))

        return true;

    Insert(astr);

    for(int i = 0;i<strlen(astr)-1;i++)

    {

        if(astr[i]==astr[i+1])

            return false;

    }

    return true;

}