一、前言
如果一直有看我的每周面試題的童鞋們厂财，應(yīng)該都知道芋簿，之前的面試題中很少或者說基本沒有程序題，可是開發(fā)崗位的面試是無法避免程序題的璃饱，因此這周來一提程序題与斤。
二、題目
在幼兒園有 n 個小朋友排列為一個隊伍，從左到右一個挨著一個編號為 ( 0 ~ n-1 ) 撩穿。其中有一些是男生磷支，有一些是女生，男生用 ’B’ 表示食寡，女生用 ’G’ 表示齐唆。小朋友們都很頑皮，當一個男生挨著的是女生的時候就會發(fā)生矛盾冻河。作為幼兒園的老師箍邮，你需要讓男生挨著女生或者女生挨著男生的情況最少。你只能在原隊形上進行調(diào)整叨叙，每次調(diào)整只能讓相鄰的兩個小朋友交換位置锭弊，現(xiàn)在需要盡快完成隊伍調(diào)整，你需要計算出最少需要調(diào)整多少次可以讓上述情況最少擂错。例如：
GGBBG -GGBGB -GGGBB
這樣就使之前的兩處男女相鄰變?yōu)橐惶幭噜徫吨停枰{(diào)整隊形 2 次
輸入描述:
輸入數(shù)據(jù)包括一個長度為 n 且只包含 G 和 B 的字符串. n 不超過 50.
輸出描述:
輸出一個整數(shù)，表示最少需要的調(diào)整隊伍的次數(shù)
輸入例子:
GGBBG
輸出例子:
2
三钮呀、解題
題目的意思應(yīng)該很好就能理解剑鞍，不能理解的看下給出的例子，基本就能知道題目表達的意思了爽醋。根據(jù)題目的意思蚁署，“男生挨著女生或者女生挨著男生的情況最少”，那么最終調(diào)整的隊形無非就兩個結(jié)果蚂四，第一：男生全部在左光戈，女生全部在隊列的右邊，中間只有一男一女是相挨著的遂赠。第二：要么就是反過來久妆，女生全部在左，男生在右跷睦。也就是假設(shè)長度為 8 的時候筷弦，只要調(diào)整為 BBBBGGGG 或者 GGGGBBBB 就行了。
這是根據(jù)第一個條件進行分析的結(jié)果抑诸，那么我們看第二個條件烂琴，“每次調(diào)整只能讓相鄰的兩個小朋友交換位置，且需要的是最少需要調(diào)整的情況” 哼鬓， 從上面可以知道监右，我們最終需要將隊形調(diào)整成 BBBBGGGG 或者 GGGGBBBB 就可以了，那么調(diào)整的時候我們只需要調(diào)整 B 或者 G 就可以了异希，意思就是說調(diào)整 B 的時候，G 不動，如果調(diào)整 G 称簿，B 不動扣癣。為什么呢？因為只動 B 和只動 G 是等價的憨降。
用 JAVA 來編程的話父虑，我們就只移動 B ,用一個 list 記錄每個 B 所在的位置（從 0 開始），比如 GGBBG , list 中有兩個值授药， 2 和 3 士嚎，大小為 2 ，如果序列為 2 的 B 移動到最左邊需要移動的次數(shù)是 2 次悔叽，也就變成 BGGBG莱衩，序列為 3 的 B 移動到最左邊需要移動的次數(shù)是 3 次，可是因為之前已經(jīng)移動號了一個娇澎，我們只需移動 2 次就行了笨蚁，也就是移動到第一次移動到最左邊的 B 的左邊；所以我們可以對當前每個 B 的下標求和趟庄，每進行一次有用的調(diào)整必然使當前的和 +1 或者 -1括细，最后我們只要計算出當前的和與最終結(jié)果的和的差。
public class AdjustFormation {
public static void main(String[] args) {
// 控制臺輸入
Scanner sc = new Scanner(System.in);
String s = sc.next();
sc.close();
int n = s.length();
if (n <= 0 || n > 50) {
throw new RuntimeException("the length is too long");
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == 'B') {
list.add(i);
}
}
int bSize = list.size();
int indexSum = 0;
for (int val : list) {
indexSum += val;
}
int left = indexSum - bSize * (bSize - 1) / 2;
int right = bSize * (n - 1) - indexSum - bSize * (bSize - 1) / 2;
// 移左 或者 移右 戚啥，選擇最少的
System.out.println(Math.min(left, right));
}
}
運行的結(jié)果：
