刷題小記：

本期涉及ACM模式下棧和鏈表的構建與使用，值得學習。

卡瑪網15.神秘字符（卡瑪網15.神秘字符）

題目分析：

若給定2行字符串，其中第一個串的長度為偶數，現要求把第二個串插入到第一個串的正中央并輸出。

輸入數據首先給出一個整數n，表示測試數據的組數，每組2行，每行一個字符串，長度大于0小于50，每組第一行的字符串的長度必為偶數。

輸出時每組輸出占一行即可。

解題思路：

分組讀入，借助StringBuilder構造。

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) { // 處理多組輸入int n = in.nextInt();in.nextLine(); // 消耗換行符while (n-- > 0) {String s1 = in.nextLine();String s2 = in.nextLine();StringBuilder sb = new StringBuilder(s1);sb.insert(sb.length() / 2, s2);System.out.println(sb.toString());}}in.close();}
}

卡碼網16.位置互換（卡碼網16.位置互換）

題目分析：

輸入包含多組測試數據，第一行是一個整數n，表示有且只有n組測試數據，每組測試數據為一行長度為偶數的字符串（串長不超過50）。

請為每組測試數據輸出奇偶位互換后的結果，每組輸出占一行。

解題思路：

借助StringBuilder進行構造，每2個字符一對遍歷字符串，每對字符使用Swap進行交換（添入StringBuilder的次序交換）。

import java.util.*;
public class Main{public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNext()) {int n = in.nextInt();in.nextLine();// 消耗換行符while(n-- > 0) {String s = in.nextLine();StringBuilder sb = new StringBuilder();for(int i = 0; i < s.length(); i+=2) {sb.append(s.charAt(i+1));sb.append(s.charAt(i));}System.out.println(sb.toString());}}in.close();}
}

卡瑪網17.出棧合法性（卡瑪網17.出棧合法性）

題目分析：

已知自然數1，2，......，N（1 <= N <= 100）依次入棧，請問接下來的各組序列是否為合法的出棧序列。

輸入包含多組測試數據。每組測試數據的第一行為整數N，當N = 0時輸入結束；第二行為N個正整數，以空格隔開，為出棧序列。

輸出Yes或No表示每組出棧序列是否合法。

解題思路：

觀察示例可以發現：出棧序列并非先將所有1~N的自然數入棧后再出棧，而是邊入棧邊適時按出棧序列出棧。

1. 以3 4 2 1 5為例：

• • 1入棧，2入棧，3入棧，3出棧—— 12
  • 4入棧，4出棧—— 12
  • 2出棧—— 1
  • 1出棧—— 棧空
  • 5入棧，5出棧——棧空

• 這是合法的。

1. 以3 5 1 4 2為例：

• • 1入棧，2入棧，3入棧，3出棧—— 12
  • 4入棧，5入棧，5出棧—— 124
  • 1出棧——124，棧頂為4，無法實現

• 這是不合法的。

解題步驟：

觀察兩個示例可以發現解題步驟如下：

• 將i屬于1~N的自然數依次入棧，且從j = 0處開始遍歷出棧序列
• 每次先將i入棧，再循環檢查棧頂元素top與出棧序列下標j處的curNum

• • 若相同，則top出棧，j++
  • 若不相同，結束循環

• 入棧序列全部完畢，棧不為空，那么結果為No。

import java.util.*;
public class Main{public static void main(String[] args){Scanner in = new Scanner(System.in);while(in.hasNext()){int N = in.nextInt();if (N == 0) break;in.nextLine();// 消耗換行符String[] popList = in.nextLine().split(" ");String res;Deque<Integer> stack = new ArrayDeque<>();for(int i = 1, j = 0; i <= N; i++) {stack.push(i);// 依次入棧while(j < N && !stack.isEmpty()) {// 依次出棧int top = stack.peek();int curNum = Integer.parseInt(popList[j]);if (top == curNum) {stack.pop();j++;} else {break;}}}if (stack.isEmpty()) res = "Yes";else res = "No";System.out.println(res);}in.close();}
}

卡碼網18.鏈表的基本操作（卡碼網18.鏈表的基本操作）

題目分析：

按要求實現鏈表及其基本操作

輸入描述：

輸入數據只有一組，第一行有n+1個整數，第一個整數是這行余下的整數數目n，后面是n個整數，用于初始化鏈表，且輸入的順序與鏈表中的順序相反。

第二行有一個整數m，表示接下來有m行，每行有一個字符串代表對鏈表的操作。

輸出描述：

每個操作的含義及其對應的輸出如下：

1. "get"，代表獲得第a個元素（a從1開始計數）

1. 1. 獲取成功則輸出該元素
   2. 獲取失敗則輸出"get fail"

1. "delete"，代表刪除第a個元素（a從1開始計數）

1. 1. 刪除成功則輸出"delete OK"
   2. 刪除失敗則輸出"delete fail"

1. "insert"，其后跟著兩個用空格隔開的整數a和e，代表在第a個位置前面插入e（a從1開始計數）

1. 1. 插入成功則輸出"insert OK"
   2. 插入失敗則輸出"insert fail"

1. "show"，直接打印鏈表全部內容

1. 1. 鏈表不為空，用空格間隔輸出鏈表中的全部元素
   2. 鏈表為空，輸出"Link list is empty"

解題思路：

頭插法實現倒序插入。

按要求初始化自定義鏈表的數據結構及其操作。

注意：

• insert方法在a為鏈表長度加1時，表示在鏈表末尾插入，若a超過此值，則插入失敗。
• insert方法和delete方法可能改變頭節點，需特殊處理（或者給鏈表增設虛擬頭節點dumpyHead以解決該問題）

import java.util.*;
public class Main{static class ListNode{int val;ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;this.next = null;}public ListNode(ListNode next) {this.next = next;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}static class MyLinkedList{ListNode head;public MyLinkedList() {this.head = null;};public void add(int val) {// 頭插法實現倒序地添加元素head = new ListNode(val, head);}public String get(int a) {ListNode cur = head;int num = 1;while(cur.next != null && num != a) {cur = cur.next;num++;}if (num == a) return Integer.toString(cur.val);else return "get fail";}public String delete(int a) {if (a == 1) {// 特殊處理a為1時的情況，更新頭節點if (head != null) {head = head.next;return "delete OK";}else {return "delete fail";}}ListNode pre = new ListNode(head);int num = 1;while(pre.next != null && num != a) {pre = pre.next;num++;}if (pre.next != null && num == a) {pre.next = pre.next.next;return "delete OK";}else {return "delete fail";}}public String insert(int a, int e) {if (a == 1) {// 特殊處理a為1時的情況，更新頭節點if (head == null) {head = new ListNode(e);} else {head = new ListNode(e, head);}return "insert OK";}ListNode pre = new ListNode(head);int num = 1;while(pre.next != null && num != a) {pre = pre.next;num++;}if (num == a) {pre.next = new ListNode(e, pre.next);return "insert OK";} else {return "insert fail";}}public String show() {StringBuilder sb = new StringBuilder();ListNode cur = head;while(cur != null) {if (cur != head) sb.append(" ");sb.append(cur.val);cur = cur.next;}if (sb.length() > 0) return sb.toString();else return "Link list is empty";}}public static void main(String[] args) {Scanner in = new Scanner(System.in);MyLinkedList list = new MyLinkedList();while(in.hasNext()) {int n = in.nextInt();while(n-- > 0) {int val = in.nextInt();list.add(val);}int m = in.nextInt();in.nextLine();// 消耗換行符while(m-- > 0) {String[] opt = in.nextLine().split(" ");switch (opt[0]) {case "get":System.out.println(list.get(Integer.parseInt(opt[1])));break;case "delete":System.out.println(list.delete(Integer.parseInt(opt[1])));break;case "insert":System.out.println(list.insert(Integer.parseInt(opt[1]), Integer.parseInt(opt[2])));break;case "show":System.out.println(list.show());break;default:break;}}}in.close();}
}