<以下微软面试题全来自网络>
<以下答案与分析纯属个人观点,不足之处,还望不吝指出^_^>
<出处:http://blog.csdn.net/zhanxinhang>
题:1、如何判断一个字符串是对称的?如a,aa,aba。
2、如何利用2函数找出一个字符串中的所有对称子串?
分析:
且看第一个问题判断字符串对称,有以下两种方法。
方法一、使迭代器p1指向头,p2指向尾。使p1,p2相对而行(—> | <—),每次比较p1,p2是否相等,直到它们相遇。
方法二、使p1、p2指向中间的一个元素(如果字符串长度为偶数的话就指向中间两个相邻的元素),使它们相向而行(<— |—>),每次比较p1,p2是否相等。直到它们一个指向头一个指向尾便结束。
(可以看出方法1明显好于方法2)
现在看第二个问题打印所有的对称子串,判断对称子串的问题我们似乎已经解决,且有以上两种方法,针对现在的情况是否两种都合适呢,确切的说不是。如果是方法一,请想象一下,如果要p1,p2一个指向子串的头一个指向子串的尾,那么至少要两层循环一层控制p1一层控制p2,还有一层循环用于判断子串是否对称,也就是说总共需要三层嵌套循环,时间复杂度指数为3。而如果选择方法二呢? 两层循环就能实现,不过要适应现在这种情况需要做些修改,就是针对偶数长度的子串进行一次遍历,再针对奇数长度的子串进行一次遍历,也就是两层嵌套循环中内层有两次循环,时间复杂度指数为2。详情且看代码。
实现加测试代码:
- /**
- Author:花心龟
- Blog:http://blog.csdn.net/zhanxinhang
- **/
- #include <iostream>
- #include <cstdlib>
- #include <ctime>
- using namespace std;
- class App
- {
- typedef string::iterator Iter_t;
- string m_str;
- void print(Iter_t p1, Iter_t p2) //打印从p1开始到p2结束的字符
- {
- while(p1<=p2)
- {
- cout<<*p1;
- p1++;
- }
- cout<<" | ";
- }
- bool isHuiwen1(Iter_t start,Iter_t end) //法1判断是否为对称子串
- {
- Iter_t p1 = start;
- Iter_t p2 = end;
- int times = (distance(p1,p2)+1) / 2; //比较次数
- while(times)
- {
- if(*p1 != *p2)
- return false;
- p1++;
- p2--;
- times--;
- }
- return true;
- }
- bool isHuiwen2(Iter_t mid_it) //法2判断是否为对称子串
- {
- Iter_t p1,p2;
- p1 = p2 = mid_it;
- while(p1>=m_str.begin() && p2 < m_str.end())
- {
- if(*p1 != *p2)
- break;
- print(p1,p2);//打印从p1到p2的字符
- p1--,p2++;
- }
- p1 = p2 = mid_it;
- p2++; //使p2向前移动一个位置,此时p1,p2分别指向中间两个相邻位置
- while(p1>=m_str.begin() && p2 < m_str.end())
- {
- if(*p1 != *p2)
- return false;
- print(p1,p2);//打印从p1到p2的字符
- p1--,p2++;
- }
- return true;
- }
- void show_all_substr_of_huiwen1() //法一打印所有对称子串
- {
- Iter_t p2=m_str.end()-1;
- Iter_t p1 = m_str.begin();
- for(;p1!=m_str.end();p1++)
- for(p2=p1;p2!=m_str.end();p2++)
- {
- if(isHuiwen1(p1,p2))
- print(p1,p2);
- }
- }
- void show_all_substr_of_huiwen2() //法二打印所有对称子串
- {
- Iter_t it = m_str.begin();
- for(;it!=m_str.end();it++)
- {
- isHuiwen2(it);
- }
- }
- public:
- void run()
- {
- m_str="abaaba";
- cout<<"测试数据为:abaaba"<<endl;
- show_all_substr_of_huiwen1();
- cout<<endl;
- show_all_substr_of_huiwen2();
- cout<<endl;
- m_str="asdfie";
- cout<<"测试数据为:asdfie"<<endl;
- show_all_substr_of_huiwen1();
- cout<<endl;
- show_all_substr_of_huiwen2();
- cout<<endl;
- m_str="aabaa";
- cout<<"测试数据为:aabaa"<<endl;
- show_all_substr_of_huiwen1();
- cout<<endl;
- show_all_substr_of_huiwen2();
- cout<<endl;
- //时间比较//
- m_str="this is a string for testing. aabaa alskjdfkljasdjflasdflkajsldkjfsjlakjsdlfjwoekjlakjlsdkjflsajlkdjfowieuoriuq aaddbb sldjfalkjsdlfkjasldjflajsldfjalskdjflakjsdlfkjaslkdjflajsdlfkjaslkdjflkajsdlkjflkasjdlfjaklsjdkfljaklsdjfklsajdflkjslkdjflaskjdlfkjalsdjlfkajsldfkjlaksjdfljasldjflaskjdfkasjdflaksjdkfljaskldfjlaksjdfljasldjflaksjdkljfkalsjdlkfjasldjflasjdlfjasldjfklsajdfljaskldfjlsakjdflkasjdfkl this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k is is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.this is a string for testing.make -k make -k make -k make -k make -k make -k end";
- time_t start,record1;
- cout<<"show all substr of huiwen 1:";
- system("pause");
- start = time(NULL);
- show_all_substr_of_huiwen1();
- record1 = time(NULL);
- cout<<endl;
- cout<<"time:"<<record1-start;
- cout<<endl;
- cout<<"show all substr of huiwen 2:";
- system("pause");
- start = time(NULL);
- show_all_substr_of_huiwen2();
- record1 = time(NULL);
- cout<<endl;
- cout<<"time:"<<record1-start;
- cout<<endl;
- cout<<"(可以看到打印速度明显快于上一次)";
- }
- };
- int main()
- {
- App myapp;
- myapp.run();
- system("pause");
- return 0;
- }
测试结果:
各测试数据下的一二行为打印出来的所有对称字串。
按下任意键后:
以上是使用方法1打印出来的结果。
按下任意键后:
以上便是用方法2打印出来的结果。
每日微软面试题——day 6(打印所有对称子串)的更多相关文章
-
每日三道面试题,通往*的道路6——JVM
茫茫人海千千万万,感谢这一秒你看到这里.希望我的面试题系列能对你的有所帮助!共勉! 愿你在未来的日子,保持热爱,奔赴山海! 每日三道面试题,成就更好自我 今天我们继续聊聊JVM的话题吧! 1. 那你知 ...
-
《剑指offer》面试题12:打印1到最大的n位数
面试题12:打印1到最大的n位数 剑指offer题目12,题目如下 输入数字n,按顺序打印出1到最大的n位十进制数,比如输入3,则打印出1,2,3一直到最大的三位数999 方法一 和面试题11< ...
-
【面试题012】打印1到最大的n位数
[面试题012]打印1到最大的n位数 大数问题 字符串中的每一个字符都是‘0’到‘9’之间的某一个字符,用来表示数字中的一位,因为数字最大是n位的,因此我们需要一个长度为n+1的字符串,字符串的最后 ...
-
【剑指offer】面试题 29. 顺时针打印矩阵
面试题 29. 顺时针打印矩阵 题目描述 题目:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
-
面试题17:打印1到最大的n位数
// 面试题17:打印1到最大的n位数 // 题目:输入数字n,按顺序打印出从1最大的n位十进制数.比如输入3,则 // 打印出1.2.3一直到最大的3位数即999. 解题思路: 首先是一个大陷阱,n ...
-
每日三道面试题,通往*的道路5——JVM
茫茫人海千千万万,感谢这一秒你看到这里.希望我的面试题系列能对你的有所帮助!共勉! 愿你在未来的日子,保持热爱,奔赴山海! 每日三道面试题,成就更好自我 昨天既然我们聊到了JVM,那我们继续这一个话题 ...
-
每日三道面试题,通往*的道路4——JVM篇
茫茫人海千千万万,感谢这一秒你看到这里.希望我的面试题系列能对你的有所帮助!共勉! 愿你在未来的日子,保持热爱,奔赴山海! 每日三道面试题,成就更好自我 昨天既然你有讲到字符串常量池是吧,那这样吧 1 ...
-
每日三道面试题,通往*的道路10——JMM篇
茫茫人海千千万万,感谢这一秒你看到这里.希望我的面试题系列能对你的有所帮助!共勉! 愿你在未来的日子,保持热爱,奔赴山海! 每日三道面试题,成就更好自我 今天我们还是继续聊聊多线程的一些其他话题吧! ...
-
每日三道面试题,通往*的道路13——锁+Volatile
茫茫人海千千万万,感谢这一秒你看到这里.希望我的面试题系列能对你的有所帮助!共勉! 愿你在未来的日子,保持热爱,奔赴山海! 每日三道面试题,成就更好自我 我们既然聊到了并发多线程的问题,怎么能少得了锁 ...
随机推荐
-
javascript基础05
javascript基础05 1.变量的作用域 变量既可以是全局,也可以是局部的. 全局变量:可以在脚本中的任何位置被引用,一旦你在某个脚本里声明了全局变量,你就可以 在这个脚本的任何位置(包括函数内 ...
-
mysql 总结二(自定义函数)
本质:mysql内置函数的一种扩展,本质上与mysql内置函数一样. 函数必要条件: @1:参数(非必备): @2:返回值: 模板: create function function_name ret ...
-
HQL 参数绑定、唯一结果、分页、投影总结(上)
我们先总结一下HQL语句常用语法: from子句:; select子句:用于选取对象和属性; where子句:用于表达查询语句的限制条件; 使用表达式:一般用在where子句中; order by子句 ...
-
网络基础知识系列:阐述VLAN和Trunk
网络性能是影响的效率的重要因素. 大的广播域分割方法,旨在提高网络性能.一个接口上,可是,路由器的LAN接口数量有限,它的主要功能是在网络间数据传输,而不是对终端设备提供网络接入. 訪问LAN的功能还 ...
-
Java中的五种单例模式实现方法
[代码] Java中的五种单例模式实现方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2 ...
-
An abandoned sentiment from past
An abandoned sentiment from past time limit per test 1 second memory limit per test 256 megabytes in ...
-
分享一个好用的微信npmjs包
https://www.npmjs.com/package/jquery_wechat_sdk 安装 $ npm install jquery_wechat_sdk 使用 Browser Script ...
-
服务器配置用户信息、ssh免密码登录和防火墙等安全配置
一.登录服务器 1.回到根目录 cd ~ 2.ssh + 用户名@服务器公网地址 ssh root@47.94.208.76 3.输入密码:注意输入法大小写 二.查看服务 ...
-
Android-LruCache与DiskLruCache
Android LruCache与DiskLruCache 学习自 Android开发艺术探索 https://blog.csdn.net/guolin_blog/article/details/28 ...
-
DirectUI消息循环的简单封装
一.真窗体和假窗体 首先在DirectWindow内部创建一个真窗体(基于WTL),可以接收消息 class CMessageWindow : public CWindowImpl< CMe ...