力扣(LeetCode)刷题，简单题(第15期)

第1题：将整数转换为两个无零整数的和

试题要求如下：

解答思路：

一对一对筛选，若一组数值某个数存在含0组成，则跳过该组。

回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getNoZeroIntegers(int n, int* returnSize){
    int i = 1,j = n-1;
    int temp = 0;
    int* data_buf = (int*)malloc((2)*sizeof(int));
    
    while(i<j){
        temp = i;
        while(temp % 10 != 0){
            temp /= 10;
        }
        if(temp != 0){
            i++;
            j--;
            continue;
        }
        
        temp = j;
        while(temp % 10 != 0){
            temp /= 10;
        }
        if(temp != 0){
            i++;
            j--;
            continue;
        } 

        break;      
    }

    data_buf[0] = i;
    data_buf[1] = j;

    *returnSize = 2;
    return data_buf;
}

运行效率如下所示：

第2题：一周中的第几天

试题要求如下：

解答思路：

1、明确起点1971.1.1 - "Friday", 用最小值避免符号运算;

2、计算从1971.1.1到(day, month, year)的天数, 需要注意中间年份会有闰年, 另外当前年份需要单独运算;

3、根据天数差值, 对7(一周7天)进行求余, 并且需要考虑起点是"Friday"(周五)的偏移。

回答（C语言）：

char * dayOfTheWeek(int day, int month, int year){
    const char *s[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

    if(year < 1971 || year > 2100) return NULL;

    int daysOfMonth[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    int sum = 0;
    for(int i = 1971; i < year; i ++)
    {
        if(0 == i % 400 || (0 != i % 100 && 0 == i % 4))
        {
            sum += 366;
        }
        else
        {
            sum += 365;
        }
    }

    if(0 == year % 400 || (0 != year % 100 && 0 == year % 4))
    {
        daysOfMonth[1] = 29;
    }

    for(int i = 0; i < month - 1; i ++)
    {
        sum += daysOfMonth[i];
    }

    sum += day - 1;

    return s[(sum + 5) % 7];
}

运行效率如下所示：

第3题：把二叉搜索树转换为累加树

试题要求如下：

解答思路：

在递归方法中，我们维护一些递归调用过程中可以访问和修改的全局变量。首先我们判断当前访问的节点是否存在，如果存在就递归右子树，递归回来的时候更新总和和当前点的值，然后递归左子树。如果我们分别正确地递归 root.right 和 root.left ，那么我们就能正确地用大于某个节点的值去更新此节点，然后才遍历比它小的值。

回答（C语言）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
static void dfs(struct TreeNode* psRoot, int* pSum)
{
    if (NULL == psRoot)
    {
        return;
    }

    dfs(psRoot->right, pSum);

    *pSum += psRoot->val;
    psRoot->val = *pSum;

    dfs(psRoot->left, pSum);
}

struct TreeNode* convertBST(struct TreeNode* root){
    int sum = 0;
    dfs(root, &sum);
    return root;
}

运行效率如下所示：

第4题：连续字符

试题要求如下：

回答（C语言）：

int maxPower(char * s){
    int i,cou = 1,num = 0,len = strlen(s)-1;
    char temp = s[0];

    for(i = 1;i <= len;i++){
        if(temp == s[i]){
            cou++;
            if(cou > num){
                num = cou;
            }
        }
        else{
            cou = 1;
        }

        temp = s[i];
    }

    if(num == 0){
        num = 1;
    }

    return num;
}

运行效率如下所示：

第5题：拿硬币

试题要求如下：

回答（C语言）：

int minCount(int* coins, int coinsSize){
    int cou = 0;
    int temp = 0;

    for(int i = 0;i < coinsSize;i++)
    {
        temp = coins[i];
        while(temp > 0){
            cou++;
            temp -= 2;
        }
    }

    return cou;
}

运行效率如下所示：

第6题：删除中间节点

试题要求如下：

解答思路：

将node->next指向的地址传给node，然后释放掉多余节点。

注意给出的形参不是头节点。

回答（C语言）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    struct ListNode *t=node->next;
    *node=*t;
    free(t);
}

运行效率如下所示：

第7题：猜数字

试题要求如下：

解答思路：

第一次在力扣做这么简单的题，判断每一位元素是否相等。

回答（C语言）：

int game(int* guess, int guessSize, int* answer, int answerSize){
    int cou = 0;
    
    for(int i = 0;i < guessSize;i++){
        if(guess[i] == answer[i]){
            cou++;
        }
    }

    return cou;
}

运行效率如下所示：

第8题：整数的各位积和之差

试题要求如下：

回答（C语言）：

int subtractProductAndSum(int n){
    int product = 1,sum = 0;

    for(int i = 0,num = n;num > 0;i++){
        product *= num%10;
        sum += num%10;
        num /= 10;
    }

    return product-sum;
}

运行效率如下所示：

第9题：一维数组的动态和

试题要求如下：

解答思路：

求取前缀和，直接对原数组求取，不用额外分配存储空间。

回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *runningSum(int *nums, int numsSize, int *returnSize)
{
    for(int i = 1;i < numsSize;i++){
        nums[i] = nums[i] + nums[i-1];
    }

    *returnSize = numsSize;
    return nums;
}

运行效率如下所示：

第10题：统计位数为偶数的数字

试题要求如下：

回答（C语言）：

int findNumbers(int* nums, int numsSize){
    int temp = 0,cou = 0,data = 0;

    for(int i = 0;i < numsSize;i++){
        temp = nums[i];
        while(temp > 0)
        {
            cou++;
            temp /= 10;
        }

        if(cou%2 == 0){
            data++;
        }

        cou = 0;
    }

    return data;
}

运行效率如下所示：