练习

这篇文章最后更新的时间在六个月之前,文章所叙述的内容可能已经失效,请谨慎参考!

leetcode

简单

67. 二进制求和

给定两个二进制字符串,返回他们的和(用二进制表示)。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

C

// c 反转字符串
void reverse(char* s, int len)
{
    // 交换 ...
    int i = 0;
    char c;
    while (i <= len / 2 - 1)
    {
        c = *(s + i);
        *(s + i) = *(s + len - 1 - i);
        *(s + len - 1 - i) = c;
        i++;
    }
}
char * addBinary(char * a, char * b){
    int al = strlen(a);
    int bl = strlen(b);
    int l;
    l = al > bl ? al : bl;
    l = l + 2; // 进一位 字符串结尾的 \0
    reverse(a, al);
    reverse(b, bl);

    char* ret;
    ret = (char*)malloc(l*sizeof(char));
    memset(ret, '0', l*sizeof(char));

    char temp, at, bt;
    temp = '0';
    for (int i = 0; i < l; i++) {
        at = a[i];
        if (i >= al || a[i] == '\0') {
            at = '0';
        }
        bt = b[i];
        if (i >= bl || b[i] == '\0') {
            bt = '0';
        }
        if (temp == '1' && at == '1' && bt == '1') {
            temp = '1';
            ret[i] = '1';
        } else if (temp == '0' && at == '1' && bt == '1') {
            temp = '1';
            ret[i] = '0';
        } else if (temp == '1' && at == '1' && bt == '0') {
            temp = '1';
            ret[i] = '0';
        } else if (temp == '0' && at == '1' && bt == '0') {
            temp = '0';
            ret[i] = '1';
        } else if (temp == '1' && at == '0' && bt == '1') {
            temp = '1';
            ret[i] = '0';
        } else if (temp == '0' && at == '0' && bt == '1') {
            temp = '0';
            ret[i] = '1';
        } else if (temp == '1' && at == '0' && bt == '0') {
            temp = '0';
            ret[i] = '1';
        } else if (temp == '0' && at == '0' && bt == '0') {
            temp = '0';
            ret[i] = '0';
        }
    }
    if (ret[l-2] == '0') {
        l = l - 1;
    }
    ret[l-1]='\0';
    reverse(ret, l - 1);
    return ret;
}

PHP

class Solution {
    /**
     * @param String $a
     * @param String $b
     * @return String
     */
    function addBinary($a, $b) {
        $a = strrev($a);
        $b = strrev($b);
        $temp = '0';
        $al = strlen($a);
        $bl = strlen($b);
        $len = max($al, $bl) + 1;
        $ret = [];
        for ($i = 0; $i < $len; $i++) {
            if ($i >= $al) {
                $at = '0';
            } else {
                $at = $a[$i];
            }
            if ($i >= $bl) {
                $bt = '0';
            } else {
                $bt = $b[$i];
            }
            if ($temp == '1' && $at == '1' && $bt == '1') {
                $temp = '1';
                $ret[$i] = '1';
            } else if ($temp == '0' && $at == '1' && $bt == '1') {
                $temp = '1';
                $ret[$i] = '0';
            } else if ($temp == '1' && $at == '1' && $bt == '0') {
                $temp = '1';
                $ret[$i] = '0';
            } else if ($temp == '0' && $at == '1' && $bt == '0') {
                $temp = '0';
                $ret[$i] = '1';
            } else if ($temp == '1' && $at == '0' && $bt == '1') {
                $temp = '1';
                $ret[$i] = '0';
            } else if ($temp == '0' && $at == '0' && $bt == '1') {
                $temp = '0';
                $ret[$i] = '1';
            } else if ($temp == '1' && $at == '0' && $bt == '0') {
                $temp = '0';
                $ret[$i] = '1';
            } else if ($temp == '0' && $at == '0' && $bt == '0') {
                $temp = '0';
                $ret[$i] = '0';
            }
        }
        if ($ret[$len-1] == '0') {
            array_pop($ret);
        }
        return implode('', array_reverse($ret));
    }
}

1021.删除最外层的括号

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B,其中 A 和 B 都是有效的括号字符串,+ 代表字符串的连接。例如,"","()","(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空,且不存在将其拆分为 S = A+B 的方法,我们称其为原语(primitive),其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S,考虑将其进行原语化分解,使得:S = P_1 + P_2 + ... + P_k,其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 S 。

示例 1:
输入:"(()())(())"
输出:"()()()"
解释:
输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())",
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2:
输入:"(()())(())(()(()))"
输出:"()()()()(())"
解释:
输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))",
删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3:
输入:"()()"
输出:""
解释:
输入字符串为 "()()",原语化分解得到 "()" + "()",
删除每个部分中的最外层括号后得到 "" + "" = ""。

提示:
S.length <= 10000
S[i] 为 "(" 或 ")"
S 是一个有效括号字符串

C

char * removeOuterParentheses(char * S){
    int i,sum=0, j=0;
    int len = strlen(S);
    for(i=0; i<len; i++) {
        if(S[i] == '(') {
            sum +=1;
        } else {
            sum -= 1;
        }
        if(S[i] == '(' && sum > 1) {
            S[j] = '(';
            j++;
        } else if(S[i] == ')' && sum > 0) {
            S[j] = ')';
            j++;
        }
    }
    S[j] = '\0';
    return S;
}

PHP

/**
 * @param String $S
 * @return String
 */
function removeOuterParentheses($S) {
    $stack = [];
    $ret = '';
    $S = str_split($S);
    $len = count($S);
    for ($i = 0; $i < $len; $i++) {
        if ($S[$i] == '(') {
            array_push($stack, $S[$i]);
            if (count($stack) > 1) {
                $ret .= $S[$i];
            }
        } else {
            if (count($stack) > 1) {
                $ret .= $S[$i];
            }
            array_pop($stack);
        }
    }
    return $ret;
}

其它

李白打酒

话说大诗人李白,一生好饮。幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。
则:babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢?
请你计算出所有可能方案的个数(包含题目给出的)。

C

#include <stdio.h>
int sum = 0;
int f(int a,int b,int c) {
    if (a > 0) {
         f(a-1,b,c*2);
    }
    if (b > 0) {
        f(a,b-1,c-1);
    }
    if (a == 0 && b == 0 && c == 1) {
        sum=sum+1;
    }
    return sum;
}
int main() {
    f(5, 9, 2);
    printf("%d\n", sum);
}

字母矩阵

给定两个整数M,N,生成一个M*N的矩阵,矩阵中元素取值为A至Z的26个字母中的一个,A在右下角,其余各数按逆时针方向旋转前进,依次递增放置,当超过26时又从A开始填充。例如,当M=5,N=8时,矩阵中的内容如下:

L K J I H G F E
M D C B A Z Y D
N E N M L K X C
O F G H I J W B
P Q R S T U V A

输入描述
M为行数,N为列数,其中M,N都为大于0的整数。
输出描述
分行输出相应的结果
输入例子
4 3
输出例子
F E D
G L C
H K B
I J A

C

#include  <stdio.h>
#include  <stdlib.h>
int main() {
    short M, N;
    char **matrix, row, col, i, direction, len;
    // M = 5;
    // N = 8;
    scanf("%hd %hd", &M, &N);
    // printf("%d %d\n", M, N);

    matrix = (char**)malloc(M*sizeof(char*));
    for (row = 0; row < M; row++) {
        matrix[row] = (char*)malloc(N*sizeof(char));
        for (col = 0; col < N; col++) {
            matrix[row][col] = 0;
        }
    }

    i = 65;
    len = M * N;
    direction = 0;
    for (col = N - 1, row = M - 1; len > 0; len--) {
        matrix[row][col] = i;
        i++;
        if (i > 90) {
            i = 65;
        }
        switch (direction) {
            case 0:
                row--;
                if (row == -1 || matrix[row][col] != 0) {
                    row++;
                    direction = 1;
                    col--;
                }
                break;
            case 1:
                col--;
                if (col == -1 || matrix[row][col] != 0) {
                    col++;
                    direction = 2;
                    row++;
                }
                break;
            case 2:
                row++;
                if (row == M || matrix[row][col] != 0) {
                    row--;
                    direction = 3;
                    col++;
                }
                break;
            case 3:
                col++;
                if (col == N || matrix[row][col] != 0) {
                    col--;
                    direction = 0;
                    row--;
                }
                break;
            default:break;
        }
    }

    for (row = 0; row < M; row++) {
        for (col = 0; col < N; col++) {
            printf("%c ", matrix[row][col]);
        }
        printf("\n");
    }

    return 0;
}

PHP

<?php

list($M, $N) = fscanf(STDIN, "%d %d");

$matrix = array_map(function ($item) use ($N) {
    return array_pad([], $N , 0);
}, array_pad([], $M , []));

$count = $M * $N;
$current = 65;
$direction = 0; // 0上 1左 2下 3右

for ($col = $N - 1, $row = $M - 1; $count > 0; $count--) {
    $matrix[$row][$col] = $current;
    $current++;
    if ($current > 90) {
        $current = 65;
    }
    switch ($direction) {
        case 0:
            $row--;
            if ($row == -1 || $matrix[$row][$col] != 0) {
                $row++;
                $direction = 1;
                $col--;
            }
            break;
        case 1:
            $col--;
            if ($col == -1 || $matrix[$row][$col] != 0) {
                $col++;
                $direction = 2;
                $row++;
            }
            break;
        case 2:
            $row++;
            if ($row == $M || $matrix[$row][$col] != 0) {
                $row--;
                $direction = 3;
                $col++;
            }
            break;
        case 3:
            $col++;
            if ($col == $N || $matrix[$row][$col] != 0) {
                $col--;
                $direction = 0;
                $row--;
            }
            break;
        default:break;
    }
}

printf("%s", array_reduce($matrix,
    function($carry, $row) {
        return $carry.array_reduce($row, function($carry, $col) {
            return $carry.sprintf("%c ", $col);
        }, '')."\n";
    }, ''));

淘宝网店

NowCoder在淘宝上开了一家网店。他发现在月份为素数的时候,当月每天能赚1元;否则每天能赚2元。
现在给你一段时间区间,请你帮他计算总收益有多少。
输入描述:
输入包含多组数据。
每组数据包含两个日期from和to (2000-01-01 ≤ from ≤ to ≤ 2999-12-31)。
日期用三个正整数表示,用空格隔开:year month day。
输出描述:
对应每一组数据,输出在给定的日期范围(包含开始和结束日期)内能赚多少钱。
示例1 
输入
2000 1 1 2000 1 31
2000 2 1 2000 2 29
输出
62
29

C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void dumpArr(int* s, int sSize) {
    for (int i = 0; i < sSize; i++) {
        printf("%d\n", *(s+i));
    }
}
int in_array(int tag) {
    int arr[] = {2, 3, 5, 7, 11};
    for (int i = 0; i < 5; i++) {
        if (arr[i] == tag) {
            return i;
        }
    }
    return -1;
}
int main() {

    struct tm** inputArr = NULL;
    int count = 0;
    int s_y, s_m, s_d, e_y, e_m, e_d;

    char sbuff[13];
    char ebuff[13];

    while (scanf("%d %d %d %d %d %d", &s_y, &s_m, &s_d, &e_y, &e_m, &e_d)) {
        if (inputArr == NULL) {
            inputArr = (struct tm**)malloc(sizeof(struct tm*)*(1+count));
        } else {
            inputArr = (struct tm**)realloc(inputArr, sizeof(struct tm*)*(1+count));
        }
        inputArr[count] = (struct tm*)malloc(sizeof(struct tm)*2);

        inputArr[count][0].tm_year = s_y - 1900;
        inputArr[count][0].tm_mon = s_m - 1;
        inputArr[count][0].tm_mday = s_d;
        inputArr[count][0].tm_hour = 0;
        inputArr[count][0].tm_min = 0;
        inputArr[count][0].tm_sec = 0;

        inputArr[count][1].tm_year = e_y - 1900;
        inputArr[count][1].tm_mon = e_m - 1;
        inputArr[count][1].tm_mday = e_d;
        inputArr[count][1].tm_hour = 0;
        inputArr[count][1].tm_min = 0;
        inputArr[count][1].tm_sec = 0;

        count++;
    }

    int* ret;
    ret = (int*)malloc(sizeof(int)*count);
    int sum;
    for (int i = 0; i < count; i++) {
        // strftime(sbuff, sizeof(sbuff), "%Y %m %d", &inputArr[i][0]);
        // strftime(ebuff, sizeof(ebuff), "%Y %m %d", &inputArr[i][1]);
        // printf("%s %s\n", sbuff, ebuff);

        time_t startTimestamp = mktime(&inputArr[i][0]);
        time_t endTimestamp = mktime(&inputArr[i][1]);
        time_t todayTimestamp = startTimestamp;

        sum = 0;
        do {
            char m[3];
            strftime(m, sizeof(m), "%m", localtime(&todayTimestamp));
            if (in_array(atoi(m)) >= 0) {
                sum += 1;
            } else {
                sum += 2;
            }
            todayTimestamp += 86400;
        } while (todayTimestamp <= endTimestamp);
        ret[i] = sum;
    }

    dumpArr(ret, count);

    return 0;
}

PHP

<?php

// 从标准输入中读取
$group = [];
while ($item = fscanf(STDIN, "%d %d %d %d %d %d")) {
    $group[] = [
        'start' => ['year' => $item[0], 'month' => $item[1], 'day' => $item[2]],
        'end' => ['year' => $item[3], 'month' => $item[4], 'day' => $item[5]],
    ];
}

$ret = [];
foreach ($group as $item) {
    $start = $item['start'];
    $end = $item['end'];

    $startTimestamp = mktime(0, 0, 0, $start['month'], $start['day'], $start['year']);
    $endTimestamp = mktime(0, 0, 0, $end['month'], $end['day'], $end['year']);
    $todayTimestamp = $startTimestamp;
    
    // date("j", 881078400); // 通过时间戳获取这是当前月的第几天
    // date("n", 881078400); // 通过时间戳获取这是几月份
    $sum = 0;
    do {
        if (in_array(date('n', $todayTimestamp), [2, 3, 5, 7, 11])) {
            $sum += 1;
        } else {
            $sum += 2;
        }
        $todayTimestamp += 86400; // 一天的时间戳 86400
    } while ($todayTimestamp <= $endTimestamp);

    $ret[] = $sum;
}

echo implode(PHP_EOL, $ret);

求1到20阶乘的和

/**
 * 1!+2!+3!+.....+20!
 */
#include <stdio.h>
long factorial(int i) {
    if (i == 1) {
        return i;
    }
    return i * factorial(i - 1);
}
int main(){
    int i;
    long sum;
    for (i = 1, sum = 0; i <= 20; i++) {
        sum += factorial(i);
    }
    printf("%ld", sum);
    return 0;
}

求 100 以内的质数

#include <stdio.h>
int main() {
    int i, j;
    for(i = 2; i < 100; i++) {
        for(j = 2; j <= i; j++) {
            if (i % j == 0) {
                break;
            }
        }
        if (i == j) {
            printf("质数%d\n", i);
        }
    }
}

数组练习

【问题描述】输入两个字符串str和tok。其中tok由若干字符构成,每个字符均可作为一个分隔字符对str进行分隔。
注意:str和tok中均可以包含空格。如果tok含有空格,则空格也作为str的分隔字符。
【输入形式】控制台分两行输入两个字符串str和tok。
【输出形式】分行输出str被分隔后的各字符串。
【样例输入】
jfi,dpf.,jfpe&df-jfpf/□□jfoef$djfo□,pe
,. □/&$-
(上例中&ldquo;□&rdquo;代表一个空格)
【样例输出】
jfi
dpf
jfpe
df
jfpf
jfoef
djfo
pe
【样例说明】输入字符串str = &ldquo;jfi,dpf.,jfpe&df-jfpf/□□jfoef$djfo□,pe&rdquo;,tok = &ldquo;,. □/&$-&rdquo;,tok中的每一个字符(包括空格)均可作为str的分隔符,输出如上例所示。
#include <stdio.h>

int in_array(char tag, char* arr, int len) {
    for (int i = 0; i < len; i++) {
        if (arr[i] == tag) {
            return i;
        }
    }
    return -1;
}

int main() {

    const int max_arr_len = 264144;

    char str[max_arr_len];
    char tok[max_arr_len];

    // char str[] = "jfi,dpf.,jfpe&df-jfpf";
    // char tok[] = ",.,&-";

    int i = 0;
    int len;
    int flg = 0; // 标记是否需要换行 0不需要 1需要

    /**
     * 题目里要求 tok 可能包含空格,所以不能用 scanf,
     * 又因为 gets 被废弃了,gets_s 是c11的特性可能不被支持,
     * 所以这里用了 fgets ,直接读取输入流
     */
    fgets(str, max_arr_len, stdin);
    fgets(tok, max_arr_len, stdin);
    
    for(len = 0; tok[len] != '\0'; ++len); // 求tok的长度
    while (str[i] != '\0') {
        if (in_array(str[i], tok, len) == -1) {
            putchar(str[i]);
            flg = 1;
        } else {
            if (flg == 1) {
                putchar('\n');
                flg = 0;
            }
        }
        i++;
    }

    return 0;
}

力扣(LeetCode)来源的题目著作权归领扣网络所有。链接:https://leetcode-cn.com

上述题目的解答均为作者所有