文档章节

给定一个布尔表达式,由0、1、&、|和^等符号组成,以及一个想要的布尔结果result,实现一个函数,算出有几种括号的放法可使该表达式

一贱书生
 一贱书生
发布于 2016/11/23 09:04
字数 718
阅读 16
收藏 0
点赞 0
评论 0

/**
 * 攻略:给定一个布尔表达式,由0、1、&、|和^等符号组成,以及一个想要的布尔结果result,实现一个函数,算出有几种括号的放法可使该表达式
 * 得出result值。

 */

两种方法:

方法一:

 

  1. /** 
  2.  * 思路:迭代整个表达式,将每个运算符当作第一个要加括号的运算符。 
  3.  * @param exp 
  4.  * @param result 
  5.  * @param s:start 
  6.  * @param e:end 
  7.  * @return 
  8.  */  
  9. public static int f(String exp,boolean result,int s,int e){  
  10.     if(s==e){  
  11.         if(exp.charAt(s)=='1'&&result)  
  12.             return 1;  
  13.         if(exp.charAt(s)=='0'&&!result)  
  14.             return 1;  
  15.         return 0;  
  16.     }  
  17.       
  18.     int c=0;  
  19.     if(result){  
  20.         for(int i=s+1;i<=e;i+=2){  
  21.             if(exp.charAt(i)=='&'){  
  22.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  23.             }else if(exp.charAt(i)=='|'){  
  24.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  25.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  26.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  27.             }else if(exp.charAt(i)=='^'){  
  28.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  29.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  30.             }  
  31.         }  
  32.     }else{  
  33.         for(int i=s+1;i<=e;i+=2){  
  34.             if(exp.charAt(i)=='&'){  
  35.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  36.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  37.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  38.             }else if(exp.charAt(i)=='|'){  
  39.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  40.             }else if(exp.charAt(i)=='^'){  
  41.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  42.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  43.             }  
  44.         }         
  45.     }  
  46.   
  47.     return c;     
  48. }     


 

 

方法二:

 

[java] view plain copy

 

  1. //动态规划  
  2. /** 
  3.  * 思路:缓存不同表达式的结果,避免多次用到同一个exp的值时需要重算。对expression和result进行缓存。 
  4.  * @param exp 
  5.  * @param result 
  6.  * @param s 
  7.  * @param e 
  8.  * @param map 
  9.  * @return 
  10.  */  
  11. public static int ff(String exp,boolean result,int s,int e,HashMap<String,Integer> map){  
  12.     String key=""+result+s+e;//注意加""的位置,应加在前面,表示为字符串的拼接。否则,则表示值先相加,再转字符串  
  13.     if(map.containsKey(key))  
  14.         return map.get(key);  
  15.       
  16.     int c=0;  
  17.     if(result){  
  18.         for(int i=s+1;i<=e;i+=2){  
  19.             if(exp.charAt(i)=='&'){  
  20.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  21.             }else if(exp.charAt(i)=='|'){  
  22.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  23.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  24.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  25.             }else if(exp.charAt(i)=='^'){  
  26.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  27.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  28.             }  
  29.         }  
  30.     }else{  
  31.         for(int i=s+1;i<=e;i+=2){  
  32.             if(exp.charAt(i)=='&'){  
  33.                 c+=f(exp,true,s,i-1)*f(exp,false,i+1,e);  
  34.                 c+=f(exp,false,s,i-1)*f(exp,true,i+1,e);  
  35.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  36.             }else if(exp.charAt(i)=='|'){  
  37.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  38.             }else if(exp.charAt(i)=='^'){  
  39.                 c+=f(exp,true,s,i-1)*f(exp,true,i+1,e);  
  40.                 c+=f(exp,false,s,i-1)*f(exp,false,i+1,e);  
  41.             }  
  42.         }         
  43.     }  
  44.     map.put(key, c);  
  45.     return c;     
  46.       
  47. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
Scheme语言入门

Scheme语言入门 最早听说 LISP,是 Stallman 的 GNU Emacs 中将 LISP 作为嵌入语言,定制和增强 Emacs。GNU Emacs 是一个文本编辑器,文本就是一种符号,而 Lisp 正好就是针对符号计算发明的...

平凡之路 ⋅ 2014/11/27 ⋅ 0

sass笔记-4|像写脚本一样写Sass,把能交给Sass办的都交给它

Sass笔记关于sass的基础部分已经写完,这一篇介绍Sass的高级特性——脚本特性。Sass能做很多事让样式表更智能,我们先会看到Sass眼中的数据类型,在这些数据类型上会有可进行的操作,此外,S...

Stinson_Zhao ⋅ 2016/12/06 ⋅ 0

javascript:基本数据结构

JavaScript提供脚本语言的编程与C++非常相似,它只是去掉了C语言中有关指针等容易产生的错误,并提供了功能强大的类库.对于已经具备C++或C语言的人来说,学习JavaScript脚本语言是一件非常轻松愉...

街边 ⋅ 2014/01/09 ⋅ 0

C#循环控制语句

本节课将介绍如何使用C#控制语句中的循环语句,本课目的如下: 1.学会"while"循环的用法。 2.学会"do" 循环的用法。 3.学会"for" 循环的用法。 4.学会foreach循环的用法。 5.进一步了解"brea...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

js正则学习笔记

工作中不可避免的会用到正则表达式,现就正则做以下总结。 正则简介 正则表达式是一种表达文本模式(即字符串结构)的方法,常常用作按照“给定模式”匹配文本的工具。 有两种创建方式,一种...

tiancai啊呆 ⋅ 2017/12/20 ⋅ 0

Kotlin:基本类型都是对象,原生类型将成为回忆

在Kotlin中,所有东西都是对象,我们可以在任何变量(如基本类型:数字、字符、布尔、数组与字符串等)上调用成员函数和属性。 一、数字 1. 内置类型种类 Kotlin提供了如下内置类型来表示数据...

p106786860 ⋅ 2017/08/08 ⋅ 0

COREJAVA第二篇

第二章、 JAVA编程基础 一、JAVA的基本语法 二、JAVA中的变量 三、运算符与表达式 四、流程控制语句 五、函数 六、数组 七、Java开发类库组成 一、JAVA的基本语法 (1)JAVA代码的落脚点 Ja...

北京创想睿和 ⋅ 2014/03/07 ⋅ 0

条件优化技术

条件: 对元组进行过滤和连接的表达式,形式上是出现在WHERE/JOIN-ON/HAVING的子句中的表达式 1、条件下推 把与单个表相关的条件,放到对单表进行扫描的过程中执行。 2、条件化简 针对:WHE...

xixicat ⋅ 2014/08/16 ⋅ 0

计算器 abacus 技术文档之二----初步设计

======================================= 计算器 abacus 的下载地址:http://www.oschina.net/code/snippet73693213725 如果你有关于 abacus 的问题或者建议,请发邮件至 zhoucosin@163.co......

zhcosin ⋅ 2012/10/30 ⋅ 0

Python中的数值类型

Python中的基本数据类型有数值类型、字符串型、列表、元组、字典、集合等。本章介绍数值类型。数值类型包括整型、布尔型、浮点型和复数类型。 3.1 整型 3.1.1 取值范围 和其他语言一样,Pyt...

勇敢的石头 ⋅ 2017/12/23 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Kubeflow实战系列:利用TFJob导出分布式TensorFlow模型

介绍 本系列将介绍如何在阿里云容器服务上运行Kubeflow, 本文介绍如何使用TfJob导出分布式模型训练模型。 第一篇:阿里云上使用JupyterHub 第二篇:阿里云上小试TFJob 第三篇:利用TFJob运行...

全部原谅 ⋅ 9分钟前 ⋅ 0

007. 深入JVM学习—老年代

老年代空间的主要目的是用于存储由Eden发送来的对象,一般在经历好几次“Minor GC”还会保存下来的对象,才会被复制到老年代,这样就可以存放更多的对象,同时在老年代中执行GC的次数也相对较...

影狼 ⋅ 10分钟前 ⋅ 0

常见的一些C#开源框架或者开源项目

原:https://blog.csdn.net/qq_27825451/article/details/70666044 Json.NET http://json.codeplex.com/ Json.Net 是一个读写Json效率比较高的.Net框架.Json.Net 使得在.Net环境下使用Json更......

whoisliang ⋅ 11分钟前 ⋅ 0

设计模式基本原理

刚开始接触编程这行的时候看过设计模式,当时感觉学这些模式没有太大的用处,当时也看不太懂。但是随着慢慢接触这一行,经过一段时间的编程以后,再回过头来看设计模式,发现设计模式的确是太...

王子城 ⋅ 14分钟前 ⋅ 0

阿里云全面支持IPv6!一文揽尽4位大咖精彩演讲

摘要: 自从去年11月以来,阿里巴巴高度重视数据中心的网络改造、云产品改造、应用及网络改造等多个维度,经过半年以来的建设,阿里云已经完成了域名解析等关键产品的分析,现在阿里云已经完...

传授知识的天使 ⋅ 25分钟前 ⋅ 0

windows Android sdk 配置

1、下载Android SDK,点击安装,直接默认路径即可! 下载地址:http://developer.android.com/sdk/index.html 2、默认路径安装后,安装完成,开始配置环境变量。 3、打开计算机属性——高级系...

阿豪boy ⋅ 28分钟前 ⋅ 0

bash shell script 简明教程

User <--> bash <--> kernel shell is not kernel or part of kernel various shells: tcsh, csh, bash, ksh find the using shell: echo $SHELL find all the shells: cat /etc/shells what......

mskk ⋅ 30分钟前 ⋅ 0

Service Mesh简史

William Morgan Service Mesh是一个相当新的概念,讲它的“历史”似乎有些勉强。就目前而言,Service Mesh已经在部分企业生产环境中运行了超过18个月,它的源头可以追溯到2010年前后互联网公...

好雨云帮 ⋅ 30分钟前 ⋅ 0

10个免费的服务器监控工具

监控你的WEB服务器或者WEB主机运行是否正常与健康是非常重要的。你要确保用户始终可以打开你的网站并且网速不慢。服务器监控工具允许你收集和分析有关你的Web服务器的数据。 有许多非常好的服...

李朝强 ⋅ 43分钟前 ⋅ 0

压缩工具之zip-tar

zip 支持目录压缩。使用yum安装zip包,使用yum安装unzip包 zip 1.txt.zip 1.txt #将1.txt文件压缩,新生成的压缩文件为1.txt.zip,原文件保留 zip -r 123.zip 123/ #-r对目录操作。将123/目录...

ZHENG-JY ⋅ 43分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部