目录

第1题：单词规律

第2题：找不同

第3题：在排序数组中查找元素的第一个和最后一个位置

第4题：使用最小花费爬楼梯

第5题：寻找峰值

第6题：字符串中的第一个唯一字符

第7题：两个数组的交集 II

第8题：分发饼干

第9题：旋转图像

第10题：矩阵置零

力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。

第1题：单词规律

试题要求如下：

回答（C语言）：

bool wordPattern(char * pattern, char * str){
    char **hash = (char **)malloc(26 * sizeof(char*));

    for (int i = 0; i < 26; ++i)
    {
        hash[i] = (char*)malloc(64 * sizeof(char));
        memset(hash[i], 0, 64 * sizeof(char));
    }
    
    int len = strlen(pattern);

    for (int i = 0; i < len; ++i)
    {
        char *p = str;
        while (p && *p != 0 && *p != ' ') ++p;
        if (' ' == *p) *p++ = 0;
        if (strlen(str) == 0)
            return false;
        int pos = pattern[i] - 'a';
        if (strlen(hash[pos]) == 0)
        {
            for (int j = 0; j < 26; ++j)
            {
                if (j != pos && strlen(hash[j]) > 0)
                {
                    if (strcmp(hash[j], str) == 0)
                        return false;
                }
            }
            strcpy(hash[pos], str);
        }
        else
        {
            if (strcmp(hash[pos], str) != 0)
                return false;
        }
        str = p;        
    }

    if (strlen(str) > 0)
        return false;
        
    return true;
}

运行效率如下所示：

第2题：找不同

试题要求如下：

解题思路：

回答（C语言）：

char findTheDifference(char* s, char* t) {
    int n = strlen(s), m = strlen(t);
    int as = 0, at = 0;

    for (int i = 0; i < n; i++) {
        as += s[i];
    }
    for (int i = 0; i < m; i++) {
        at += t[i];
    }
    
    return at - as;
}

运行效率如下所示：

第3题：在排序数组中查找元素的第一个和最后一个位置

试题要求如下：

回答（C语言）：

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*2);
    ret[0]=-1;
    ret[1]=-1;
    *returnSize=2;
    
    if(numsSize==0||target<nums[0]||target>nums[numsSize-1]){        
        return ret;
    }
    int left=0, right=numsSize-1, mid=0, head=0, tail=0;
    while(left<=right){
        mid=(left+right)/2;
        if(nums[mid]>=target){
            right=mid-1;
        }
        else{
            left=mid+1;         //mid存的就是第一个>=target的那个值的索引
        }
    }

    head=left;
    left=0, right=numsSize-1, mid=0;

    while(left<=right){
        mid=(left+right)/2;
        if(nums[mid]<=target){
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    tail=right;
    if(nums[head]==target){     //存在这个数
        ret[0]=head;
        ret[1]=tail;
    }

    return ret;
}

运行效率如下所示：

第4题：使用最小花费爬楼梯

试题要求如下：

回答（C语言）：

int minCostClimbingStairs(int* cost, int costSize) {
    int prev = 0, curr = 0;

    for (int i = 2; i <= costSize; i++) {
        int next = fmin(curr + cost[i - 1], prev + cost[i - 2]);
        prev = curr;
        curr = next;
    }
    
    return curr;
}

运行效率如下所示：

第5题：寻找峰值

试题要求如下：

回答（C语言）：

int findPeakElement(int *nums, int numsSize)
{
    if (!nums || numsSize < 1) {
        return 0;
    }
    if (numsSize == 1) {
        return 0;
    }
    if (nums[0] > nums[1]) {
        return 0;
    }
    if (nums[numsSize - 1] > nums[numsSize - 2]) {
        return numsSize - 1;
    }
    for (int i = 1; i < numsSize - 1; i++) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            return i;
        }
    }
    
    return -1;
}

运行效率如下所示：

第6题：字符串中的第一个唯一字符

试题要求如下：

解题思路：

两次遍历，一次记录字符出现次数，一次找出第一个出现一次的索引。

回答（C语言）：

int firstUniqChar(char * s){
    if(s == NULL || strlen(s) == 0) return -1;
    int len = strlen(s);
    if(len == 1) return 0;
    int recode[26] = {0};

    //记录字符出现次数
    for(int i=0;i<len;i++){
        recode[s[i]-'a']++;
    }

    //找出第一个出现一次的索引
    for(int i=0;i<len;i++){
        if(recode[s[i]-'a'] == 1){
            return i;
        }
    }
    
    return -1;
}

运行效率如下所示：

第7题：两个数组的交集 II

试题要求如下：

解题思路：

回答（C语言）：

运行效率如下所示：

第8题：分发饼干

试题要求如下：

回答（C语言）：

int compare(const void * a, const void * b)
{
    return ( *(int*)b - *(int*)a );
}

int findContentChildren(int* g, int gSize, int* s, int sSize){
    int count=0;

    qsort (g, gSize, sizeof(int), compare);
    qsort (s, sSize, sizeof(int), compare);
    
    for(int i = 0, j = 0; i < gSize && j < sSize; i++, j++)
    {
        if(s[j] >= g[i])
            count++;
        else
            j--;
    }

    return count;
}

运行效率如下所示：

第9题：旋转图像

试题要求如下：

回答（C语言）：

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    int matrix_new[matrixSize][matrixSize];

    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixSize; j++) {
            matrix_new[i][j] = matrix[i][j];
        }
    }
    
    for (int i = 0; i < matrixSize; ++i) {
        for (int j = 0; j < matrixSize; ++j) {
            matrix[j][matrixSize - i - 1] = matrix_new[i][j];
        }
    }
}

运行效率如下所示：

第10题：矩阵置零

试题要求如下：

回答（C语言）：

void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
    int i = 0;
    int j = 0;
    int iRow = matrixSize;
    int iCol = matrixColSize[0];
    int row[iRow];
    int col[iCol];

    memset(row, 0x00, sizeof(int) * iRow);
    memset(col, 0x00, sizeof(int) * iCol);

    //1,遍历一遍，找出所有为0的元素，并在行，列数组中标记
    for (i = 0; i < iRow; i++)
    {
        for (j = 0; j < iCol; j++)
        {
            if (matrix[i][j] == 0)
            {
                row[i] = 1;
                col[j] = 1;
            }
        }
    }

    //2,遍历数组，按照行，列中的结果修改矩阵
    for (i = 0; i < iRow; i++)
    {
        for (j = 0; j < iCol; j++)
        {
            if (row[i] == 1)
            {
                matrix[i][j] = 0;
            }
            if (col[j] == 1)
            {
                matrix[i][j] = 0;
            }
        }
    }
}

运行效率如下所示：