京东2018秋招笔试编程题集合
1.括号匹配方案
合法的括号匹配序列被定义为:
- 空串""是合法的括号序列
- 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
- 如果"X"是一个合法的序列,那么"(X)"也是一个合法的括号序列
- 每个合法的括号序列都可以由上面的规则生成
例如"", "()", "()()()", "(()())", "(((())))"都是合法的。 东东现在有一个合法的括号序列s,一次移除操作分为两步:
- 移除序列s中第一个左括号
- 移除序列s中任意一个右括号.保证操作之后s还是一个合法的括号序列
东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空
如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
例如: s = "()()()()()",输出1, 因为每次都只能选择被移除的左括号所相邻的右括号.
s = "(((())))",输出24, 第一次有4种情况, 第二次有3种情况, ... ,依次类推, 4 * 3 * 2 * 1 = 24
输入描述:
输入包括一行,一个合法的括号序列s,序列长度length(2 ≤ length ≤ 20).
输出描述:
输出一个整数,表示方案数
输入例子1:
(((())))
输出例子1:
24
思路:
- 遍历字符串,每次把左括号都压入栈,每次遇到右括号,先统计栈中有几个左括号,统计数与上次统计数相乘
- 接着弹出栈中的一个左括号
- 直到遍历结束,结果即为方案数
代码:
import java.util.Scanner; import java.util.Stack; public class BracketMatch { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); Stack<Character> stack = new Stack<>(); int result = 1; char c; for (int i = 0; i < s.length(); i++) { c = s.charAt(i); if (c == '(') { stack.push(c); } if (c == ')') { int size = stack.size(); result *= size; stack.pop(); } } System.out.println(result); } }
2.神奇数
东东在一本古籍上看到有一种神奇数,如果能够将一个数的数字分成两组,其中一组数字的和等于另一组数字的和,我们就将这个数称为神奇数。例如242就是一个神奇数,我们能够将这个数的数字分成两组,分别是{2,2}以及{4},而且这两组数的和都是4.东东现在需要统计给定区间中有多少个神奇数,即给定区间[l, r],统计这个区间中有多少个神奇数,请你来帮助他。
输入描述:
输入包括一行,一行中两个整数l和r(1 ≤ l, r ≤ 10^9, 0 ≤ r - l ≤ 10^6),以空格分割
输出描述:
输出一个整数,即区间内的神奇数个数
输入例子1:
1 50
输出例子1:
4
思路:
首先判断数组能否被平分,即数组分割问题, dp[i][j]表示数组前i个数字能否求和得到 j 则dp[i][j]=dp[i−1][j]||dp[i−1][j−array[i]],其中||是逻辑或运算。 优化: 1、若sum(array)为奇数,直接返回false 2、使用逆序循环将dp数组简化为一维数组
代码:
import java.util.Arrays; import java.util.Scanner; public class MagicNumber { public static boolean isMagic(int[] nums, int sum) { int len = nums.length; if (sum % 2 != 0) return false; int mid = sum / 2; int[] dp = new int[mid + 1]; dp[0] = 1; for (int i = 0; i < len; i++) { for (int j = mid; j > 0; j--) { if (j >= nums[i] && nums[i] != -1) dp[j] = Math.max(dp[j], dp[j - nums[i]]); } } if (dp[mid] > 0) return true; else return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int l = sc.nextInt(); int r = sc.nextInt(); int result = 0; for (int i = l; i <= r; i++) { int num = I; int[] nums = new int[10]; int sum = 0; Arrays.fill(nums, -1); int index = 0; while (num > 0) { int temp = num % 10; nums[index++] = temp; sum += temp; num = num / 10; } if (isMagic(nums, sum)) { result++; } } System.out.println(result); } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
从零开始学 Web 之 HTML(一)认识前端
大家好,这里是 Daotin 从零开始学 Web 系列教程。此文首发于「 Daotin的梦呓 」,欢迎大家订阅关注。在这里我会从 Web 前端零基础开始,一步步学习 Web 相关的知识点,期间也会分享一些好玩的项目。现在就让我们一起进入 Web 前端学习的冒险之旅吧! 1、什么是前端 前端对于网站来说,通常是指网页,网站的前台部分包括网站的表现层和结构层。因此前端技术一般分为前端设计和前端开发。 前端设计一般可以理解为网站的视觉设计,比如 UI 设计; 前端开发则是网站的前台代码实现,包括基本的HTML和CSS以及JavaScript/ajax,现在最新的高级版本HTML5、CSS3,以及SVG等。 前端开发的核心部分主要是:HTML,CSS,JavaScript 三个部分。 HTML 是这三者中最基础的部分,相当于是网页的骨架,也就是网页的结构;CSS 部分是网页的表现形式,也可以说是网页的美化,比如一个图片的大小、位置,文字的大小颜色等;JavaScript 是一种动态的脚本语言,负责与用户进行交互,增加用户体验的作用。 2、网页组成 一个网页的组成部分主要包括下面几个部分:文字、...
- 下一篇
如何利用Python网络爬虫抓取微信好友数量以及微信好友的男女比例
前几天给大家分享了利用Python网络爬虫抓取微信朋友圈的动态(上)和利用Python网络爬虫爬取微信朋友圈动态——附代码(下),并且对抓取到的数据进行了Python词云和wordart可视化,感兴趣的伙伴可以戳这篇文章:利用Python词云和wordart可视化工具对朋友圈数据进行可视化。 今天我们继续focus on微信,不过这次给大家带来的是利用Python网络爬虫抓取微信好友总数量和微信好友男女性别的分布情况。代码实现蛮简单的,具体的教程如下。 相信大家都知道,直接通过网页抓取微信的数据不太可行,但是强大的Python提供了一个itchat库,搭建了链接微信好友信息的友好桥梁,直接上代码,如下图所示。 关键部分的代码,都有注释,方便大家理解。当程序运行的时候,会弹出一个微信二维码,此时需要用手机扫码授权登录。如果您当时正在微信电脑版上登录的话,此时微信会强制退出,然后进行授权。授权成功之后,程序会继续往下执行,稍等片刻之后,便可以给您返回您的微信好友数量信息。 在这里,以小编的微信好友为例,程序运行之后,得到的信息如下图所示: 可以看到,小编的微信好友共有1637人。相信很多小...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS8安装Docker,最新的服务器搭配容器使用
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS6,CentOS7官方镜像安装Oracle11G
- CentOS关闭SELinux安全模块
- CentOS7设置SWAP分区,小内存服务器的救世主
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装