java算法知识点解析(1):字符串操作

时间:2022-03-03 13:14:20
华为面试题:
按要求分解字符串,输入两个数M,N;
M代表输入的M串字符串,N代表输出的每串字符串的位数,不够补0。
例如:输入2,8,
“abc” ,“123456789”,
则输出为“abc00000”,“12345678“,”90000000”

题目分析:
1.输入要合并的字符串数,字符串的长度
2.调用方法,for循环输出字符串,if判断大于字符串长度,输出0,并且将temp为空。小于字符串长度,存入temp全局中
3.判断temp循环如果不为空,重新执行方法

题目解法:
/*按要求分解字符串,输入两个数M,N;M代表输入的M串字符串,N代表输出的每串字符串的位数,不够补0。
例如:输入2,8, “abc” ,“123456789”,则输出为“abc00000”,“12345678“,”90000000”*/

public class Main {
      static int wei;
      static String sheng;
      public static void main(String[] args) {
            //定义输入字符串数!
            int ge=2;
            //定义输出位数!
            wei=8;
            //获取输入的字符串!
            String s[]=new String[ge];
            s[0]="abc";
            s[1]="123456789";

            for (int i = 0; i < s.length; i++) {
                  //输出字符串方法
                  printString(s[i]);
                  System.out.print("\t");     //添加缩进符号
                  while(sheng!=null){     //当剩余不为空的时候需要继续执行
                        printString(sheng);
                        System.out.print("\t");     //添加缩进符号
                  }
            }
      }

//输出字符串方法
      public static void printString(String s) {
            if(s.length()<8){
                  System.out.print(s);
                  for (int i = 0; i < 8-s.length(); i++) {  //补全所缺的代码
                        System.out.print("0");
                  }
                  sheng=null;
            }else{
                  System.out.print(s.substring(0, wei));   //截取最多的位数
                  sheng=s.substring(wei,s.length());   //截取后面的位数存起来
            }
      }

}
字符串操作是面试很常见的题目,一个不够,下面再举一个
二分查找字符串
有一个有序数组a,从小到大排序,共有n个元素。给定任一元素x,找出数组中第一次出现x的位置。用你熟悉的任何计算机语言比如c/c++,java,python等。写一个find函数,实现上述功能,并做好注释。

题目分析:
1.排序好的数组可能是非整型,所以用String包揽。寻找字符串的所在可以用方法:indexOf
2.如果不想用方法的话,可以自己编写二分查找法来寻找,这里主要用二分查找法
public class Test {
public static void main(String[] args) {
      String[] a={"a","b","c","d","e","f"};
      //System.out.println(Arrays.binarySearch(a, "c"));  //使用方法进行查找
      find(a,"f");   //执行查找字符串方法
}
/**
 * 查找字符串方法
 * @param a
 * @param key
 */
public static void find(String[] a,String key) {
      int min=0;   //定义最小脚标
      int max=a.length-1;   //定义最大脚标
      int mid;
      while(max>=min){   //需要等于才能遍历到最后一个数
            mid=min+(max-min)/2;  //获取中间脚标
            if(a[mid].compareTo(key)==0){ //判断中间与目标值得大小关系,等于0说明放好是这个脚标
                  System.out.println(mid);
                  return;   //结束循环
            }else if(a[mid].compareTo(key)<0){   //在前面部分
                  min=mid+1;
            }else if(a[mid].compareTo(key)>0){
                  max=mid-1;
            }
      }
}

}
再来一道跟二进制有关的,也是面试真题:
补充完成这个方法:
public static String _parse(int input){
     
     return null;
}
这个方法的功能是将任意一个整数转换成二进制字符串,返回一个长度为8的字符串,需要满足一下的条件:
a)如果字符串长度不足8位,则前面添加0一直补足8位,为8位则直接返回。
b)如果字符串长度大于8位,则返回NULL


题目分析:
1.转化为二进制可以直接使用Integer.toBinaryString()方法,如果不用方法,需要用for循环
2.把输入进来的数字不断/2一直除到1为止。除后的数如果是偶数输出0,如果是奇数输出1,将输出的数值连接起来,就是所要求的二进制
3.要求往前面补充凑足8位
public class Main {
public static void main(String[] args) {
      Scanner input=new Scanner(System.in);
      int num=input.nextInt();   //获取整形
      System.out.println(Integer.toBinaryString(num));   //利用方法转化为二进制,还没补充0
      System.out.println(_parse(num));          //执行获取二进制方法
}

public static String _parse(int input){
      String result = "";
      int sum;
      for (int i = input; i >= 1; i=i/2) {   //将输入的数值除以2
            if (i % 2 == 0) {  //偶数就输出0
                  sum = 0;
            } else {   //奇数输出1
                  sum = 1;
            }
            result = sum + result;  //将输出内容收集起来,往后添加
      }
      if(result.length()<8){
            int bu=8-result.length();
            for (int i = 0; i < bu; i++) {
                  result="0"+result;    //在前面补充欠缺的0
            }
            return result;    //返回数值
      }else if(result.length()==8){   //等于8直接返回数值
            return result;
      }
    return null;   //前面都有返回,这个就是其余情况(大于8位),返回空
}

}
做完了手上的真题,继续研究,下面这道是从牛客网寻找到的:2017年校招全国统一模拟笔试(第一场)编程题集合
[编程题] 循环单词

如果一个单词通过循环右移获得的单词,我们称这些单词都为一种循环单词。 例如:picture 和 turepic 就是属于同一种循环单词。 现在给出n个单词,需要统计这个n个单词中有多少种循环单词。 
输入描述:
输入包括n+1行:
第一行为单词个数n(1
n 50)
接下来的n行,每行一个单词word[i],长度length(1
length 50)。由小写字母构成
输出描述:
输出循环单词的种数
输入例子:
5

picture

turepic

icturep

word

ordw

输出例子:
2

题目分析:
1.首先获取输入的行数
2.每一次输入字符串,我们可以以他为标准作为比较。但是每一次都要重新组合很麻烦。为什么不把组合的情况先存起来呢?为了避免重复存,所以用HashSet。当我存一个之后,我第二个就不用存了,直接判断包含不就可以了,而存的项数将决定所有的情况
判断Hashset中是否包含,不包含的话就增加1项,并且多次改变其头尾,将所有情况存入set中
3.最后输出计数量即可
import java.util.HashSet;
import java.util.Scanner;

public class Main {
      public static void main(String[] args) {
            Scanner input=new Scanner(System.in);
            HashSet<String> set=new HashSet<String>();

            int num=input.nextInt();  //获取输入的字符串数
            input.nextLine();

            int count=0;   //定义一个类别计数器
            for (int i = 0; i < num; i++) {
                  String a=input.nextLine();   //获取字符串
                  if(!set.contains(a)){   //如果set数组不包含a字符串要执行以下操作
                        count++;
                        set.add(a);   //将a存入set数组中
                        String b=another(a);   //获取另一种a的情况
                        while(!set.contains(b)){  //当这个b在set里面是没有的,一直到循环重组
                              set.add(b);
                              b=another(b);   //对b进行再一次重组
                        }
                  }
            }
            System.out.println(count);
      }
      /**
       * 重组字符串a
       * @param a
       * @return
       */
      public static String another(String a) {
            return a.substring(a.length()-1)+a.substring(0, a.length()-1);
      }

}
牛客网一翻,下一题又是字符串操作的,现在把它也给做了
DNA分子是以4种脱氧核苷酸为单位连接而成的长链,这4种脱氧核苷酸分别含有A,T,C,G四种碱基。碱基互补配对原则:A和T是配对的,C和G是配对的。如果两条碱基链长度是相同的并且每个位置的碱基是配对的,那么他们就可以配对合成为DNA的双螺旋结构。现在给出两条碱基链,允许在其中一条上做替换操作:把序列上的某个位置的碱基更换为另外一种碱基。问最少需要多少次让两条碱基链配对成功 
输入描述:
输入包括一行: 包括两个字符串,分别表示两条链,两个字符串长度相同且长度均小于等于50。 


输出描述:
输出一个整数,即最少需要多少次让两条碱基链配对成功 

输入例子:
ACGT TGCA 

输出例子:
0

题目分析:
1.题目大概可以理解为,不对应的有多少个,我的思路是这样的:将两个数据存入String中
2.将两组String取出i,双方是否对应。比较方式,该角标下同时符合,四种情况其中一种即可
3.当不同的时候进行计数,这就是需要替换的数量
public class Main {
public static void main(String[] args) {
      Scanner input=new Scanner(System.in);
      //新建两个字符串
      String st_1=input.next();
      String st_2=input.next();
      //比较方法
      System.out.println(comp(st_1,st_2));

}
/**
 * 输出不能配对的个数
 * @param st_1
 * @param st_2
 * @return
 */
public static int comp(String st_1, String st_2) {
      int count=0;
      for (int i = 0; i < st_1.length(); i++) {
            if((st_1.charAt(i)=='A'&&st_2.charAt(i)=='T')||(st_1.charAt(i)=='T'&&st_2.charAt(i)=='A')||(st_1.charAt(i)=='C'&&st_2.charAt(i)=='G')||(st_1.charAt(i)=='G'&&st_2.charAt(i)=='C')){   //四种配对情况符合一种即可
                  continue;
            }else{
                  count++;   //不配对计数加1
            }
      }
      return count;
}

}
这是一道天梯赛的题,我觉得这道题跟字符操作也有不少关系。
L1-007. 念数字

输入一个整数,输出每个数字对应的拼音。当整数为负数时,先输出“fu”字。十个数字对应的拼音如下:

0: ling
1: yi
2: er
3: san
4: si
5: wu
6: liu
7: qi
8: ba
9: jiu
输入格式:

输入在一行中给出一个整数,如: 1234 。

提示:整数包括负数、零和正数。

输出格式:

在一行中输出这个整数对应的拼音,每个数字的拼音之间用空格分开,行末没有最后的空格。如 yi er san si。

输入样例:
-600
输出样例:
fu liu ling ling


时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
翁恺

题目分析:
1.首先将表存入Map数组中
2.判断大小,输出表对应的信息
public class Main {
public static void main(String[] args) {
      HashMap<String, String> hm=new HashMap<String, String>(); //新建HashMap容器作为表
      hm.put("-", "fu");
      hm.put("0", "ling");   //存入数据
      hm.put("1", "yi");
      hm.put("2", "er");
      hm.put("3", "san");
      hm.put("4", "si");
      hm.put("5", "wu");
      hm.put("6", "liu");
      hm.put("7", "qi");
      hm.put("8", "ba");
      hm.put("9", "jiu");
      Scanner input=new Scanner(System.in);
      //获取输入的整形
      String num=input.next();
      ArrayList<String> al=new ArrayList<String>();
      //输出内容
      int temp=num.length();
      for (int i = 0; i < temp; i++) {
            if(i!=(temp-1)){
                  System.out.print(hm.get(num.substring(0, 1))+" ");
            }else{
                  System.out.print(hm.get(num.substring(0, 1)));  //尾部不需要空格
            }
            num=num.substring(1);//对字符串进行切割
      }
}
}
这是一道将String字符串转化为整形的题
L1-018. 大笨钟


微博上有个自称“大笨钟V”的家伙,每天敲钟催促码农们爱惜身体早点睡觉。不过由于笨钟自己作息也不是很规律,所以敲钟并不定时。一般敲钟的点数是根据敲钟时间而定的,如果正好在某个整点敲,那么“当”数就等于那个整点数;如果过了整点,就敲下一个整点数。另外,虽然一天有24小时,钟却是只在后半天敲1~12下。例如在23:00敲钟,就是“当当当当当当当当当当当”,而到了23:01就会是“当当当当当当当当当当当当”。在午夜00:00到中午12:00期间(端点时间包括在内),笨钟是不敲的。

下面就请你写个程序,根据当前时间替大笨钟敲钟。

输入格式:

输入第一行按照“hh:mm”的格式给出当前时间。其中hh是小时,在00到23之间;mm是分钟,在00到59之间。

输出格式:

根据当前时间替大笨钟敲钟,即在一行中输出相应数量个“Dang”。如果不是敲钟期,则输出:

Only hh:mm.  Too early to Dang.
其中“hh:mm”是输入的时间。

输入样例1:
19:05
输出样例1:
DangDangDangDangDangDangDangDang
输入样例2:
07:05
输出样例2:
Only 07:05.  Too early to Dang.

题目分析:
1.将输入的字符串分割成两部分数据
2.将两部分转化为int型然后传到响钟方法中(注意分钟需要在时钟12h才会有效)
public class main {
      static int count=0;  //记录响的次数
      public static void Main(String[] args) {
            //获取时间
            Scanner input=new Scanner(System.in);
            String time=input.next();

            //切割时间调用前响方法
            int hour=Integer.parseInt(time.substring(0, 2));
            if(hour<0||hour>=24){   //筛选范围
                  return;
            }
            before(hour);
            //切割时间调用补响方法
            int minute=Integer.parseInt(time.substring(4,5));
            if(minute<0||minute>59){   //筛选范围
                  return;
            }
            if(hour>12){
                  after(minute);                //分钟要响需要时钟的12点之后
            }
            if(count==0){  //没敲过钟
                  System.out.print("Only "+time+".  Too early to Dang.");
            }

      }

/**
 * 前面敲钟方法
 * @param substring
 */
      public static void before(int hour) {
            if(hour>12){  //大于12才有资格敲钟
                  for (int i = 0; i < hour-12; i++) {
                        System.out.print("Dang");
                        count++;
                  }
            }
      }
/**
 * 后面敲钟方法
 * @param substring
 */
      public static void after(int minute) {
            if(minute>0){
                  System.out.print("Dang");
                  count++;
            }
      }

}
这是天梯赛的,通过提取筛选,顺序输出字符串
L1-023. 输出GPLT
时间限制
150 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
给定一个长度不超过10000的、仅由英文字母构成的字符串。请将字符重新调整顺序,按“GPLTGPLT....”这样的顺序输出,并忽略其它字符。当然,四种字符(不区分大小写)的个数不一定是一样多的,若某种字符已经输出完,则余下的字符仍按GPLT的顺序打印,直到所有字符都被输出。
输入格式:
输入在一行中给出一个长度不超过10000的、仅由英文字母构成的非空字符串。
输出格式:
在一行中按题目要求输出排序后的字符串。题目保证输出非空。
输入样例:
pcTclnGloRgLrtLhgljkLhGFauPewSKgt
输出样例:
GPLTGPLTGLTGLGLL


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class main {

      static int[] count=new int[4];   //定义计数器
      static String[] gplt={"G","P","L","T","g","p","l","t"};

      public static void main(String[] args) throws IOException {
            //数据处理
//          Scanner input=new Scanner(System.in);  //Scanner可能会导致内存太大!
//          String st=input.nextLine();   //获取字符串信息
            BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
            String st=in.readLine();

            //数据操作
            count(st);
            //数据显示
            show();
      }

/**
 * 获取不同字符的数量计数
 * @param st
 */
      public static void count(String st) {
            //寻找G的个数
            for (int i = 0; i <count.length; i++) {
                  String temp=st.substring(0); //截取整条数据
                  int start=0;
                  while(start!=-1){
                        start=temp.indexOf(gplt[i]);
                        if(start!=-1){   //有存在G
                              temp=temp.substring(start+1);  //截取后面的部分
                              count[i]++;  //计数器++
                        }
                  }
                  start=0;    //初始化查询指针
                  temp=st.substring(0); //初始化整条字符串
                  while(start!=-1){
                        start=temp.indexOf(gplt[i+4]);
                        if(start!=-1){   //有存在G
                              temp=temp.substring(start+1);  //截取后面的部分
                              count[i]++;  //计数器++
                        }
                  }

            }
      }
/**
 * 显示打印数据
 */
      public static void show() {
            for (int i = 0; i < count.length; i++) {
                  while(count[0]>0||count[1]>0||count[2]>0||count[3]>0){
                        if(count[0]>0){
                              System.out.print("G");
                              count[0]--;
                        }
                        if(count[1]>0){
                              System.out.print("P");
                              count[1]--;
                        }
                        if(count[2]>0){
                              System.out.print("L");
                              count[2]--;
                        }
                        if(count[3]>0){
                              System.out.print("T");
                              count[3]--;
                        }

                  }
            }
      }

}
继续选择天梯赛的题目,这个还是用到了字符串判断。
L1-025. 正整数A+B

本题的目标很简单,就是求两个正整数A和B的和,其中A和B都在区间[1,1000]。稍微有点麻烦的是,输入并不保证是两个正整数。

输入格式:

输入在一行给出A和B,其间以空格分开。问题是A和B不一定是满足要求的正整数,有时候可能是超出范围的数字、负数、带小数点的实数、甚至是一堆乱码。

注意:我们把输入中出现的第1个空格认为是A和B的分隔。题目保证至少存在一个空格,并且B不是一个空字符串。

输出格式:

如果输入的确是两个正整数,则按格式“A + B = 和”输出。如果某个输入不合要求,则在相应位置输出“?”,显然此时和也是“?”。

输入样例1:
123 456
输出样例1:
123 + 456 = 579
输入样例2:
22. 18
输出样例2:
? + 18 = ?
输入样例3:
-100 blabla bla...33
输出样例3:
? + ? = ?

时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越

题目分析:
1.获取两个字符串
2.判断字符串是否为数字
3.输出内容,三个位置
public class Main {
      static String st_a;
      static String st_b;
      static String st_c="-1";
      static String a="0123456789";
public static void main(String[] args) {
      //数据管理
      Scanner input=new Scanner(System.in);
      String st=input.nextLine();   //注意不要重复定义
      st_a=st.substring(0,st.indexOf(" "));
      st_b=st.substring(st.indexOf(" ")+1);

      //数据控制
      if(!control(st_a)){   //判断如果非数字
            st_a="?";   //改变成需要显示的数据
            st_c="?";
      }else if(Integer.parseInt(st_a)<1||Integer.parseInt(st_a)>1000){   //接收范围1~1000
            st_a="?";   //改变成需要显示的数据
            st_c="?";
      }
      if(!control(st_b)){
            st_b="?";
            st_c="?";
      }else if(Integer.parseInt(st_b)<1||Integer.parseInt(st_b)>1000){   //接收范围1~1000
            st_b="?";   //改变成需要显示的数据
            st_c="?";
      }

      //数据显示
      show();
}
/**
 * 判断是不是数字
 * @param st
 * @return
 */
public static boolean control(String st) {
      boolean flag=true;
      for (int i = 0; i < st.length(); i++) {
            if(a.contains(st.substring(i, i+1))){   //是数字
                  continue;   //继续运行
            }else{    //不是数字
                  flag=false;
            }
      }
      return flag;
}

/**
 * 通过string显示数据
 */
public static void show() {
      if(st_c.equals("?")){
            System.out.print(st_a+" + "+st_b+" = ?");
      }else{
            int a =Integer.parseInt(st_a);
            int b=Integer.parseInt(st_b);
            System.out.print(a+" + "+b+" = "+(a+b));
      }
}

}