字符串中相同字母删除

字符串中相同字母删除"/>

字符串中相同字母删除

美团2020面试题

将给定的字符串，按照规则删除字符，输出删除后的字符串。删除规则为：相同字符连续，则删除，如”aaaab”删除后的字符串为”b” 。注：仅是单个字符连续才删除，如babababa则不能删除；

参考代码：

public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {String str = in.nextLine();StringBuilder sb = new StringBuilder();// i记录连续子串的头部for (int i = 0; i < str.length(); i++) {// j为移动指针，记录连续子串的尾部int j = i;// 若后一个字符跟当前一样，则j后移一位while (j + 1 < str.length() && str.charAt(j) == str.charAt(j + 1))j++;if (i == j)// ij相等说明不是连续的，拼接之sb.append(str.charAt(i));else// 当前子串是连续，跳过i = j;}if (sb.toString().equals(""))System.out.println("no");elseSystem.out.println(sb);}}

知识点：
1.StringBuilder sb = new StringBuilder(); sb.append();
为了能高效拼接字符串，Java标准库提供了StringBuilder，它是一个可变对象，可以预分配缓冲区，这 样，往StringBuilder中新增字符时，不会创建新的临时对象.
2. Scanner scan = new Scanner(System.in); // 从键盘接收数据
其中，通过 Scanner 类的 next() 与 nextLine() 方法获取输入的字符串，在读取前我们一般需要 使用 hasNext 与 hasNextLine 判断是否还有输入的数据：nextLine()：①以Enter为结束符,也就是说 nextLine()方法返回的是输入回车之前的所有字符。
②可以获得空白。
next():①一定要读取到有效字符后才可以结束输入。②对输入有效字符之前遇到的空白，next() 方法会自动将其去掉。③只有输入有效字符后才将其后面输入的空白作为分隔符或者结束符。④next() 不能得到带有空格的字符串。
3.List< string > result=new ArrayList()；
name.add(“zzz”);

总结：
使用Scanner类获取键盘输入的字符，对输入的字符使用两个指针，一个指针指向重复的字符串的首部，一个指针指向重复字符串的尾部，首部指针使用小于输入字符的长度循环遍历整个字符，重复的字符每次的首部指针等于尾部指针的内容达到删除的效果。

寻找最小子字符串

小美和小团在玩一个游戏，小美任意给出一个大字符串str1以及一个独立的小字符串str2，小团需要从这个大字符串str1里找到包含独立小字符串str2中所有字符的最小子字符串str3；
例如，小美给出一个大字符串"meituan2019"和一个子字符串"i2t"，那么小团给出的答案就应该是"ituan2"；
注意：
1、str1中有可能没有完整包含str2所有字符的情况，此时返回""，即为空字符串；
2、str1不会为空，但str2有可能为空，此时返回整个str1；
3、str2可能存在重复的字符，此时str3需要包含相等数量该字符；

参考答案：

		public static String getMinString (String str1, String str2) {// write code hereif(str2==null||str2.length()==0){ return str1;}int[] strA = new int[128];int[] strB = new int[128];int left = 0,right = 0;for(int i=0;i<str1.length();i++){strA[str1.charAt(i)]++;}for(int i=0;i<str2.length();i++){strB[str2.charAt(i)]++;}// 没有完全包含所有字符,str2中有个字符多了几个或一个。for(int k=0;k<str2.length();k++){//str.charAt()if(strA[str2.charAt(k)]<strB[str2.charAt(k)]){return "";}}//find leftfor(int k=0;k<str1.length();k++){//保证相同数目的字符在范围内if(--strA[str1.charAt(k)]<strB[str1.charAt(k)]){left=k;break;}}for(int k=str1.length()-1;k>=0;k--){if(--strA[str1.charAt(k)]<strB[str1.charAt(k)]){right=k;break;}}return str1.substring(left,right+1);}public static void main(String[] args) {String str1="meituan2019";String str2="i2t";System.out.println(getMinString(str1,str2));}

对两个字符串的字母数量分别进行了统计，使用了hash函数；
对字符串str1进行挨个遍历，直到在str1中找到当前字符的数量减1小于str2字符数量为止，确定str1中的该字符下标为最小子字符串的左端，同样道理从str1的最后一位开始倒数，从而确定最小子字符串的右端；

知识点
1.public String substring(int beginIndex, int endIndex)
其中，beginIndex – 起始索引（包括）, 索引从 0 开始。
endIndex – 结束索引（不包括）。
2.–a,先进行减一操作后进行引用
3.int[] strA = new int[128];
动态初始化：初始化时由程序员指定数组的长度，由系统初始化每个数组元素的默认值。
4. int[] strA = new int[128];
for(int i=0;i<str1.length();i++){
strA[str1.charAt(i)]++;
}
hash统计了每一个字符的数量

3.队列

一个班级男生和女生数量相同，老师要求男生女生进行排队，男生全部排在队列前面，女生紧跟着排在男生队列后面，形成一个队列，现在要求男生女生交叉排列并且第一位是男生，且每个人在在原队列中的顺序不变，如何来做？
要求：
交叉前：队列[男1，男2，男3，男4…男n，女1，女2，女3，女4…女n]
交叉后：队列[男1，女1，男2，女2，男3，女3，男4，女4…男n，女n]

思路：使用一个变量判断其是奇数还是偶数，控制队列的插入；
参考答案：
①java

import java.util.ArrayList;
import java.util.Scanner;
public class Main3 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int size = 2*n;//ArrayList<Integer> list = new ArrayList<Integer>(2*n);int[] arr = new int[n];int[] brr = new int[n];for (int i = 0; i <n; i++) {arr[i] = sc.nextInt();}for (int i = 0; i <n; i++) {brr[i] = sc.nextInt();}for (int i=0,j=0,k=0; k<size;k++) {if(k%2==0) {//偶数位System.out.println(arr[i]);i++;}else {System.out.println(brr[j]);j++;}}sc.close();}
}

知识点：
ArrayList类是一个特殊的数组–动态数组。通过添加和删除元素，就可以动态改变数组的长度。

迪杰斯特拉算法

import java.util.*;
public class Main4 {static int dijkstra(int[][] g, int n, int target, int k, int value){boolean[] finished = new boolean[n];int[] distance = new int[n];Arrays.fill(distance, Integer.MAX_VALUE);distance[0] = k == 0 ? value : 0;if(k != 0) {for(int i=0; i < n; i++)if(i != k && g[k][i] != -1) {g[i][k] = g[k][i] += value;}}for(int i=0; i < n; i++) {int t = -1;for(int j=0; j < n; j++) {if(finished[j]==false &&(t == -1 || distance[t] > distance[j])) {t = j;}}finished[t] = true;for(int j=0; j < n; j++) {if(g[t][j] != -1) {distance[j] = Math.min(distance[j], distance[t]+g[t][j]);}}}return distance[target];}public static void main(String[] args){Scanner sc = new Scanner(System.in);int target = sc.nextInt();int k = sc.nextInt(), value=sc.nextInt();int n = 6;int[][] g = new int[n][n];for(int i=0; i < n; i++){Arrays.fill(g[i], -1);g[i][i] = 0;}g[0][1] = 1; g[0][2] = 2; g[0][3] = 7;g[1][0] = 1; g[1][2] = 2; g[1][4] = 5; g[1][5] = 4;g[2][0] =  2; g[2][1] = 2; g[2][4] = 4; g[2][3] = 4;g[3][0] = 7; g[3][2] = 4; g[3][4] = 6;g[4][1] = 5; g[4][2] = 4; g[4][3] = 6; g[4][5] = 3;g[5][1]=4; g[5][4] = 3;System.out.println(dijkstra(g, n, target, k, value));}
}

知识点：
1.Arrays.fill(distance, Integer.MAX_VALUE);初始化数组；