連結：https://www.nowcoder.com/questionTerminal/29d1622d47514670a85e98a1f47b8e2d
來源：牛客網
已知一種新的火星文的單詞由英文字母（僅小寫字母）組成，但是此火星文中的字母先後順序未知。給出一組非空的火星文單詞，且此組單詞已經按火星文字典序進行好了排序（從小到大），請推斷出此火星文中的字母先後順序。
連結：https://www.nowcoder.com/questionTerminal/29d1622d47514670a85e98a1f47b8e2d
來源：牛客網
輸入描述:
一行文本，為一組按火星文字典序排序好的單詞(單詞兩端無引号)，單詞之間通過空格隔開
輸出描述:
按火星文字母順序輸出出現過的字母，字母之間無其他字元，如果無法确定順序或者無合理的字母排序可能，請輸出"invalid"(無需引号)
示例一
輸入
z x
輸出
zx
示例2
輸入
wrt wrf er ett rftt
輸出
wertf
示例3
輸入
z x z
輸出
invalid
我每次做筆試題，看到題目長就可能靜不下心去看題，其實和做數學題一樣，題目越長越要靜下心來分析，挖掘關系
這道題的題目讓求火星文中的先後順序；
順序由已知的字元串來決定；
具體規則：給出的字元串按從小到大排序；
此時我們根據示例求解；
z x
因為z寫在了x前面；是以輸出為zx
wrt wrf er ett rftt
這道題大家可能有些疑惑，rftt不是将f寫在了t前面，那順序是不是werft呢，但是答案是wertf
我們仔細思量一下，題目中說的是此組單詞按照火星文字典序進行了排序，記住，是此組，不是每一個字母中的每一個字元都按照大小排序，它保證的是前一個字元總體小于後一個字元，可以把第一個字元看成一級比較，二級，三級……一次類推，首先第一個字元進行大小比較再進行第二個字元比較，根據題目中wrt 和 wrf 可以發現，t在f的後面，因為e在r的前面，是以後兩個字元的順序已經确定，而倒推法，加入f在t的前面，那麼前兩個字元串因為前兩個字元相同，那麼會wrf wrt這樣排序，勢必和原題相反，是以，我們比較的根據是前一個和後一個字元的第一個不同的字元來排序
public class IsSort {
//用map記錄圖，因為有26個字元，直接用二維數組可以表示橫縱坐标（兩個字元）之間的關系，
private static int[][]map=new int[26][26];
//用來記錄目前字元是否是圖中的，圖中有且未被選為1，已被選即為0
private static int[]indegree=new int[26];
//标記數組，标記字元是否在圖中出現
private static boolean[]flag=new boolean[26];
//set集合用來加入字元，統計字元個數，好處是去重
private static Set<Character> set=new HashSet<>();
//結果集
private static List<Character> ans=new ArrayList<>();
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String[]input=sc.nextLine().split(" ");//生成數組
//int maxLen=0;
//建立圖
build(input);
//進行排序
topolpgy();
if(ans.size()==set.size()){
for(Character c:ans){
System.out.print(c);
}
}else {
System.out.println("invalid");
}
}
private static void build(String[] strs) {
String pre=strs[0];//将前一個字元儲存
for(char c:pre.toCharArray()){
set.add(c);//加入set集合
}
for(int i=1;i<strs.length;i++){
String cur=strs[i];//将目前字元記錄
for(char c:cur.toCharArray()){
set.add(c);//将不同字元加入
}
//循環比較第一個不同的元素，并且加入map
for(int j=0;j<Math.min(pre.length(),cur.length());j++){
if(pre.charAt(j)==cur.charAt(j)) continue;//如果相同就繼續
if(map[pre.charAt(j)-'a'][cur.charAt(j)-'a']==1)break;//說明這組資料已經加入過圖了，沒必要
map[pre.charAt(j)-'a'][cur.charAt(j)-'a']=1;//值設為1，說明pre.charAt(j)-'a'<cur.charAt(j)-'a'
indegree[cur.charAt(j)-'a']+=1;//向後标記，标記目前數組中的那個不同的字元出現的次數，也就是稍大一點的
flag[pre.charAt(j)-'a']=true;//标記，用來得知在圖中已經有了
flag[cur.charAt(j)-'a']=true;
break;//因為我們隻要得知第一個不同的字元即可，是以直接break
}
pre=cur;//維護pre
}
}
private static void topolpgy() {
//set中的個數就是所有字元的個數
while (ans.size()<set.size()){
//先找到第一個字元，因為當時标記是 indegree[cur.charAt(j)-'a']+=1;是以第一個字元串的那個不同的字元就漏掉了，也就是最小的那個
int cnt=0;
for(int i=0;i<indegree.length;i++){
if(indegree[i]==0&&flag[i]) cnt++;
}
if(cnt!=1)break;//也就是說如果找到的不是一個，就是錯的
//開始找
for(int i=0;i<indegree.length;i++){
if(indegree[i]==0&&flag[i]){//第一次循環找到的就是最小的字元，而後每次操作indegree[j]--，是以再找就是下一個最小的
ans.add((char)('a'+i));//按順序加入
flag[i]=false;//已經加入結果集，是以設為false
for(int j=0;j<26;j++){//在二維數組中找i這個字元和j字元之間的大小關系
if(map[i][j]==0)continue;//是0說明沒關系
indegree[j]--;//将j出現的次數-1
map[i][j]=0;//維護map，置為0
}
}
}
}
}
}
這是代碼，是看評論區寫的；
沒看懂别着急；
一步一步來帶你調試，還原程式運作的過程；
build函數
wrt wrf
首先是這兩個字元開始比較
map[t][f]=1;(這裡使用字元，真正執行是轉化成數字哦）
indegree[f]=1;
flag(t)=true;
flag(f)=true;
wrf er
map[w][e]=1;
indegree[e]=1;
flag(w)=true;
flag(e)=true;
er ett
map[r][t]=1;
indegree[t]=1;
flag(r)=true;
flag(t)=true;
ett rftt
map[e][r]=1;
indegree[r]=1;
flag(e)=true;
flag(r)=true;
topolpgy函數
根據indegree[i]==0&&flag[i]第一次找到最小
map[22][4]即map[w][e]=1,且indegree[w]沒有标記過
ans.add(w);
indegree[e]--;
map[w][e]=0;
因為上一步操作将indegree[e]--;是以變為0
這次找到的就是map[e][r];
ans.add(e);
indegree[r]--;
map[e][r]=0;
以此類推，其實橫縱坐标就保證了有序性。
2110年美團外賣火星第3000号配送站點有26名騎手，分别以大寫字母A-Z命名，是以可以稱呼這些騎手為黃家騎士特工A，黃家騎士特工B…黃家騎士特工Z，某美團黑珍珠餐廳的外賣流水線上會順序産出一組包裹，美團配送排程引擎已經将包裹配置設定到騎手，并在包裹上粘貼好騎手名稱，如RETTEBTAE代表一組流水線包裹共9個，同時配置設定給了名字為A B E R T的5名騎手。請在不打亂流水線産出順序的情況下，把這組包裹劃分為盡可能多的片段，同一個騎手隻會出現在其中的一個片段，傳回一個表示每個包裹片段的長度的清單。
連結：https://www.nowcoder.com/questionTerminal/80fdfb1b65e149959fc1088bd3f9692e
來源：牛客網
輸入描述:
輸入資料隻有一行，為一個字元串(不包含引号)，長度不超過1000，隻包含大寫字母’A’到’Z’，字元之間無空格。
輸出描述:
輸出每個分割成片段的包裹組的長度，每個長度之間通過空格隔開
示例1
輸入
MPMPCPMCMDEFEGDEHINHKLIN
輸出
9 7 8
說明
劃分結果為MPMPCPMCM,DEFEGDE,HINHKLIN。
每個騎手最多出現在一個片段中。
像MPMPCPMCMDEFEGDE,HINHKLIN的劃分是錯誤的，因為劃分的片段數較少。
這道題是求劃分字段開始的下标；
我一開始的想法是将每個字元的下标存入map中，以map<String,List>的形式存儲，然後因為不知怎麼控制退出條件，然後就沒有做下去了
看了評論之後，發現答主雙指針用的很妙；
public static void cutLen(String s){
int i=0,j=0,len=s.length();
while (j<len){
char c=s.charAt(j);
int tail=s.lastIndexOf(c);
int pre=j;
i=j+1;
j=tail;
while (i<j){
char inner=s.charAt(i);
j=Math.max(j,s.lastIndexOf(inner));
i++;
}
j++;
System.out.print(j-pre+" ");
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
cutLen(s);
}
打車派單場景, 假定有N個訂單， 待配置設定給N個司機。每個訂單在比對司機前，會對候選司機進行打分，打分的結果儲存在N*N的矩陣A， 其中Aij 代表訂單i司機j比對的分值。
假定每個訂單隻能派給一位司機，司機隻能配置設定到一個訂單。求最終的派單結果，使得比對的訂單和司機的分值累加起來最大，并且所有訂單得到配置設定。
示例1
輸入
3
1.08 1.25 1.5
1.5 1.35 1.75
1.22 1.48 2.5
輸出
5.25
1 2
2 1
3 3
這道題我走了幾個坑，應該是找到最大值，而我找的是每一列的最大值
和二維數組有關的好多都是DFS，回溯；比如機器人路徑問題，n皇後問題；
這道題需要行和列一起結合來考慮；
這種DFS問題好難啊；
import java.util.Scanner;
public class Main {
static double[][] order;
static boolean[] isAssigned;
static int[] path;
static int[] resPath;
static double max=-1;
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
order=new double[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
order[i][j]=in.nextDouble();
}
}
isAssigned=new boolean[n];
path=new int[n];
resPath=new int[n];
dfs(0,path, 0);
System.out.println(String.format("%.2f", max));
for(int i=0; i<n; i++){
System.out.println((i+1)+" "+Math.round(resPath[i]));
}
}
static void dfs(int now, int[] path, double value){
if(now<path.length){
for(int i=0; i<path.length; i++){
if(!isAssigned[i]){
path[now]=i+1;
isAssigned[i]=true;
dfs(now+1, path, value+order[now][i]);
isAssigned[i]=false;
}
}
}else{
if(value>max){
max=value;
System.arraycopy(path,0,resPath,0,path.length);
}
}
}
}
明天調試一遍；
給出兩個字元串，分别是模式串P和目标串T，判斷模式串和目标串是否比對，比對輸出 1，不比對輸出 0。模式串中‘？’可以比對目标串中的任何字元，模式串中的 ’*’可以比對目标串中的任何長度的串，模式串的其它字元必須和目标串的字元比對。例如P=a?b，T=acb，則P 和 T 比對。
連結：https://www.nowcoder.com/questionTerminal/2e2510b2e41e4d3b922416e51afc077b
來源：牛客網
輸入描述:
輸入第一行包含一個字元串p， (1 ≤ |p| ≤ 20).
輸入第二行包含一個字元串t， (1 ≤ |t| ≤ 20).
輸出描述:
輸出僅包含0和1的整數，0表示p和t不比對，1表示p和t比對。
示例1
輸入
a?b
ab
輸出
0
示例2
輸入
a*b
ab
輸出
1
示例3
輸入
a*b
a(cb
輸出
1
這道題力扣好像有；主要是字元串問題，比起KMP還算簡單；
import java.util.*;
public class Main
{
public static void main(String[] args){
System.out.print(result());
}
public static int result(){
Scanner sc = new Scanner(System.in);
String str=sc.nextLine();
String str2=sc.nextLine();
char[] strArray=str.toCharArray();
char[] strArray2=str2.toCharArray();
int arrayseq=0;
for(int i=0;i<strArray.length;i++){
if(strArray[i]=='?'){
arrayseq++;
continue;
}
else if(strArray[i]=='*'){
while (true){
if (i<strArray.length-1&& strArray[i+1]=='*') {
i++;
}
else {
break;
}
}
if(i==strArray.length-1){
return 1;
}
else{
for(int j=arrayseq;j<strArray2.length;j++){
if(strArray[i+1]==strArray2[j]){
arrayseq=j-1;
break;
}
}
}
}
else{
if(strArray[i]!=strArray2[arrayseq]){
return 0;
}
}
arrayseq++;
if ((i+1)==strArray.length-1&&arrayseq<strArray2.length-1){
return 0;
}
else if (arrayseq==strArray2.length-1&&(i+1)<strArray.length-1){
return 0;
}
}
return 1;
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)