2017年11月

我为什么作死想去参加ACM…我为什么要学算法…我明明相当前端的…我还年轻,我不想掉头发(╯°Д°)╯︵┴─┴

写了好几天的算法,忽然发现时间复杂度爆炸。明明有一个很简单的类似桶排序的解决方法,我嫌弃占空间一定要换思路……结果发现这个数组不知道被我遍历了多少遍……中间还嵌了个冒泡排序( ´◔‸◔`)

C语言丢一边吧,打两天星际换换脑子。

闭着眼睛睡不着,拿起手机一看才发现我已经想了一个小时算法题。可能最近肠胃炎的药吃多了睡不着吧……

所以想通了算法我现在是不是应该拿出电脑码代码……可是明天早上六点要起床晨跑(╯°Д°)╯︵┴─┴

我还是换道题继续想吧,想着想着就睡着了。

括号配对问题

时间限制: 3000 ms  |  内存限制: 65535 KB
难度:3

描述

现在,有一行括号序列,请你检查这行括号是否配对。

输入

第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[", "]", "(", ")" 四种字符

输出

每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No

样例输入

3
[(])
(])
([[]()])

样例输出

No
No
Yes

来源网络

上传者naonao

解题思路

用了栈的思想,后进后出。读取一个括号,如果与栈尾配对,则栈尾出栈,否则入栈。

代码

#include &lt;stdio.h&gt;
#define Max 10000
int main()
{
    int n;
    scanf("%d", &n);
    while (n > 0)
    {
        char s[Max], t[Max];
        //printf("%d inpot=", n);//debug
        scanf("%s", s);
        int j = 0, i = 0;
        //printf("pdstart\n");//debug
        while (s[i] != '\0')
        {
            t[j] = s[i]; //入栈
            //printf("j=%d\t", j);//debug
            t[j + 1] = '\0'; //关闭
            //打印配对前栈
            //printf("t=%s\t", t);//debug
            //配对
            if ((t[j] == ']' && t[j - 1] == '[') || (t[j] == ')' && t[j - 1] == '('))
            {
                j = j - 1;
                t[j] = '\0'; //出栈
                //printf("j=%d\t->\t", j);//debug
            }
            else
            {
                j++;
                //printf("j=%d\t--\t", j);//debug
            }
            i++;
            //打印配对后栈
            //printf("t=%s\n", t);//debug
        }
        if (t[0] == '\0')
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
        //printf("pdend\n");//debug
        n--;
    }
    return 0;
}

描述
小明十分聪明,而且十分擅长排列计算。比如给小明一个数字5,他能立刻给出1-5按字典序的全排列,如果你想为难他,在这5个数字中选出几个数字让他继续全排列,那么你就错了,他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。
输入
第一行输入整数N(1<N<10)表示多少组测试数据,
每组测试数据第一行两个整数 n m (1<n<9,0<m<=n)
输出
在1-n中选取m个字符进行全排列,按字典序全部输出,每种排列占一行,每组数据间不需分界。如样例
样例输入
2
3 1
4 2
样例输出
1
2
3
12
13
14
21
23
24
31
32
34
41
42
43


 解题笔记

说实话我刚刚看到全排序几个字的时候有点懵逼,后来才想起好像数学老师讲过……言归正传第一个想到的算法是冒泡排序,完全冒泡一遍不就是一个全排列吗!但是貌似和题意不符……貌似应该是一个深度优先算法。总之先搭个框架然后再去温习下算法书233

#include <stdio.h> 
int main()
{
    int n, a, b;
    scanf("%d", &n);
    getchar();
    for (n; n > 0; n--)
    {
        scanf("%d", &a);
        getchar();
        scanf("%d", &b);
        getchar();
        //开始排列

        //结束排列
    }
    return 0;
}