1670人阅读
1、原始题目 & & & &
& & & & 看到一道大家讨论的比较老的算法面试题，说是字符串pStr，其中包含有大括号“{&&&&}&&&中括号&[&&&]&&小括号&&(&&&)&试编写一个递归函数，判断表达式中的括号是否匹配，返回true或者false。这道题之前自己准备面试的时候也做到过，好像是Catalan数的一个应用，用一个栈还是能很好地实现的，博主的代码如下。
#include &vector&
bool isMatch(const char* pStr)
const char* p = NULL;
vector&char& S
(*p != '{') && (*p != '}')
&& (*p != '[') && (*p == ']')
&& (*p != '(') && (*p != ')')
if (Stack.empty())
return (false);
p++;
else if ((*p == '{') && (*p != '[') && (*p != '('))
Stack.push_back(*p);
p++;
else if ((*p == '}') && (*p != ']') && (*p != ')'))
char c = '\0';
if (Stack.empty())
return (false);
c = Stack[Stack.size() - 1];
('{' == c) && (*p == '}')
|| ('[' == c) && (*p == ']')
|| ('(' == c) && (*p == ')')
Stack.pop_back();
p++;
return (false);
return (Stack.empty());
int main()
const char *p = &{}&;
printf(&%s\n&, isMatch(p)? &True&: &False&);
getchar();
2、附加要求
& & & & 但是最近看到的要求是用递归写，整个实现不可以出现一个循环语句，大家有什么好的想法吗，我看了一部分童鞋的讨论，也粘贴在下面了。
@：这个问题用到一个性质:左数第一个右括号的左邻括号，正是右括号的匹配括号。因此递归函数可以有两个参数:左括号栈，余下数组。每次递归取余下数组的首项，如果是左括号则进左括号栈;如果是右括号则左括号栈顶出栈;继续递归直到两个参数都空为止，此时输出yes，否则输出no
n的复杂度上限。
@：尾递归+stack，O(n)&
@：感觉像是Catalan数的应用，任何一个时刻左括号的数目不应该小于右括号的数目，那维护一个变量，初始为0，判断当前字符，为左括号则变量+1，否则-1，变量减小到负数则直接退出，否则下标加一，传参递归。
3、题目扩展
& & & & 这道变种题大多数人的解题思路都是动态规划，思路如下。不知道大家有没有好的别的方法，求教。
& & &1）用 dp[i][j] 表示从位置 i &到字符位置 j 所需的最少括号数。假定字符串是 “[ ( )”, 那么 dp[0][0] = dp[1][1] &= dp[2][2] = 1。
& & 2）如果我们要算dp[i][j+1], 那么，最坏的情况是使得没有被匹配的括号数增加了，即 dp[i][j+1] 最多为 min( dp[i][j] + 1,
dp[i+1][j+1] + 1). 但是，这可能不是我们想要的答案，因为在刚才的例子里，即：假定字符串是 “[ ( )”, 那么
dp[0][1] =&dp[0][0] + 1= 2， 但是&dp[1][2] 却不等于&dp[1][1]
& & 3）那么，什么情况下dp[i][j+1] =&dp[i][j] + 1？只有当 字符串里从i 到 j 没有任何字符与第 j + 1 个字符匹配的时候。但是，如果存在和第 j + 1 个字符匹配的情况，问题就不一样了。
& & 4）假设在i 到 j 之间存在一个字符（比如在位置 k）与第 j + 1 个字符匹配，那么我们相当于把原来的字符串分成了两个部分dp[i][k-1] 和
dp[k+1][j], 因为第k 个 和 j + 1 个字符已经匹配掉了。而且，我们不会再考虑 i 到 k - 1 的字符会和 k + 1 到 j 之间的字符匹配的情况，因为我们已经把这两个部分完全分开了。话句话说
dp[i][j+1] = min(min(&dp[i][j] + 1,
dp[i+1][j+1] + 1), &dp[i][k-1] +
dp[k+1][j]).
#include&iostream&
#include&string&
#include&memory.h&
bool is(char a, char b){
if(a == '(' && b == ')')
if(a == '[' && b == ']')
if(a == '{' && b == '}')
int main(){
//dp[i][j] 表示从第i位至第j位的最小匹配长度
int t, i, j, k, dp[105][105];
while(t--){
memset(dp, 0, sizeof(dp));
for(i = 0; i &= s.length(); ++i){
dp[i][i] = 1;
for(i = 2; i &= s.length(); ++i){
for(j = i - 1; j &= 1; --j){
dp[j][i] = dp[j][i - 1] + 1;
for(k = k & ++k){
if(is(s[k - 1], s[i - 1])){
dp[j][i] = min(dp[j][i], dp[j][k - 1] + dp[k + 1][i - 1]);
cout && dp[1][s.length()] &&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1373413次
积分：10106
积分：10106
排名：第1322名
原创：98篇
评论：559条
海淀区『明光村计算机职业技能学校』烟酒僧毕业。有几年机器学习/数据挖掘工作经验。大厂打过杂，做过几个NLP、推荐系统、点击率预估、深度学习图像分类/检索相关项目。欢迎联系和交流。
EMAIL:hanxiaoyang.&
数据科学沙龙QQ群
2000人群(已满)2000人群(已满)2000人群不定期有机器学习/数据科学公开课和线上讨论
其余机器学习QQ群
(已满), (已满)，(已满)
阅读：130827
文章：25篇
阅读：477674
文章：11篇
阅读：261823
(1)(4)(6)(1)(4)(5)(2)(2)(6)(11)(2)(6)(2)(2)(26)(21)千里之行 始于足下精诚所至 金石为开
欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 1298 人关注过本帖
标题：今天做oj碰到这道题，17的倍数，参考了一下网上的解题方法还是通不过，求指 ...
来　自：毛里求斯
等　级：新手上路
&&问题点数：0&&回复次数：6&&&
今天做oj碰到这道题，17的倍数，参考了一下网上的解题方法还是通不过，求指导
&定理：把一个至少两位的正整数的个位数字去掉，再从余下的数中减去个位数的5倍。当且仅当差是17的倍数时，原数也是17的倍数 。
例如，34是17的倍数，因为3-20=-17是17的倍数；201不是17的倍数，因为20-5=15不是17的倍数。输入一个正整数n，你的任务是判断它是否是17的倍数。
输入文件最多包含10组测试数据，每个数据占一行，仅包含一个正整数n（1&=n&=10^100），表示待判断的正整数。n=0表示输入结束，你的程序不应当处理这一行。
对于每组测试数据，输出一行，表示相应的n是否是17的倍数。1表示是，0表示否。
#include&stdio.h&
#include&string.h&
int main()
&&& char str[1001];
&&& int t,a,b,c,d,e,i;
&&& while(gets(str)!=NULL)
&&&&&&&&if(str[0]=='0') return 0;
&&&&&&&&t=strlen(str);
&&&&&&&&while(t&3)
&&&&&&&&&&&&d=(str[t-1]-'0')*5;
&&&&&&&&&&&&c=(str[t-2]-'0');
&&&&&&&&&&&&b=(str[t-3]-'0')*10;
&&&&&&&&&&&&a=(str[t-4]-'0')*100;
&&&&&&&&&&&&e=a+b+c-d;
&&&&&&&&&&&&str[t-2]=e%10+'0';
&&&&&&&&&&&&str[t-3]=e/10%10+'0';
&&&&&&&&&&&&str[t-4]=e/100+'0';
&&&&&&&&&&&&t--;
&&&&&&&&for(e=0,i=0;i&=t-1;i++)
&&&&&&&&&&&&e=e*10;
&&&&&&&&&&&&e=e+(str[i]-'0');
&&&&&&&&if(e%17==0)
&&&&&&&&printf(&1\n&);
&&&&&&&&else
&&&&&&&&printf(&0\n&);
&&& return 0;
#include&stdio.h&
int main()
&&& char a[1001];
&&& int n,b[1001],i,j,e;
&&& while(gets(a)!=NULL)
&&&&&&&&if(a[0]=='0') return 0;
&&&&&&&&for(i=0,n=0;a[i]!='\0';i++)
&&&&&&&&&&&&b[i]=a[i]-'0';n++;
&&&&&&&&j=b[0];
&&&&&&&&for(i=1;i&n;i++)
&&&&&&&&&&&&e=j*10+b[i];j=e%17;
&&&&&&&&if(j==0) printf(&1\n&);
&&&&&&&&else printf(&0\n&);
&&& return 0;
希望各位能给我讲讲哪里出问题了，谢谢0.0
搜索更多相关主题的帖子:
等　级：版主
威　望：189
帖　子：4425
专家分：23554
原题的算法太慢，可以作弊一下，形如
从左到右不停的模除17，余数保留作为新的头，最后有剩余则不是17的倍数
等　级：版主
威　望：189
帖　子：4425
专家分：23554
“通不过”是什么意思呀，为什么不愿意将问题描述清楚？
你这里有两段代码，那我问你：
a. 哪段代码是你的，哪段是别人的？或者说 你需要别人替你查哪段代码的错误？
b. 你提交的是哪段代码？抑或是两段代码同时提交上去了？
c. 你提交代码后，OJ告诉你是编译链接错误呢，还是测试不能通过？
来　自：毛里求斯
等　级：新手上路
首先感谢帮忙，两个都提交了都是答案错误，第二个代码的思路是根据模拟除法做的，还是错了
这是oj给的
=================/1003.out
-----------------
=================
辅助解释：
/**************************************************************
&&& Problem: 1003
&&& Language: C
&&& Result: 答案错误
****************************************************************/
Hello world!
等　级：版主
威　望：189
帖　子：4425
专家分：23554
看不出有什么问题，看来看去，只有题目中的“n=0表示输入结束”你用的是“if(a[0]=='0') return 0;”，不怎么符合题目要求。
我改一下吧
程序代码：#include &stdio.h&
int main( void )
&&& // tip: 10^100需要101个字符，加上'\0'，所以共需102
&&& //&&&&&&gets已经被C语言废弃，所以我用scanf
&&& for( char s[<font color=#]; scanf(&%s&,s)==<font color=# && !(s[<font color=#]=='<font color=#' && s[<font color=#]=='<font color=#'); )
&&&&&&&&unsigned r = <font color=#;
&&&&&&&&for( size_t i=<font color=#; s[i]!='<font color=#'; ++i )
&&&&&&&&&&&&r = (r*<font color=#+s[i]-'<font color=#')%<font color=#;
&&&&&&&&printf( &%d\n&, r==<font color=# );
&&& return <font color=#;
来　自：毛里求斯
等　级：新手上路
十分感谢，我把gets改成scanf过了！！
Hello world!
等　级：新手上路
程序代码：/*
把一个至少两位的正整数的个位数字去掉，
再从余下的数中减去个位数的5倍。
当且仅当差是17的倍数时，原数也是17的倍数 。
34是17的倍数，因为3-20=-17是17的倍数；
201不是17的倍数，因为20-5=15不是17的倍数。
输入一个正整数n，你的任务是判断它是否是17的倍数。
输入文件最多包含10组测试数据，
每个数据占一行，仅包含一个正整数n（1&=n&=10^100），
表示待判断的正整数。
n=0表示输入结束，你的程序不应当处理这一行。
对于每组测试数据，输出一行，表示相应的n是否是17的倍数。1表示是，0表示否。
34=&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&1
3-4*5=-17&&&&&&&&&&&&&&&&&&&&&&&&&&&&&1
201=&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 0
20-5=15&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 0
1-25=-24&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&0
=&&&&&&&&&&&&&&&&&&&&&&&&&&&1
=&&&&&&&&&&&&&&& 1
=&&&&&&&&&&&&&&&&&&1
=2098752&&&&&&&&&&&&&&&&&&&&1
=209865&&&&&&&&&&&&&&&&&&&&& 1
61&&&&&&&&&&&&&&&&&&&&&&&&1
1&&&&&&&&&&&&&&&&&&&&&&&&&&&1
209-5=204&&&&&&&&&&&&&&&&&&&&&&&&&&&&&1
20-20=0&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 1
&&&&&&&&&&&&&&&
#include&iostream&
#include&cstring&
#include&cmath&
using namespace
int shiqi(char a[])
&&& int n,m,x,t,mop,p;
&&& n=strlen(a);
&&& if(n&<font color=#)&&//长度大于1&&就是2位数以上
&&&&&&&&n=n-<font color=#;
&&&&&&&&//我提取 最小的一位数字 并把他乘5
&&&&&&&&m=a[n]-'<font color=#';
&&&&&&&&m=m*<font color=#;
&&&&&&&&//我也要适当 提取 后面的数字
&&&&&&&&p=<font color=#;
&&&&&&&&x=<font color=#;
&&&&&&&&t=<font color=#; //这个用于记录我提取了几位
&&&&&&&&while(fabs(x)&=fabs(m))
&&&&&&&&&&&&x=x+p*(a[n-t]-'<font color=#');
&&&&&&&&&&&&p=p*<font color=#;
&&&&&&&&&&&&if(n-t==<font color=#) break;
&&&&&&&&&&&&t++;
&&&&&&&&t--;
&&&&&&&&//现在好了 我算下 后t位的 相剪的数字
&&&&&&&&x=x-m;&&//x是最后的几位(t位)
&&&&&&&&//一共提取了t位
&&&&&&&&// x=123&&t=3&&我要提取 1&&& x/100=1&&&x=x%100 =23
&&&&&&&&// x=23&&&t=2&&我要提取 2&&& x/10 =2&&&x=x%10 =3
&&&&&&&&// x=3&&& t=1&&我要提取 3&&& x/1
&&&&&&&&//x
&&&&&&&&int
&&&&&&&&if(n==<font color=#) t++;
&&&&&&&&mop=pow(<font color=#,t-<font color=#);
&&&&&&&&for(xx=n-t;t&<font color=#;t--,xx++)
&&&&&&&&&&&&if(mop==<font color=#) mop=<font color=#;
&&&&&&&&&&&&a[xx]=x/mop+'<font color=#';
&&&&&&&&&&&&x=x%
&&&&&&&&&&&&mop=mop/<font color=#;
&&&&&&&&a[n]=<font color=#;
&&&&&&&&return shiqi(a);
&&&&&&&&x=<font color=#;
&&&&&&&&x=(a[<font color=#]-'<font color=#')*<font color=#+(a[<font color=#]-'<font color=#');
&&&&&&&&return
int main(){
&&& char a[<font color=#][<font color=#]={<font color=#};
&&& int i,j;
&&& for(i=<font color=#;i&<font color=#;i++)
&&&&&&&&gets(a[i]);
&&&&&&&&if(strcmp(a[i],&<font color=#&)==<font color=#) break;
&&& for(j=<font color=#;j&i;j++)
&&&&&&&&if(shiqi(a[j])%<font color=#==<font color=#) cout&&<font color=#&&
&&&&&&&&else cout&&<font color=#&&
&&& return <font color=#;
版权所有，并保留所有权利。
Powered by , Processed in 0.054529 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved后使用快捷导航没有帐号？
查看: 1881|回复: 9
在线时间 小时
1& &If 1050 – 74 is written as an integer in base 10 notation, what is the sum of the digits in that integer?
A.& & & & 424
B.& & & & 433
C.& & & & 440
D.& & & & 449
E.& & & & 467
In the xy-plane, point (r, s) lies on a circle with center at the origin.&&What is the value of r2 + s2?
(1)& & & && &The circle has radius 2.
(2)& & & && &The point (√2, -√2) lies on the circle.
A. Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.
B. Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.
C. BOTH statements TOGETHER are sufficient, but NEITHER statement ALONE is sufficient.
D. EACH statement ALONE is sufficient.
E. Statements (1) and (2) TOGETHER are NOT sufficient.
答案是D&&我选了E&&（2）只是说那个点在圆上，那圆的位置可以有好几个啊~怎么就能和（1）一起确定题干呢？
3 A photographer will arrange 6 people of 6 different heights for photograph by placing them in two rows of three so that each person in the first row is standing in f&&ront of someone in the second row.&&The heights of the people within each row must increase from left to right, and each person in the second row must be taller than the person standing in front of him or her.&&How many such arrangements of the 6 people are possible?
A.& & & & 5
B.& & & & 6
C.& & & & 9
D.& & & & 24
E.& & & & 36
答案是A&&我选了B&&我是用列举法&&如果6个人身高用1-6表示，则第二排第一排战法分别由： 456 123& & 256 134& &356 124& &256 134& & 246 135&&346 125
有更简便的方法吗？我上面列举的有哪个不对吗？
4 If n = 811 – 8, what is the units digit of n?
A.& & & & 0
B.& & & & 1
C.& & & & 4
D.& & & & 6
E.& & & & 8
这种位数题要怎么做呢？答案是C
Joanna bought only $0.15 stamps and $0.29 stamps.&&How many $0.15 stamps did she buy?
(1)& & & && &She bought $4.40 worth of stamps.
(2)& & & && &She bought an equal number of $0.15 stamps and $0.29 stamps.
A. Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.
B. Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.
C. BOTH statements TOGETHER are sufficient, but NEITHER statement ALONE is sufficient.
D. EACH statement ALONE is sufficient.
E. Statements (1) and (2) TOGETHER are NOT sufficient.
答案是1&&可我觉得两个条件都用上 0.15X+0.29X=4.4&&X 可以的出来啊~
A positive integer n is said to be “prime-saturated” if the product of all the different positive prime factors of n is less than the square root of n.&&What is the greatest two-digit prime-saturated integer?
A.& & & & 99
B.& & & & 98
C.& & & & 97
D.& & & & 96
E.& & & & 95
答案是D&&关键是& if the product of all the different positive prime factors “这个是指所有质数因子还是所有质数因子的和啊？
A jar contains 16 marbles, of which 4 are red, 3 are blue, and the rest are yellow.&&If 2 marbles are to be selected at random from the jar, one at a time without being replaced, what is the probability that the first marble selected will be red and the second marble selected will be blue?
A.& & & & 3/64
B.& & & & 1/20
C.& & & & 1/16
D.& & & & 1/12
E.& & & & 1/8
答案是B&&我觉得不是4/16&&*&&3/12=1/16& &吗？
谢谢各位~~
在线时间 小时
第一个题是10^50 - 74这样吧 =99999....926 所以是48*9+2+6=440
在线时间 小时
moreday 发表于
第一个题是10^50 - 74这样吧 =99999....926 所以是48*9+2+6=440
哦！~谢谢~一开始我不理解那个in base 10 notation的意思~
在线时间 小时
第三题你写了两遍256 134这个可能。最后一题应该是4/16*3/15 = 1/20
在线时间 小时
第四题是8^11-8? 8得一次方个位是8，2次方个位是4。。以此类推个位的循环就是8，4，2，6，所以8的11次方的个位就是2。然后再用2减8就等于4了
在线时间 小时
<font color="#13GMAT 发表于
第三题你写了两遍256 134这个可能。最后一题应该是4/16*3/15 = 1/20
哦对~我犯低级错误了~
在线时间 小时
第二题 圆的公式 r^2+s^2=半径的平方。1 告诉你了半径，2 告诉你了一点可以算出半径，所以就都sufficient。
在线时间 小时
<font color="#13GMAT 发表于
第四题是8^11-8? 8得一次方个位是8，2次方个位是4。。以此类推个位的循环就是8，4，2，6，所以8的11次方的 ...
在线时间 小时
楼主做题一定要仔细看清楚题目啊。。。不然亏大了。。。
第二题：题目说了圆心在原点，所以（2）就有半径了。
第五题：我第一次做prep也被骗了，其实（1）以及题目的数值很巧的，x、y都要是整数。
式子化简是：15x+29y=440，15x的尾数必为5或0，要配合440的和，29y的尾数也要是5或0，所以y 的取值可以是5或10；再计算x，若y为5，则15x为295，x 不是整数；若y为10，x为10，刚刚好。所以（1）够了。
第六题：the product of all the different positive prime factors of n 是指“n所有不同质因子的乘积”，先把选项因数分解再乘一下就行了。一定是小于10的才可以选。
在线时间 小时
pisco 发表于
楼主做题一定要仔细看清楚题目啊。。。不然亏大了。。。
第二题：题目说了圆心在原点，所以（2）就有半径了 ...
嗯?这几题很多都是自己没看清题干导致的?上午做题太浮躁?thx?
所属分类: GMAT考试
正在浏览此版块的会员 ()
ChaseDream 论坛
All Rights Reserved.小木虫 --- 500万硕博科研人员喜爱的学术科研平台
&&查看话题
【求助】求一道数值分析题的解法！
设B点是线段AC上的一点，记AB长为x1，BC长为x2，经测量得数据如下：
AB=15.5，BC=6.1，AC=20.9
试合理确定出 x1，x2的长度。
是欧氏空间R2中的三个点还是球面上的三个点
研究生必备与500万研究生在线互动！
扫描下载送金币
浏览器进程
打开微信扫一扫
随时随地聊科研}