Java数据结构和算法总结-字符串相关高频面试题算法

前言:周末闲来无事,在七月在线上看了看字符串相关算法的讲解视频,收货颇丰,跟着视频讲解简单做了一下笔记,方便以后翻阅复习同时也很乐意分享给大家。什么字符串在算法中有多重要之类的大路边上的客套话就不多说了,直接上笔记吧。

一、字符串

  • java:String内置类型,不可更改。(如需更改可考虑:StringBuffer, StringBuilder,char[]等)

二、归类

 字符串涉及到的相关题型通常会是以下几个方面:

  • 概念理解:字典序
  • 简单操作:插入删除字符、旋转
  • 规则判断(罗马数字转换 是否是合法的整数、浮点数)
  • 数字运算(大数加法,二进制加法)
  • 排序、交换
  • 字符计数:变位词
  • 匹配(正则表达式、全串匹配、KMP、周期判断)
  • 动态规划(LCS、编辑距离、最长回文子串)
  • 搜索(单词变换、排列组合)

三、例题

1、交换:把一个只包含01的串排序,可交换任意两个数的位置,最少需要多少次交换?

  思路:从两头往中间扫荡,扫荡过程中在左边遇到1就和右边遇到的0交换位置,直接到左有下标相遇时结束。 具体代码如下:

 1 public static void main(String[] strs) {
 2         int count = 0;
 3         int[] arrays = new int[] {0, 0, 1, 1, 1, 0, 1, 0, 0, 1};
 4         int left = 0;
 5         int right = arrays.length - 1;
 6         while (true) {
 7             while (arrays[left] == 0) {
 8                 left++;
 9             }
10             while (arrays[right] == 1) {
11                 right--;
12             }
13             if (left >= right) {
14                 break;
15             } else {
16                 int temp = arrays[left];
17                 arrays[left] = arrays[right];
18                 arrays[right] = temp;
19                 count++;
20             }
21         }
22         Logger.println("交换次数:" + count);
23         for (int array : arrays) {
24             Logger.print(array + ", ");
25         }
26 }

清晰起见,交换次数和排序后的的字符串输出如下:

交换次数:3
0, 0, 0, 0, 0, 1, 1, 1, 1, 1,

2、字符串替换和复制:删除一个字符串所有的a,并且复制所有的b(字符数组足够大)

  思路:详细思路见代码注释

 1 public static void main(String[] strs) {
 2         char[] input = new char[]{'a', 'b', 'c', 'd', 'a', 'f', 'a', 'b', 'c', 'd', 'b', 'b', 'a', 'b'};
 3         char[] chars = new char[50];
 4         for (int j = 0; j < input.length; j++) {
 5             chars[j] = input[j];
 6         }
 7         Logger.println("操作前:");
 8         for (char c:chars
 9                 ) {
10             Logger.print(c + ", ");
11         }
12         int n = 0;
13         int countB = 0;
14         // 1、删除a,用n当做新下标,循环遍历数组,凡是不是a的元素都放到新下标的位置,由于新n增长慢,老下标i增长快,所以元素不会被覆盖。
15         // 并且在删除a时顺便记录b的数量,以便下一步复制b时可以提前确定数组最终的最大的下标。
16         for (int i = 0; chars[i] != '\u0000' && i < chars.length; i++) {
17             if (chars[i] != 'a') {
18                 chars[n++] = chars[i];
19             }
20             if (chars[i] == 'b') {
21                 countB++;
22             }
23         }
24 
25         // 2、复制b,由于在第一步中就已经知道了字符串中b的个数,这里就能确定最终字符串的最大下标,从最打下表开始倒着复制原字符串,碰到b时复制即可。
26         int newMaxIndex = n + countB - 1;
27         for (int k = n - 1; k >= 0; k--) {
28             chars[newMaxIndex--] = chars[k];
29             if (chars[k] == 'b') {
30                 chars[newMaxIndex--] = chars[k];
31             }
32         }
33 
34         Logger.println("\n操作后:");
35         for (char c:chars
36                 ) {
37             Logger.print(c + ", ");
38         }
39 }

3、交换星号:一个字符串只包含 * 和数字,请把它的 * 都放在开头。

  如:1 * 2 * 4 * 3 => * * * 1 2 4 3

  • 方案一:倒着操作,从最大下标开始向前遍历,遇到非 * 号的元素则加入"新"下标中,遍历完毕后,j即代表 * 号的个数,然后将0-j赋值为 * 即可。(操作后,数字的相对位置不变) 代码如下:
 1 public static void main(String[] strs) {
 2         char[] chars = new char[]{'1', '*', '4', '3', '*', '5', '*'};
 3         // 方案一(操作后,数字的相对位置不变)
 4         // 倒着操作:从最大下标开始向前遍历,遇到非*号的元素则加入"新"下标中,遍历完毕后,j即代表*号的个数,然后将0-j赋值为*即可。
 5         int j = chars.length - 1;
 6         for (int i = j; i >= 0; i--) {
 7             if (chars[i] != '*') {
 8                 chars[j--] = chars[i];
 9             }
10         }
11         while (j >= 0) {
12             chars[j--] = '*';
13         }
14         for (char c:chars
15                 ) {
16             Logger.print(c + ", ");
17         }
18 }

输出结果如下:

*, *, *, 1, 4, 3, 5,
  • 方案二(操作后,数组的相对位置会变)快排划分,根据循环不变式(每一步循环之后条件都成立):如本题[0..i-1]是*,[i..j-1]是数字,[j...n-1]未探测,循环时,随着i和j增加,维护此条件依然不变,代码如下:
 1 public static void main(String[] strs) {
 2         char[] chars = new char[]{'1', '*', '4', '3', '*', '5', '*'};
 3         // 方案二(操作后,数组的相对位置会变)
 4         // 快排划分,根据循环不变式(每一步循环之后条件都成立):如本题[0..i-1]是*,[i..j-1]是数字,[j...n-1]未探测,循环时,随着i和j增加,维护此条件依然不变
 5         for (int i = 0, j = 0; j < chars.length; ++j) {
 6             if (chars[j] == '*') {
 7                 char temp = chars[i];
 8                 chars[i] = chars[j];
 9                 chars[j] = temp;
10                 i++;
11             }
12         }
13         for (char c:chars
14                 ) {
15             Logger.print(c + ", ");
16         }
17 } 

输出结果如下:

*, *, *, 3, 1, 5, 4,

4、单词翻转

  例如:I am a student =》 student a am I

  思路:

  1、先将整个字符串翻转:如:I am a student =》 tneduts a ma I

  2、通过空格判断出每个单词,然后对每个单词进行翻转

  代码如下:

 1 public static void main(String[] strs) {
 2         String input = "I am a student";
 3         char[] chars = input.toCharArray();
 4         int i = 0;
 5         int j = chars.length - 1;
 6         while (i < j) {
 7             swap(chars, i++, j--);
 8         }
 9         int front = 1;
10         int tail = 0;
11         while (front < chars.length) {
12             if (chars[front] == ' ') {
13                 int frontTemp = front - 1;
14                 while (tail < frontTemp) {
15                     swap(chars, tail++, frontTemp--);
16                 }
17                 tail = front + 1;
18             }
19             front++;
20         }
21         for (char c:chars
22                 ) {
23             Logger.print(c);
24         }
25 }
26 
27 public static void swap(char[] chars, int index1, int index2) {
28         char temp = chars[index1];
29         chars[index1] = chars[index2];
30         chars[index2] = temp;
31 }

输出结果如下:

student a am I

5、子串变位词:给定两个串a和b,问b是否a的子串变位词。

  例如:a=hello。b=lel,lle,ello都是true;b=elo是false

  思路:

    •   一、首先需要了解对两个串是否是变位词的判断:
    1.   对两个串按统一规则排序,排序后若相等则是变位词。
    2.   对两个串中出现的字母统计,两串中相同的字母出现的次数一致则为变位词。
    •   二、然后从母串的第一个元素遍历,每往后遍历一个元素就把从当前元素开始到加上子串的长度的位置作为一个区间和子串比较是否是变位词。

最后一题综合前几个题用到的一些技巧,还是比较有趣的,这里就不贴出代码了,也激发一下大家的动手能力,感兴趣的童鞋不妨试着写一写。

以上问题如有不同思路欢迎交流。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏简书专栏

Python面对对象编程

面向过程:根据业务逻辑从上到下写代码 函数式:将某功能代码封装到函数中,日后便无需重复填写,仅调用函数即可 面对对象:对函数进行分类和封装,让开发"更好更快...

1103
来自专栏机器学习算法与Python学习

动画+原理+代码,解读十大经典排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

963
来自专栏极客慕白的成长之路

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

734
来自专栏C/C++基础

C++中函数重载、隐藏、覆盖和重写的区别

C++规定在同一作用域中,同名函数的形式参数(指参数的个数、类型或者顺序)不同时,构成函数重载。

862
来自专栏我的技术专栏

图说C++对象模型:对象内存布局详解

2283
来自专栏Java帮帮-微信公众号-技术文章全总结

第十一天 面向对象-接口多态【悟空教程】

1454
来自专栏我的博客

基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,...

2936
来自专栏我杨某人的青春满是悔恨

“身首异处”的序列(Swift)

声明:文章开头部分内容翻译自objc的一篇博客。当然,我并没有逐行翻译原文,只是说个大致意思,顺带阐述一些自己的理解和扩展思考,还有我自己的代码。

1252
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:数组全解!!

正文之前 其实我的《C++ Primer》 已经看到第五章了,但是因为码字比较费时间,所以暂时没有迅速更新实在是对不住,但是没办法, 总不能一天拿出五六个小时来...

34810
来自专栏落影的专栏

程序员进阶之算法练习(三十四)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

1073

扫码关注云+社区