新学期开始了，小哈是小哼的新同，小哼向小哈询问QQ号，小哈当然不会直接告诉小哼。所以小哈给了小哼一串加密过的数字，同时小哈也告诉了小哼解密规则。规则是这样的：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数再放到这串数的末尾，再将第5个数删除……直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是小哈的QQ啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 7 5 8 9 2 4”。解密后小哈的QQ号应该是“6 1 5 9 4 7 2 8 3”。
输入格式:
只有2行 第1行有一个整数n （1<=n<=100000） 第2行有n个整数为加密过的QQ号，每个整数之间用空格隔开。每个整数在1~9之间。输出格式:
只有一行，输出解密后的QQ号。限制:
每个测试点1秒 50%的数据1<=n<=10000 100%的数据1<=n<=100000样例 1 :
输入: 9 6 3 1 7 5 8 9 2 4输出: 6 1 5 9 4 7 2 8 3 package com.qianwei.chapter2; import java.util.Arrays; public class QueueTest1 { public static void main(String[] args) { int[] a = {6,3,1,7,5,8,9,2,4}; int[] q = Arrays.copyOf(a, 100); int head = 0; int tail = 9; while (head < tail) { System.out.print(q[head]+" "); head++; q[tail] = q[head]; tail++; head++; } } }
package com.qianwei.chapter2; import java.util.Scanner; class Queue { int[] data = new int[100]; int head; int tail; } public class QueueTest2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Queue q = new Queue(); q.head = 0; q.tail = 0; for (int i=0;i<9;i++) { q.data[q.tail] = sc.nextInt(); q.tail++; } while (q.head < q.tail) { System.out.print(q.data[q.head]+" "); q.head++; q.data[q.tail] = q.data[q.head]; q.tail++; q.head++; } sc.close(); } }
package com.qianwei.chapter2; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class QueueTest3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Deque<Integer> q = new LinkedList<Integer>(); for (int i=0;i<9;i++) q.offer(sc.nextInt()); while (!q.isEmpty()) { System.out.print(q.poll()+" "); Integer t = q.poll(); if (q.isEmpty()) { //如果此时队列为空，则跳出循环 System.out.print(t); break; } q.offer(t); } sc.close(); } }
“xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列，如“席主席”、“记书记”、“aha”和“ahaha”均是回文，但“ahah”不是回文。输入一行字符（仅包含小写英文字母a~z）请判断这行字符串是否为回文。
输入格式:
只有一行，仅包含小写英文字母a~z的字符串，长度小于等于100。输出格式:
只有一行，如果是回文请输出YES，不是回文则输出NO，请注意大小写。样例 1 :
输入: ahah输出: NO样例 2 :
输入: ahaha输出: YESpackage com.qianwei.chapter2; import java.util.Scanner; public class StackTest1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[] a = new char[100]; char[] s = new char[100]; a = sc.next().toCharArray(); int len = a.length; int mid = len/2-1; int top = 0; int next; for (int i=0;i<=mid;i++) s[++top] = a[i]; if (len%2 == 0) next = mid+1; else next = mid+2; for (int i=next;i<len;i++) { if (a[i] != s[top]) break; top--; } if (top == 0) System.out.println("Yes"); else System.out.println("No"); sc.close(); } }
package com.qianwei.chapter2; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class StackTest2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); int len = s.length(); int mid = len/2-1; Deque<Character> stack = new LinkedList<Character>(); for (int i=0;i<=mid;i++) stack.push(s.charAt(i)); int next; if (len%2 == 0) next = mid+1; else next = mid+2; for (int i=next;i<len;i++) { if (s.charAt(i) != stack.pop()) break; } if (stack.isEmpty()) System.out.println("Yes"); else System.out.println("No"); sc.close(); } }
package com.qianwei.chapter2; import java.util.Scanner; public class StackTest3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); String t = new StringBuffer(s).reverse().toString(); if (s.equals(t)) System.out.println("Yes"); else System.out.println("No"); sc.close(); } }
在编程当中我们只会用到三种括号：圆括号()，方括号[]和花括号{}，编译器在编译的时候会检查括号是否正确匹配。例如{[()]}、{()[]{}}都是合法的匹配。但是([)]则是不合法的匹配。请编写一个程序来判断输入的括号序列是否合法。
输入格式:
只有一行，为( ) [ ] { }组成的序列，长度不超过100输出格式:
只有一行，如果是合法匹配则输出YES，不合法则输出NO，请注意大小写限制:
每个测试点1秒样例 1 :
输入: {([()]{})}输出: YES package com.qianwei.chapter2; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class StackTest4 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); Deque<Character> stack = new LinkedList<Character>(); if (s.charAt(0)==')' || s.charAt(0)==']' || s.charAt(0)=='}') System.out.println("No"); stack.push(s.charAt(0)); for (int i=1;i<s.length();i++) { if (stack.peek()=='(' && s.charAt(i)==')') stack.pop(); else if (stack.peek()=='[' && s.charAt(i)==']') stack.pop(); else if (stack.peek()=='{' && s.charAt(i)=='}') stack.pop(); else stack.push(s.charAt(i)); } if (stack.isEmpty()) System.out.println("Yes"); else System.out.println("No"); sc.close(); } }
星期天小哼和小哈约在一起玩桌游，他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的：将一副扑克牌平均分成两份，每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小哼刚打出的扑克牌的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时，游戏结束，对手获胜。
假如游戏开始时，小哼手中有 6 张牌，顺序为 2 4 1 2 5 6，小哈手中也有 6 张牌，顺序为 3 1 3 5 6 4，最终谁会获胜呢？现在你可以拿出纸牌来试一试。接下来请你写一个程序来自动判断谁将获胜。这里我们做一个约定，小哼和小哈手中牌的牌面只有 1~9。
package com.qianwei.chapter2; import java.util.Scanner; class QueueFish { int[] data = new int[1000]; int head; int tail; } //指向栈底时，top==1; class Stack { int[] data = new int[10]; int top; } public class KittenFishing1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); QueueFish q1 = new QueueFish(); QueueFish q2 = new QueueFish(); Stack s = new Stack(); int[] book = new int[10]; int t; q1.head = 0; q1.tail = 0; q2.head = 0; q2.tail = 0; s.top = 0; for (int i=0;i<6;i++) q1.data[q1.tail++] = sc.nextInt(); for (int i=0;i<6;i++) q2.data[q2.tail++] = sc.nextInt(); while (q1.head<q1.tail && q2.head<q2.tail) { t = q1.data[q1.head]; System.out.println(t); if (book[t] == 0) { q1.head++; s.data[++s.top] = t; book[t] = 1; }else { q1.head++; q1.data[q1.tail++] = t; while (s.data[s.top] != t) { book[s.data[s.top]] = 0; q1.data[q1.tail++] = s.data[s.top--]; } book[s.data[s.top]] = 0; q1.data[q1.tail++] = s.data[s.top--]; } if (q1.head == q1.tail) break; t = q2.data[q2.head]; System.out.println(t); if (book[t] == 0) { q2.head++; s.data[++s.top] = t; book[t] = 1; }else { q2.head++; q2.data[q2.tail++] = t; while (s.data[s.top] != t) { book[s.data[s.top]] = 0; q2.data[q2.tail++] = s.data[s.top--]; } book[s.data[s.top]] = 0; q2.data[q2.tail++] = s.data[s.top--]; } } if (q2.head == q2.tail) { System.out.println("小哼win"); System.out.println("小哼当前手中的牌是："); for (int i=q1.head;i<q1.tail;i++) System.out.print(q1.data[i]+" "); if (s.top>0) { System.out.println("\n桌子上的牌是："); for (int i=0;i<s.top;i++) //输出桌子上的牌不是按照出栈的顺序，而是相反的顺序输出 System.out.print(s.data[i+1]+" "); }else System.out.println("桌子上已经没有牌了"); }else { System.out.println("小哈win"); System.out.println("小哈当前手中的牌是："); for (int i=q2.head;i<q2.tail;i++) System.out.print(q2.data[i]+" "); if (s.top>0) { System.out.println("\n桌子上的牌是："); for (int i=0;i<s.top;i++) System.out.print(s.data[i+1]+" "); }else System.out.println("桌子上已经没有牌了"); } sc.close(); } }
package com.qianwei.chapter2; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class KittenFishing2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Deque<Integer> q1 = new LinkedList<Integer>(); Deque<Integer> q2 = new LinkedList<Integer>(); Deque<Integer> stack = new LinkedList<Integer>(); int[] book = new int[10]; for (int i=0;i<6;i++) q1.offer(sc.nextInt()); for (int i=0;i<6;i++) q2.offer(sc.nextInt()); while (!q1.isEmpty() && !q2.isEmpty()) { int t = q1.peek(); if (book[t] == 0) { q1.poll(); stack.push(t); book[t] = 1; }else { q1.offer(q1.poll()); while (stack.peek() != t) { book[stack.peek()] = 0; q1.offer(stack.pop()); } book[stack.peek()] = 0; q1.offer(stack.pop()); } if (q1.isEmpty()) break; t = q2.peek(); if (book[t] == 0) { q2.poll(); stack.push(t); book[t] = 1; }else { q2.offer(q2.poll()); while (stack.peek() != t) { book[stack.peek()] = 0; q2.offer(stack.pop()); } book[stack.peek()] = 0; q2.offer(stack.pop()); } } if (q2.isEmpty()) { System.out.println("小哼win"); System.out.println("小哼当前手中的牌是："); //一开始这样写运行结果老是有问题，后来发现原来是q1.size()不是固定不变的， //随着q1.poll()的执行，q1.size()的值也在变化，所以导致最终输出赢赢的人手中的牌不正确 // for (int i=0;i<q1.size();i++) // System.out.print(q1.poll()+" "); //改成这样就不会出现上面的那种情况了 while (!q1.isEmpty()) System.out.print(q1.poll()+" "); if (!stack.isEmpty()) { System.out.println("\n桌子上的牌是"); //这里也同样，stack.size()的值是随着stack.removeLast()的执行而变化 // for (int j=0;j<stack.size();j++) // System.out.print(stack.removeLast()+" "); while (!stack.isEmpty()) //输出桌子上的牌不是按照出栈的顺序，而是相反的顺序输出 System.out.print(stack.removeLast()+" "); }else System.out.println("桌子上已经没有牌了"); }else { System.out.println("小哈win"); System.out.println("小哈当前手中的牌是："); // for (int i=0;i<q1.size();i++) // System.out.print(q1.poll()+" "); while (!q2.isEmpty()) System.out.print(q2.poll()+" "); if (!stack.isEmpty()) { System.out.println("\n桌子上的牌是"); // for (int j=0;j<stack.size();j++) // System.out.print(stack.removeLast()+" "); while (!stack.isEmpty()) System.out.print(stack.removeLast()+" "); }else System.out.println("桌子上已经没有牌了"); } sc.close(); } }
用链表存储n个数，这n个数按从小到大的顺序输入。书上的C语言代码辣么辣么长，还有一堆指针指来指去，看着就烦，看我用Java几行代码就搞定。
package com.qianwei.chapter2; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class LinkedListTest1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List<Integer> list = new LinkedList<Integer>(); for (int i=0;i<n;i++) list.add(sc.nextInt()); for (int j=0;j<n;j++) System.out.print(list.get(j)+" "); sc.close(); } }
package com.qianwei.chapter2; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class LinkedListTest2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List<Integer> list = new LinkedList<Integer>(); for (int i=0;i<n;i++) list.add(sc.nextInt()); int insert = sc.nextInt(); int index = 0; for (int j=0;j<n;j++) { if (list.get(j) > insert) { index = list.lastIndexOf(list.get(j)); break; } } list.add(index, insert); for (int k=0;k<n;k++) System.out.print(list.get(k)+" "); sc.close(); } }
链表中的每一个结点只有两个部分。我们可以用一个数组 data 来存储每序列中的每一个数。那每一个数右边的数是谁，这一点该怎么解决呢？上一节中是使用指针来解决的，这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了。
package com.qianwei.chapter2; import java.util.Scanner; //有bug 如果插入的元素大于链表中所有的元素会出现bug,导致无法插入元素 public class LinkedListDemo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] data = new int[100]; int[] right = new int[100]; int n = sc.nextInt(); for (int i=0;i<n;i++) data[i] = sc.nextInt(); for (int i=0;i<n;i++) { if (i != n-1) right[i] = i+1; else right[i] = 0; } data[n] = sc.nextInt(); int t = 0; while (true) { if (data[right[t]]>data[n]) { right[n] = right[t]; right[t] = n; break; } t = right[t]; } t = 0; while (true) { System.out.print(data[t]+" "); t = right[t]; if (t == 0) break; } sc.close(); } }