阅读 31632 次
发表时间:2010-07-21
1。逆波兰表达式

ps:如果有javascript,直接eval執行表達式即可

2。暴力破解就行了
发表时间:2010-07-21
第二题其实就用一个for循环,从100到333。然后分别乘以2跟3,再把得到的数,进行字符串合并进行判断,如果符合就输出出来。叫我在短时间内要弄出来的话,我就会这样子来处理。楼主的说的样子的规律不是不对。如果在短时间内你要按着那样子的规律来弄,个人觉得不可能。我觉得这样子在短时间内最快的。

其实再认真考虑一下。因为每个数字只能重复出现一次,并且又得是三位的数字,所以这个循环在范围是在123到321里。其实还可以再缩小一点。没有必要再去进行人工的判断了,这个循环也不是很多。能很快就处理出来了的。
发表时间:2010-07-21
aabcc 写道
leon_a 写道
第一个,逆波兰表达式
http://leon-a.iteye.com/blog/186104

第二题,由于java在1秒内运算的数量级大概是10^9,所以纯暴力就可以了
package test;

public class Main {

	String[] nums = new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
	boolean[] visable = new boolean[] { false, false, false, false, false, false, false, false, false };

	public void check() {
		for (int i = 0; i < nums.length; i++) {
			for (int j = 0; j < nums.length; j++) {
				for (int k = 0; k < nums.length; k++) {
					if (!nums[i].equals(nums[j]) && !nums[i].equals(nums[k]) && !nums[j].equals(nums[k])) {
						Integer num = new Integer(nums[i] + nums[j] + nums[k]);
						Integer num2 = num * 2;
						Integer num3 = num * 3;
						visable[i] = true;
						visable[j] = true;
						visable[k] = true;
						String str = num2.toString() + num3.toString();
						if (str.length() == 6) {
							if (isUnique(str)) {
								System.out.println(num + "," + num2 + "," + num3);
							}
						}
						resetVisable();
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		m.check();

	}

	public void resetVisable() {
		for (int i = 0; i < visable.length; i++) {
			visable[i] = false;
		}
	}

	public boolean isUnique(String str) {
		String[] strs = str.split("");
		for (int i = 0; i < strs.length; i++) {
			for (int j = 0; j < nums.length; j++) {
				if (strs[i].equals(nums[j])) {
					if (!visable[j]) {
						visable[j] = true;
					} else {
						return false;
					}

				}
			}
		}
		return true;
	}

}




逆波兰表达式,怀念啊,读书的时候根本不知道这个有什么用
for (int i = 0; i <3; i++) {
			for (int j = 0; j < nums.length; j++) {

这样好多了
发表时间:2010-07-21
Enn 写道
eval飘过……

你太邪恶了。不过如果用eval的话,太危险了,别人给你输入个rm *,不就挂了。eval也没办法检查表达式的正确性。
>> eval('2*3*4+(2+(2+3)*2)/2')
=> 30

用逆波兰吧。
第二个暂时没想好,有些复杂。暴力破解可以,不过应该有更好点的。
发表时间:2010-07-21
biaobiao520 写道
第一个:写一个方法,参数传递一个字符串表达式,返回结果为表达式计算结果。如:传递表达式"1+2*3+6-2/2"返回计算的结果。

第二个:9个数1-9组成三个数,如:327 654 981,每个数字只能用一次,每三个数字组成一个新的数字,第二个数是第一个数的两倍,第三个数是第一个数的三倍,用程序实现。

我的实现:
第一个:把传进来的字符串解串,用了以个while循环,只要碰到"+","-","*","/"就记录符号的index,计算index两边的值,然后再组成新的字符串返回,当字符串的长度为一的时候,就是最后的值。因为当时时间紧急,考虑的不是很全面。

第二个:用程序实现不了,但总结了三点规律:
1、三个数的百位数必须是倍数关系 如327 654 981 和 219 438 657 百位数分别为3 6 9和2 4 6
2、三个数的十位数必须均值递增,如上十位数为别为2 5 8和1 3 5
3、三个数的个位数必须均值递减,如上个位数分别为7 4 1和9 8 7

请教大家评论及指点!



首先,1+2*3+6-2/2我们知道二叉树的中序遍历。然后使用后序遍历就变成了逆波兰。就是123*+622/-+
把逆波兰的串压入栈,就是
遇到计算符号就弹出栈的最高两位进行计算。
                 /
       *       2 2 -
     3 3 +   2 2 2 1 +
  2  2 2 6 6 6 6 6 6 5
1 1  1 1 1 7 7 7 7 7 7 12

只要处理好中序和后序遍历就可以了,编程需要花点时间。

第二道题目
我也想到穷举法,当然能找到规律的话,就能让穷举的范围更小的一点,但是首先要保证规律的正确性。
这样的规律能找到越多,需要遍历的数字就越少,效果越好。
大的步骤是:
1.列出所有可能的第一个数
2.根据第一个数得到第二个以及第三个数的值
3.根据3个数值的9个数字,判断是否有重复的数字,没有重复的数字就是我们要的结果

第一个数的百位肯定是123之间选择,如果是4,那么第三个数将超过1000.
十位如果在百位是3的时候,可能不会是3,也不能比3大,所以只能是1和2.
也就是32*, 31*, 1**, 2** 是保证第一个数是正确的。
32* 有9-2=7种可能
31* 有7种可能
1** 有8 * 7=56种可能
2** 有56种可能

也就是需要for 7 + 7 + 56 + 56 = 126
当然列出所有的可能性也是需要一个程序完成的。可以编写另外的一个函数调用,也许想修改列出的算法也方便点。

对第一个数字乘以2,得到第二个数字
对第一个数字乘以3,得到第三个数字
这时候就有9个数字,接下去要做的就是判断这些数字里面是否有重复的,如果没有重复的就是想要的结果之一。

如何判断是否有重复的数字呢?
1. 用1-9遍历9个数字,如果发现有个数字找到两次,马上停止返回。9个数字遍历9遍。当然前面三位例如321,肯定是不会重复的,在比较3,2,1的时候可以跳过前面3个数字,但是这样算法就复杂了,也不能节省多少的时间。
2. 排序,然后两两比较是否相等
3. 用9个int型的数组,遍历一遍9个数字就可以,如果遍历到是1,那么置数组0位为1,遍历到2,那么置数组1位为1,如果发现本来已经是1了,那么就表示重复,这个需要9个int的空间,只需要遍历一次,比较也是判断是否为1.
发表时间:2010-07-21
第一题显然是编译原理题
词法分析然后递归下降
当然你如果熟悉javacc antlr会很快

第二题暴力+优化(比如第一个数不可能大于250)

这两道题能在三个小时内做对的不多
发表时间:2010-07-21
   ScriptEngine jse = new ScriptEngineManager().getEngineByName("JavaScript");

        System.out.println(jse.eval("1+2*3+6-2/2"));
发表时间:2010-07-21
ytsmtxxi 写道
第二题其实就用一个for循环,从100到333。然后分别乘以2跟3,再把得到的数,进行字符串合并进行判断,如果符合就输出出来。叫我在短时间内要弄出来的话,我就会这样子来处理。楼主的说的样子的规律不是不对。如果在短时间内你要按着那样子的规律来弄,个人觉得不可能。我觉得这样子在短时间内最快的。

其实再认真考虑一下。因为每个数字只能重复出现一次,并且又得是三位的数字,所以这个循环在范围是在123到321里。其实还可以再缩小一点。没有必要再去进行人工的判断了,这个循环也不是很多。能很快就处理出来了的。

这个确实比较好!!!
发表时间:2010-07-21
wanghe 写道
   ScriptEngine jse = new ScriptEngineManager().getEngineByName("JavaScript");

        System.out.println(jse.eval("1+2*3+6-2/2"));

这个快!!!!!!!
发表时间:2010-07-21
wanghe 写道
   ScriptEngine jse = new ScriptEngineManager().getEngineByName("JavaScript");

        System.out.println(jse.eval("1+2*3+6-2/2"));


这也太牛了,学习了

 

Global site tag (gtag.js) - Google Analytics