前言:周末闲来无事,在七月在线上看了看字符串相关算法的讲解视频,收货颇丰,跟着视频讲解简单做了一下笔记,方便以后翻阅复习同时也很乐意分享给大家。什么字符串在算法中有多重要之类的大路边上的客套话就不多说了,直接上笔记吧。
一、字符串
二、归类
字符串涉及到的相关题型通常会是以下几个方面:
三、例题
思路:从两头往中间扫荡,扫荡过程中在左边遇到1就和右边遇到的0交换位置,直接到左有下标相遇时结束。 具体代码如下:
- public static void main(String[] strs) {
- int count = 0;
- int[] arrays = new int[] {0, 0, 1, 1, 1, 0, 1, 0, 0, 1};
- int left = 0;
- int right = arrays.length - 1;
- while (true) {
- while (arrays[left] == 0) {
- left++;
- }
- while (arrays[right] == 1) {
- right--;
- }
- if (left >= right) {
- break;
- } else {
- int temp = arrays[left];
- arrays[left] = arrays[right];
- arrays[right] = temp;
- count++;
- }
- }
- Logger.println("交换次数:" + count);
- for (int array : arrays) {
- Logger.print(array + ", ");
- }
- }
清晰起见,交换次数和排序后的的字符串输出如下:
- 交换次数:3
- 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
思路:详细思路见代码注释
- public static void main(String[] strs) {
- char[] input = new char[]{'a', 'b', 'c', 'd', 'a', 'f', 'a', 'b', 'c', 'd', 'b', 'b', 'a', 'b'};
- char[] chars = new char[50];
- for (int j = 0; j < input.length; j++) {
- chars[j] = input[j];
- }
- Logger.println("操作前:");
- for (char c:chars
- ) {
- Logger.print(c + ", ");
- }
- int n = 0;
- int countB = 0;
- // 1、删除a,用n当做新下标,循环遍历数组,凡是不是a的元素都放到新下标的位置,由于新n增长慢,老下标i增长快,所以元素不会被覆盖。
- // 并且在删除a时顺便记录b的数量,以便下一步复制b时可以提前确定数组最终的最大的下标。
- for (int i = 0; chars[i] != '\u0000' && i < chars.length; i++) {
- if (chars[i] != 'a') {
- chars[n++] = chars[i];
- }
- if (chars[i] == 'b') {
- countB++;
- }
- }
- // 2、复制b,由于在第一步中就已经知道了字符串中b的个数,这里就能确定最终字符串的最大下标,从最打下表开始倒着复制原字符串,碰到b时复制即可。
- int newMaxIndex = n + countB - 1;
- for (int k = n - 1; k >= 0; k--) {
- chars[newMaxIndex--] = chars[k];
- if (chars[k] == 'b') {
- chars[newMaxIndex--] = chars[k];
- }
- }
- Logger.println("\n操作后:");
- for (char c:chars
- ) {
- Logger.print(c + ", ");
- }
- }
如:1 * 2 * 4 * 3 => * * * 1 2 4 3
- public static void main(String[] strs) {
- char[] chars = new char[]{'1', '*', '4', '3', '*', '5', '*'};
- // 方案一(操作后,数字的相对位置不变)
- // 倒着操作:从最大下标开始向前遍历,遇到非*号的元素则加入"新"下标中,遍历完毕后,j即代表*号的个数,然后将0-j赋值为*即可。
- int j = chars.length - 1;
- for (int i = j; i >= 0; i--) {
- if (chars[i] != '*') {
- chars[j--] = chars[i];
- }
- }
- while (j >= 0) {
- chars[j--] = '*';
- }
- for (char c:chars
- ) {
- Logger.print(c + ", ");
- }
- }
输出结果如下:
- *, *, *, 1, 4, 3, 5,
- public static void main(String[] strs) {
- char[] chars = new char[]{'1', '*', '4', '3', '*', '5', '*'};
- // 方案二(操作后,数组的相对位置会变)
- // 快排划分,根据循环不变式(每一步循环之后条件都成立):如本题[0..i-1]是*,[i..j-1]是数字,[j...n-1]未探测,循环时,随着i和j增加,维护此条件依然不变
- for (int i = 0, j = 0; j < chars.length; ++j) {
- if (chars[j] == '*') {
- char temp = chars[i];
- chars[i] = chars[j];
- chars[j] = temp;
- i++;
- }
- }
- for (char c:chars
- ) {
- Logger.print(c + ", ");
- }
- }
输出结果如下:
- *, *, *, 3, 1, 5, 4,
例如:I am a student =》 student a am I
思路:
1、先将整个字符串翻转:
- 如:I am a student =》 tneduts a ma I
2、通过空格判断出每个单词,然后对每个单词进行翻转
代码如下:
- public static void main(String[] strs) {
- String input = "I am a student";
- char[] chars = input.toCharArray();
- int i = 0;
- int j = chars.length - 1;
- while (i < j) {
- swap(chars, i++, j--);
- }
- int front = 1;
- int tail = 0;
- while (front < chars.length) {
- if (chars[front] == ' ') {
- int frontTemp = front - 1;
- while (tail < frontTemp) {
- swap(chars, tail++, frontTemp--);
- }
- tail = front + 1;
- }
- front++;
- }
- for (char c: chars) {
- Logger.print(c);
- }
- }
- public static void swap(char[] chars, int index1, int index2) {
- char temp = chars[index1];
- chars[index1] = chars[index2];
- chars[index2] = temp;
- }
输出结果如下:
- student a am I
例如:a=hello。b=lel,lle,ello都是true;b=elo是false
最后一题综合前几个题用到的一些技巧,还是比较有趣的,这里就不贴出代码了,也激发一下大家的动手能力,感兴趣的童鞋不妨试着写一写。
以上问题如有不同思路欢迎交流。
来源: http://www.cnblogs.com/codingblock/p/7712596.html