print 两指针 结构 == 输出结果 com 英文 在一起
三道题目基本上都和字符串操作相关。
1. 给定一组元素个数不定的字符串数组,每个字符串的长度不定;请统计出该字符串数组中的英文字母子串、数字子串和其他字符子串的总数; 输出为以 "," 符号分隔 3 个数值,分别代表英文字母子串、数字子串和其他字符子串的数量; 实现时无需考虑非法输入。
输入描述:
输入为:
字符串数组
例子:abcd1244!! BKMKLK0987%
输出描述:
输出为以 "," 符号分隔 3 个数值,分别代表英文字母子串、数字子串和其他字符子串的数量。
输入例子:
abcd1244!! BKMKLK0987%
输出例子:
2,2,2
思路:从左往右扫描输入字符串,利用两指针指向字符串的开始两个字符,往后递增,每一个步判断两指针所指的字符是否相同,如果不相同,则将后一个指针所指的字符类型所对应的字符字串计数器加 1.
代码:
- #include
- #include<string>using namespace std;
- boolisSameType(char*p1,char*p2);
- int main()
- {
- string str;
- cin>>str;
- intalpha=0;
- intdigi=0;
- intrest=0;
- intn=str.size();
- if(n==0){
- return 0;
- }else if(n==1){
- if((str[0]>='a'&&str[0]<='z')||(str[0]>='A'&&str[0]<='Z')){
- cout<<"1,0,0"<<endl;
- }else if(str[0]>='0'&&str[0]<='9'){
- cout<<"0,1,0"<<endl;
- }else{
- cout<<"0,0,1"<<endl;
- }
- return 0;
- }
- /*初始前一个指针从空开始,第二指针指向字符串中的第一位,从左向右遍历,每次两个指针所指
- 向的字符类型不同时,判断第二个指针所指字符的类型,将相应的计数器加1*/
- char*p1=NULL;
- char*p2=&str[0];
- for(inti=0;i1;){
- if(!isSameType(p1,p2)){
- if((*p2>='a'&&*p2<='z')||(*p2>='A'&&*p2<='Z')){
- alpha++;
- }else if(*p2>='0'&&*p2<='9'){
- digi++;
- }else{
- rest++;
- }
- }
- i++;
- p1=&str[i];
- p2=&str[i+1];
- }
- cout<","<","<endl;
- return 0;
- }
- boolisSameType(char*p1,char*p2)
- {
- int type1;
- int type2;
- if(p1==NULL){
- return false;
- }
- if((*p1>='a'&&*p1<='z')||(*p1>='A'&&*p1<='Z')){
- type1=0;
- }else if(*p1>='0'&&*p1<='9'){
- type1=1;
- }else{
- type1=2;
- }
- if((*p2>='a'&&*p2<='z')||(*p2>='A'&&*p2<='Z')){
- type2=0;
- }else if(*p2>='0'&&*p2<='9'){
- type2=1;
- }else{
- type2=2;
- }
- if(type1==type2){
- return true;
- }else{
- return false;
- }
- }
2. 输入一个字符串,对其进行逐词的反转后,然后返回。 比如:
输入:"the sky is blue"
输出:"blue is sky the"
注意: 1)"词" 是指:任何不含空格的连续字符串
2)输入字符串可以有首尾空格,但是返回的字符串不能有首尾空格
3)输入字符串中两个词之间可以有多个空格,但是返回的字符串中词只能用单个空格隔开
思路:利用栈的先进后出特性,从右往左倒序读取数组,如果是字母则入栈,遇到空格时将栈中所有字母弹出并输出,再输出一个空格,这里注意的是考虑到原字符串里可能有多个空格连在一起的情况,所以遇到空格出栈中字母之前需要判断此时栈是否为空。当然了,对原字符穿一开始还要去掉首位空格才行。
代码:
- importjava.util.*;
- public class Main{
- public static void main(String[] args){
- Scanner sc=new Scanner(System.in);
- String ss=sc.nextLine();
- ArrayList chr=newArrayList<>();
- char[] ch=ss.toCharArray();
- intn=ch.length;
- Stack stack=new Stack();
- if(n==0){
- return;
- }
- /*去首尾空格*/
- inti=0;
- /*这里要加上判断条件i<n,否则如果输入的全是空格的话数组会越界*/
- while(iCharacter.isSpace(ch[i])){
- i++;
- }
- intj=n-1;
- /*同上*/
- while(j>-1&&Character.isSpace(ch[j])){
- j--;
- }
- while(j>=i){
- /*如果判断到原字符串的第一个单词,此时将栈中字母弹出即可,不需要输出空格*/
- if(j==i){
- /*这里要记得把第一个字符压入栈*/
- stack.push(ch[j]);
- intsize=stack.size();
- for(intk=0; k){
- System.out.print(stack.pop());
- }
- }else if(Character.isSpace(ch[j])){
- /*如果是空格,并且栈不是空,则弹出栈中所有字母,并输出一个空格。
- 这里的栈是否为空判断是为了避免输出可能的多余空格*/
- if(stack.size()!=0){
- intsize=stack.size();
- for(intk=0; k){
- System.out.print(stack.pop());
- }
- System.out.print(" ");
- }
- }else{
- /*是字母的话直接入栈即可*/
- stack.push(ch[j]);
- }
- j--;
- }
- }
- }
3. LISP 语言唯一的语法就是括号要配对。形如 (OP P1 P2 ...),括号内元素由单个空格分割。其中第一个元素 OP 为操作符,后续元素均为其参数,参数个数取决于操作符类型
注意:参数 P1, P2 也有可能是另外一个嵌套的 (OP P1 P2 ...),当前 OP 类型为 quote / reverse / search / combine 字符串相关的操作:
- quote: 引用一个字符串,即返回字符串本身内容,参数个数 1
- reverse: 把字符串反转,并返回,参数个数 1
- search: 在第一个字符串中查找第二个字符串的第一次出现,返回从这开始到结束的所有字符串,如果查找不到,返回空字符串,参数个数 2
- combine: 把所有字符串组合起来,参数个数不定,但至少 1 个
其中 P1, P2 等参数可能是带双引号的字符串, 如 "abc",也有可能是另外一个 (OP P1 P2 ...),上述字符串包括引号;引号中间的所有字符,均为 ASCII 可打印字符,且不会再出现引号 ("),输出也为带双引号的字符串
举例:
输入字符串 输出结果
(quote"!@#$%")"!@#$%"
(reverse"a b c")"c b a"
(search"abcdef""cd") "cdef"
(search"abcdef""xy") ""
(combine"a""b" "cde) ")"abcde) "
(search (combine"1234567890""abcdefgh" "1234567890") (reverse"dc")) cdefgh1234567890
输入描述:
合法 C 字符串,字符串长度不超过 512;用例保证了无语法错误.
输出描述:
合法 C 字符串,需要带括号
输入例子:
(search"huawei""we")
输出例子:
"wei"
思路:利用栈结构,遇到 "("、操作符、操作数都压入栈,遇到")" 持续出栈 直至弹出一个 "(", 计算结果,再将这个结果压入栈。
代码:
- importjava.util.*;
- public class Main{
- public static void main(String[] args){
- Scanner sc=new Scanner(System.in);
- String ss=sc.nextLine();
- Stack stack=newStack();
- StringBuilder temp1=newStringBuilder();//字符串缓存,用来判断累积读入的字符是否构成一个操作数/操作符List temp2=newArrayList(); //用于存储栈弹出来的操作数
- char[] chars=ss.toCharArray();
- intn=chars.length;
- /*从左往右扫描字符数组*/
- for(inti=0;i){
- /*如果是 ( ,要判断是否实在操作数中,是的话加入缓存字符串,不是的话直接入栈*/
- if(chars[i]=='('){
- if(temp1.indexOf("\"")==-1){
- stack.push("(");
- }else{
- temp1.append('(');
- }
- }
- /*如果是 ) ,要判断是否实在操作数中,是的话加入缓存字符串,不是的话出栈至遇到一个 ( */
- else if(chars[i]==')'){
- /*根据缓存字符串中有没有 " 来判断是否在一个操作数中*/
- if(temp1.indexOf("\"")!=-1){
- temp1.append(')');
- }else{
- String back=stack.pop();
- while(!back.equals("(")){
- temp2.add(back);
- back=stack.pop();
- }
- String operator=temp2.get(temp2.size()-1);
- switch(operator){
- case"quote":
- stack.push("\""+(temp2.get(0)).replaceAll("\"","")+"\"");
- break;
- case"search":
- stack.push(search(temp2.get(1),temp2.get(0)));
- break;
- case"reverse":
- stack.push(reverse(temp2.get(0)));
- break;
- case"combine":
- String stringComb=combine(temp2.subList(0,temp2.size()-1));
- stack.push(stringComb);
- break;
- }
- temp2.clear();
- }
- }
- /*如果是空格,判断空格是否在操作数字符串中,不是的话原先的字符串缓存已经构成一个操作数/符,压入栈。
- 是的话加入到字符串缓存中*/
- else if(chars[i]==' '){
- if((temp1.indexOf("\"")!=-1)&&(chars[i-1]!='\"')){
- temp1.append(chars[i]);
- }else{
- if(temp1.length()>0){
- String tempString=temp1.toString();
- stack.push(tempString);
- temp1.setLength(0);
- }
- }
- }
- /*如果遇到成对的 " ,表明缓存的是一个操作符/数,将其压入栈*/
- else if((chars[i]=='\"')&&(temp1.indexOf("\"")!=-1)){
- if(temp1.length()>0){
- temp1.append('\"');
- String tempString=temp1.toString();
- stack.push(tempString);
- temp1.setLength(0);
- }
- }
- /*字母或者数字的情况直接加入到字符串缓存*/
- else{
- temp1.append(chars[i]);
- }
- }
- for(inti=0;i){
- System.out.print(stack.pop());
- }
- }
- static String search(String s1,String s2){
- s1=s1.replaceAll("\"","");
- s2=s2.replaceAll("\"","");
- if(s1.indexOf(s2)!=-1){
- return"\""+s1.substring(s1.indexOf(s2))+"\"";
- }else{
- return"\""+ "\"";
- }
- }
- static String reverse(String s){
- s=s.replaceAll("\"","");
- StringBuilder sb=new StringBuilder();
- char[] chars=s.toCharArray();
- for(inti=chars.length-1;i>=0;i--){
- sb.append(chars[i]);
- }
- return"\""+sb.toString()+"\"";
- }
- staticString combine(List l){
- StringBuilder sb=new StringBuilder();
- for(inti=l.size()-1;i>=0;i--){
- String s=(l.get(i)).replaceAll("\"","");
- sb.append(s);
- }
- return"\""+sb.toString()+"\"";
- }
- }
注:
判断 StringBuilder 是否为空:temp1.length()>0,通过长度是否大于 0 来判断,以及利用 setLength(0) 来清空 StringBuilder 中的内容
华为笔试算法题 1
来源: http://www.bubuko.com/infodetail-2146282.html