九度OJ 1366(栈操作) 1367(二叉树遍历) 1368(二叉树路径) 1369(字符串全排列) 1370(特殊数字查找)

本文主要是介绍九度OJ 1366(栈操作) 1367(二叉树遍历) 1368(二叉树路径) 1369(字符串全排列) 1370(特殊数字查找),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


1366:栈的压入、弹出序列

http://ac.jobdu.com/problem.php?pid=1366

题意

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。

思路

根据两个数组的值,还原栈的压入弹出过程,如果能够完全还原则答案为YES。

代码

#include <stdio.h>#define N 100000int stack[N], top;void init()
{top = 0;
}int push(int key)
{if (top == N)return 0;else{stack[top++] = key;return 1;}
}int pop(int *key)
{if (top == 0)return 0;else{*key = stack[--top];return 1;}
}int Top()
{return stack[top-1];
}int main(void)
{int n, i, j;int a[N], b[N];int key;while (scanf("%d", &n) != EOF){for(i=0; i<n; i++)scanf("%d", &a[i]);for(i=0; i<n; i++)scanf("%d", &b[i]);init();i = j = 0;while (i<n && j<n){do{push(a[i]);i++;} while (i<n && top && Top() != b[j]);while (j<n && top && Top() == b[j]){pop(&key);j++;}}if (i<n || j<n)printf("No\n");elseprintf("Yes\n");}return 0;
}
/**************************************************************Problem: 1366User: liangrx06Language: CResult: AcceptedTime:200 msMemory:2012 kb
****************************************************************/

1367:二叉搜索树的后序遍历序列

http://ac.jobdu.com/problem.php?pid=1367

题意

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。

思路

反向模拟后序遍历过程,如果没有发现矛盾则答案为YES。

代码

#include <stdio.h>
#include <string.h>#define N 10000int checkAfter(int *a, int len)
{if (len <= 1)return 1;int root = a[len-1];int i;int res;for (i=0; i<len-1; i++){if (a[i] == root)return 0;if (a[i] > root)break;}int mid = i;for (i=mid; i<len-1; i++){if (a[i] <= root)return 0;}res = checkAfter(a, mid-1);if (res == 0)return 0;res = checkAfter(a+mid, len-1-mid);if (res == 0)return 0;return 1;
}
int main(void)
{int n, i, res;int a[N];while (scanf("%d", &n) != EOF){for (i=0; i<n; i++)scanf("%d", &a[i]);res = checkAfter(a, n);if (res == 0)printf("No\n");elseprintf("Yes\n");}return 0;
}
/**************************************************************Problem: 1367User: liangrx06Language: CResult: AcceptedTime:10 msMemory:912 kb
****************************************************************/

1368:二叉树中和为某一值的路径

http://ac.jobdu.com/problem.php?pid=1368

题意

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

模拟二叉树遍历过程

代码

#include <stdio.h>#define N 10000void search(int a[N][3], int h, int k, int sum, int id[], int step)
{if (h == -1)return ;int i;sum += a[h][0];id[step] = h;step ++;if (a[h][1] == -1 && a[h][2] == -1 && k == sum){printf("A path is found:");for (i=0; i<step; i++)printf(" %d", id[i]);printf("\n");return ;}if (a[h][1] < a[h][2]){search(a, a[h][1], k, sum, id, step);search(a, a[h][2], k, sum, id, step);}else{search(a, a[h][2], k, sum, id, step);search(a, a[h][1], k, sum, id, step);}
}int main(void)
{int n, k, i;int a[N+1][3];int id[N+1];while (scanf("%d%d", &n, &k) != EOF){for (i=1; i<=n; i++)scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);printf("result:\n");search(a, 1, k, 0, id, 0);}return 0;
}
/**************************************************************Problem: 1368User: liangrx06Language: CResult: AcceptedTime:30 msMemory:1000 kb
****************************************************************/

1369:字符串的排列

http://ac.jobdu.com/problem.php?pid=1369

题意

输入一个字符串,按字典序打印出该字符串中字符的所有排列。

思路

DFS可解。
如果用c++有一个函数next_p****()直接能打印,具体忘记了。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define N 9 char s[N+1];
int n;void array(int begin)
{int i, j;if (begin == n-1){printf("%s\n", s);return;}char c;for (i=begin; i<n; i++){if (i>begin && s[i]==s[i-1])continue;c = s[i];for (j=i; j>begin; j--)s[j] = s[j-1];s[begin] = c;array(begin+1);c = s[begin];for (j = begin; j < i; j++)s[j] = s[j+1];s[j] = c;}
}int cmp(const void *a, const void *b)
{return *(char *)a - *(char *)b;
}int main(void)
{while (scanf("%s", s) != EOF){n = strlen(s);qsort(s, n, sizeof(s[0]), cmp);array(0);//printf("\n");}return 0;
}
/**************************************************************Problem: 1369User: liangrx06Language: CResult: AcceptedTime:120 msMemory:912 kb
****************************************************************/

1370:数组中出现次数超过一半的数字

http://ac.jobdu.com/problem.php?pid=1370

题意

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

思路

我用的是随机算法测试出现概率,准确度还是很高的。

代码

#include <stdio.h>
#include <time.h>
#include <stdlib.h>#define N 100000int random()
{int num;num = rand()%10;printf("%d\n", num);if(num==0)num++;return num;
}int main()
{int i, j, n;int a[N], b[100], count[100];while(scanf("%d", &n) != EOF){for (i=0; i<n; i++)scanf("%d", &a[i]);if (n == 1){printf("%d\n", a[0]);continue;}srand( (unsigned)time( NULL ) );//printf("rand() = %d\n", rand());for (i=0; i<100; ++i)b[i] = a[rand()%n];for (i=0; i<100; i++){count[i] = 0;for (j=0; j<100; j++){if (b[i] == b[j])count[i] ++;if (count[i] > 40)break;}if (count[i] > 40)break;}if (i==100 && j==100){printf("-1\n");continue;}int k=0;for (j=0; j<n; j++){if (a[j] == b[i])k ++;}if (k > n/2)printf("%d\n", b[i]);elseprintf("-1\n");}return 0;
}
/**************************************************************Problem: 1370User: liangrx06Language: CResult: AcceptedTime:50 msMemory:1236 kb
****************************************************************/

这篇关于九度OJ 1366(栈操作) 1367(二叉树遍历) 1368(二叉树路径) 1369(字符串全排列) 1370(特殊数字查找)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/868687

相关文章

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,:本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘