九度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

相关文章

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

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

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的