T1 除自身以外数组的乘积

给你一个长度为 4 的整数数组 nums，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

样例输入:

1
[1,2,3,4]

样例输出:

1
[24,12,8,6]

说明: 请不要使用除法，且在 O(n)O(n) 时间复杂度内完成此题。

这个题的正解限制的很死，但是相对来说难度不高

主要是因为

  1. O(n)O(n) 时间复杂度限制

  2. 不允许使用除法

正常思维下第一时间想到的应该是双层循环，外层循环循环数组 output[i] ，内层循环循环数组 nums[k] ,然后通过 if 判断进行乘算

但是这个算法是 O(n2)O(n^2) 的，不符合题意

那么下一步的想法是首先算出四个数总乘积，再对其做除法得到四个输出，但是同样不符合题意。

那么就只剩下不多的做法了，我的解法直接上代码会比较快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
int main()
{
    int nums[4] = {1, 2, 3, 4};
    int output[4] = {1, 1, 1, 1};
    //初值为1,避免出现乘积为0的情况
    int i;
    for (i = 0; i < 4; i++)
    {
        if (i != 0)
            output[i] *= nums[0];
        if (i != 1)
            output[i] *= nums[1];
        if (i != 2)
            output[i] *= nums[2];
        if (i != 3)
            output[i] *= nums[3];
    }
    printf("[");
    for (i = 0; i < 3; i++)
        printf("%d,", output[i]);
    printf("%d]", output[3]);
    return 0;
}

唯一注意的是输出部分，要求保留两侧的方括号和逗号，具体思路看代码就行

T2 核桃的数量

小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃(据传言能补脑)。他的要求是：

  1. 各组的核桃数量必须相同

  2. 各组内必须能平分核桃(当然是不能打碎的)

  3. 尽量提供满足 1,2 条件的最小数量(节约闹革命嘛)

输入约定:

程序从标准输入读入：a b c

a,b,c 都是正整数，表示每个组正在加班的人数，用空格分开(a,b,c<30)(a,b,c<30)

输出规范:

一个正整数，表示每袋核桃的数量。

样例输入 1

1
2 4 5

样例输出 1：

1
20

样例输入 2：

1
3 1 1

样例输出 2：

1
3

这个题没啥好说的

首先要保证核桃数量是每个组人数的倍数，因为要能在组内平分，其次要保证分给每组的数量都相同，因此其实很容易想到就是三个组人数的最小公倍数。

实在想不到遍历就是，1 除外一直向上遍历，令这个数是三个数的最小公倍数就行

如果遍历做法也是可以的

在这只给出核心算法

1
2
3
4
5
6
7
8
for (i = 2; i < a * b * c; i++)
{
    if (i / a == 0 && i / b == 0 && i / c == 0)
    {
        printf("%d", i);
        return 0;
    }
}

下面是利用最小公倍数的算法，这段代码的 gcd(a,b)使用了递归和三目运算符，请大家酌情理解，大家教材上那种算 gcd(最大公倍数)的方法同样适用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int gcd(int x, int y)
{
    return x ? gcd(y % x, x) : y;
}
//这段函数看不懂不勉强
int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}
int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    printf("%d", lcm(lcm(a, b), c));
    //主要目的是求三个数的最小公倍数
    return 0;
}

T3-1 杨辉三角

给定一个非负索引 kk，其中 k≤33k \le 33，返回杨辉三角的第 kk 行。在杨辉三角中，每个数是它左上方和右上方的数的和。

样例输入:

1
3

样例输出:

1
[1,3,3,1]

这个有点考平常题量，得知道杨辉三角是个啥玩意

杨辉三角主要有几个特性

  1. 每个数等于它上方两数之和。

  2. 每行数字左右对称，由 1 开始逐渐变大。

  3. 第 nn 行的数字有 nn 项。

  4. 前 nn 行共 (1+n)n2\frac{(1+n)n}2 个数。

  5. 第 n 行的 m 个数可表示为 Cn−1m−1C_{n-1}^{m-1}，即为从 n−1n-1 个不同元素中取 m−1m-1 个元素的组合数。

杨辉三角大致形状是这样。

1
2
3
4
5
6
7
8
[1]
[1,1]
[1,2,1]
[1,3,3,1] <-- 样例输出的第3行
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
......

题目里给出的样例省去了第一行的 1，所以其实是输出 k+1 行，我不太确定，姑且按这个来。

想要做这道题，如果熟悉数列性质，其实可以使用第 5 条性质，使用组合数答题

但是同样这里也给出打印整个杨辉三角的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <string.h>
#define MAXN 35
int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int m[MAXN][MAXN];
    memset(m, 0, sizeof(m));
    int x, y, n;
    scanf("%d", &n);
    m[1][1] = 1;
    m[1][2] = 1;
    m[2][2] = 1;
    for (y = 3; y <= n + 1; y++)
        for (x = 1; x <= y; x++)
            m[x][y] = m[x][y - 1] + m[x - 1][y - 1];
    printf("[");
    for (x = 1; x <= n; x++)
        printf("%d,", m[x][n + 1]);
    printf("%d]", m[n + 1][n + 1]);
    return 0;
}

它使用二维数组将整个杨辉三角存储在内部存储内。

但是我们上面说过，杨辉三角的数存在规律

第 nn 行的 mm 个数可表示为 Cn−1m−1C_{n-1}^{m-1}，即为从 n−1n-1 个不同元素中取 m−1m-1 个元素的组合数。

那么我们就有了数学解法

组合数计算方法

Cnm=n!m!(n−m)!C^{m}_{n}=\frac{n!}{m!(n-m)!}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
long long factorial(int x)
{
    long long sum = 1;
    int i;
    for (i = 1; i <= x; i++)
        sum *= i;
    return sum;
}
int combinatorial(int m, int n)
{
    if (m == 0)
        return 1;
    return factorial(n) / (factorial(m) * factorial(n - m));
}
int main()
{
    int n;
    scanf("%d", &n);
    int i = 0;
    n++;
    printf("[");
    for (i = 1; i <= n - 1; i++)
    {
        printf("%d,", combinatorial(i - 1, n - 1));
    }
    printf("%d]", combinatorial(i - 1, n - 1));
    return 0;
}

T3-2 买饮料

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C 型饮料，凭 3 个瓶盖可以再换一瓶 C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。

输入约定:

一个整数 n，表示开始购买的饮料数量 (0<n<10000)(0<n<10000)

输出规范:

一个整数，表示实际得到的饮料数

样例输入 1

1
100

样例输出 1

1
149

样例输入 2

1
100

样例输出 2

1
151

这道题的思路也相当简单，当你手中的饮料数小于三的时候，则不能进行下次兑换。

用now表示现有的饮料，sum表示总共的饮料，每次兑换饮料为now%3，兑换后还有的饮料为now%3+now/3，只要now大于等于三就一直循环，每次循环加兑换的饮料(sum+=now/3)，结束循环后即可得出总共的饮料。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main()
{
    int n, now, sum;
    scanf("%d", &n);
    sum = n;
    now = n;
    while (now >= 3)
    {
        sum += now / 3;
        now = now % 3 + now / 3;
    }
    printf("%d", sum);
    return 0;
}

T4 报数出队

一群小孩围成一个圈，从第一个开始报数(从 1 到 5 报数)，报到 5 的小孩退出圈，继续，求剩下的最后一个小孩的编号。

要求输入小孩的个数，输出最后一个小孩对应的编号。

样例输入 1

1
5

样例输出 1

1
2

这个题也是很经典的一个题，最优解法是循环链表，考虑到同学们的水平这里给出一种 C 语言和数组的解法

大致思路是：

使用一个布尔型数组vis,使用memset(vis, 1, sizeof(vis));对其初始化为 1，其代表当前下标表示的小孩未出队，使用sum计算当前还有多少人未出队。

移动伪指针 p，读取vis数据，遇到 0 跳过，遇 1 令计数器 k 增加，累积到 5 将当前指向的成员标 0。同时sum递减。sum==1即剩余 1 人退出循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <string.h>
#define MAXN 10000
int main()
{
    int n;
    scanf("%d", &n);
    int sum = n, p = 1, k = 0;
    bool vis[MAXN];
    memset(vis, 1, sizeof(vis));
    while (sum > 1)
    {
        if (p > n)
            p = 1;
        if (vis[p])
            k++;
        if (k == 5)
        {
            vis[p] = 0;
            k = 0;
            sum--;
        }
        p++;
    }
    for (int i = 1; i <= n; i++)
        if (vis[i])
            printf("%d ", i);
    return 0;
}

T5 冰雹数

任意给定一个正整数 NN

  • 如果是偶数，执行： N/2N / 2

  • 如果是奇数，执行： N∗3+1N * 3 + 1

生成的新的数字再执行同样的动作，循环往复。

通过观察发现，这个数字会一会儿上升到很高，一会儿又降落下来。

就这样起起落落的，但最终必会落到 "1""1"

这有点像小冰雹粒子在冰雹云中翻滚增长的样子。

比如 N=9N=9 时：

1
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

可以看到，N=9N=9 的时候，这个"小冰雹"最高冲到了 52 这个高度。

输入约定：

一个正整数 N(N<1000000)N(N<1000000)

输出规范:

一个正整数，表示不大于 N 的数字，经过冰雹数变换过程中，最高冲到了多少。

样例输入 1

1
9

样例输出 1

1
52

样例输入 2

1
100

样例输出 2

1
100

这个题应该是非常非常明显的递归暗示了，题目里

但最终必会落到 "1""1"

生成的新的数字再执行同样的动作，循环往复。

这不基本是明示递归边界条件——当前值为 1 嘛，而且题目都说了必定会变化为 1，不用担心递归边界问题。

而执行同样的动作也满足递归的条件

所以我认为这题的正解是递归。

常规解法也比较简单，在这里不放出常规写法了，就阐述一下思路：利用 while 循环循环目前的数字，判断条件为n>1,每次判断奇偶性再执行两种操作，记录过程中的最大值即可

请注意初值也算是过程中的值！不要忘记！

下面给出递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
int max;
void HailNumber(int n)
{
    if (n > max)
        max = n;
    if (n == 1)
        return;
    if (n % 2 == 1)
        HailNumber(n * 3 + 1);
    if (n % 2 == 0)
        HailNumber(n / 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    max = n;
    HailNumber(n);
    printf("%d", max);
    return 0;
}

by Ansel