Week 2 - 线性结构
第二周 线性结构
主要讲的是与链表、Stack（栈，LIFO）、Queue（队列，LILO）相关的数据结构实现以及相应的方法实现。
题1：一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
解决思路：
首先，多项式由链表构成，每一个节点对应一项，包含其指数以及系数。
加法
- 加法比较简单，利用两个cursor分别对应1个多项式，当指数相等时，系数相加，cursor均移动；当指数不等时，按指数大的取，对应的1个cursor移动。依次循环，直到两个cursor都到末尾。
乘法
- 首先确定项数较少的那一个多项式，拿它的每一项与另一个多项式相乘，并加到预先设定的空的多项式中，然后cursor往后移动一项。依次循环直至cursor到末尾。
import java.util.Scanner;
public class PolynMerge {
private Node head;
private Node end;
private int n;
private static class Node
{
private int coef;
private int expn;
private Node next;
public Node()
{ }
public Node(int coef, int expn)
{
this.coef = coef;
this.expn = expn;
}
}
public PolynMerge()
{
head = null;
end = null;
n = 0;
}
public void add(int coef, int expn)
{
Node newNode = new Node(coef, expn);
if (end != null) {
end.next = newNode;
end = newNode;
}
else {
head = newNode;
end = newNode;
}
n++;
}
public PolynMerge polyAdd(Node node_p1, Node node_p2)
{
PolynMerge result = new PolynMerge();
while (node_p1 != null && node_p2 != null)
{
if (node_p1.expn == node_p2.expn) {
int sum = node_p1.coef + node_p2.coef;
if (sum != 0)
result.add(sum, node_p1.expn);
node_p1 = node_p1.next;
node_p2 = node_p2.next;
}
else if (node_p1.expn > node_p2.expn) {
if (node_p1.coef != 0)
result.add(node_p1.coef, node_p1.expn);
node_p1 = node_p1.next;
}
else {
if (node_p1.coef != 0)
result.add(node_p2.coef, node_p2.expn);
node_p2 = node_p2.next;
}
}
while (node_p1 != null) {
result.add(node_p1.coef,node_p1.expn);
node_p1 = node_p1.next;
}
while (node_p2 != null) {
result.add(node_p2.coef,node_p2.expn);
node_p2 = node_p2.next;
}
return result;
}
public PolynMerge polyMulti(Node p1, Node p2)
{
PolynMerge result = new PolynMerge();
Node p2_head = p2;
int coef, expn;
while (p1 != null)
{
PolynMerge p3 = new PolynMerge();
while (p2 != null)
{
coef = p1.coef * p2.coef;
expn = p1.expn + p2.expn;
if (coef != 0)
{
p3.add(coef,expn);
}
p2 = p2.next;
}
if (result.n != 0)
result = result.polyAdd(result.head, p3.head);
else
result = p3;
p2 = p2_head;
p1 = p1.next;
}
return result;
}
public String toString()
{
if (n == 0)
return "0 0";
else {
Node node = head;
StringBuilder s = new StringBuilder();
while(node != null)
{
s.append(node.coef + " " + node.expn + " ");
node = node.next;
}
s.deleteCharAt(s.length() - 1);
return s.toString();
}
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
while (in.hasNext())
{
PolynMerge p1 = new PolynMerge();
PolynMerge p2 = new PolynMerge();
int N = in.nextInt();
int i = 0;
while (i < N)
{
p1.add(in.nextInt(), in.nextInt());
i++;
}
N = in.nextInt();
i = 0;
while (i < N)
{
p2.add(in.nextInt(), in.nextInt());
i++;
}
System.out.println(p1.polyMulti(p1.head, p2.head));
System.out.println(p1.polyAdd(p1.head, p2.head));
}
}
}
题2：Reversing Linked List
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.
**Input Specification: **
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
**Output Specification: **
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
解题思路：
- 先按照顺序形成一个初始的链表（没有按给定的地址连接）
- 依据给定的头地址以及每个元素的自己的名义地址与下一节点的名义地址，再次形成一个需要的链表。
- 根据给定的k，判断当前cursor后的节点数量是否足以进行reverse。若可以reverse，则把链表的连接顺序反转[改变节点中next的值]，特别要注意首尾节点的指向【对于当前cursor所在的首节点指向末尾节点指向的节点，末尾节点应该被指向cursor的节点指向】。之后cursor移动到末尾之后，依次循环，直到cursor指向null。
- 最后根据reverse之后的链表顺序，修改节点中下一节点的名义地址。
import java.util.Scanner;
import java.util.regex.Pattern;
public class ReverseLinkV2 {
private Node head;
private Node end;
private int n;
private static class Node {
private String address;
private int num;
private String nextAddress;
private Node next;
public Node()
{ }
public Node(String address, int num, String nextAddress) {
this.address = address;
this.num = num;
this.nextAddress = nextAddress;
this.next = null;
}
}
public void add(String address, int num, String nextAddress) {
Node newNode = new Node(address, num, nextAddress);
if (head != null) {
end.next = newNode;
end = newNode;
}
else {
head = newNode;
end = newNode;
}
n++;
}
public void add(Node newNode) {
add(newNode.address, newNode.num, newNode.nextAddress);
}
public void delete(int num) {
Node node = head;
Node prev = null;
while (node != null && node.num != num) {
prev = node;
node = node.next;
}
if (node == null)
return;
else if (prev == null) {
head = node.next;
n--;
}
else {
prev.next = node.next;
n--;
}
}
public Node search(Node node, String address) {
while (node != null && !node.address.equals(address) ) {
node = node.next;
}
if (node != null)
return node;
else
return null;
}
public ReverseLinkV2 shift(String headAddress) {
ReverseLinkV2 trueList = new ReverseLinkV2();
trueList.add(search(head, headAddress));
delete(trueList.head.num);
Node newNode;
while (!trueList.end.nextAddress.equals("-1")) {
newNode = search(head, trueList.end.nextAddress);
trueList.add(newNode);
delete(trueList.end.num);
}
return trueList;
}
public void reverse(int k) {
Node end = hasSeqn(null, k);
Node current = head;
if (end != null) {
Node prev = reverse(end, k);
for (int i = 0; i < k ; i++) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
else
return;
}
public Node reverse(Node beforeHead, int k) {
Node end = hasSeqn(beforeHead, k);
Node head = beforeHead.next;
if (end != null) {
Node prev = reverse(end, k);
for (int i = 0; i < k; i++) {
Node next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
else {
return beforeHead.next;
}
}
public Node hasSeqn(Node head, int k) {
int i = 0;
if (head == null) {
head = this.head;
i = 1;
}
while (head != null && i < k) {
head = head.next;
i++;
}
return head;
}
public void correct() {
Node current = head;
while (current != null) {
if (current.next != null)
current.nextAddress = current.next.address;
else
current.nextAddress = "-1";
current = current.next;
}
}
public String toString() {
StringBuilder s = new StringBuilder();
if (n != 0) {
Node node = head;
while (node != null) {
s.append(node.address + " " + node.num + " " + node.nextAddress + "\n");
node = node.next;
}
s.deleteCharAt(s.length() - 1);
return s.toString();
}
else
return "Nothing in the list.";
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String address, nextAddress, headAddress;
int num, nNode, k;
while (in.hasNext()) {
ReverseLinkV2 originList = new ReverseLinkV2();
headAddress = in.next(Pattern.compile("[0-9]{5}"));
nNode = in.nextInt();
k = in.nextInt();
for (int i = 0; i < nNode; i++) {
address = in.next(Pattern.compile("[0-9]{5}"));
num = in.nextInt();
nextAddress = in.next(Pattern.compile("[0-9]{5}|-1"));
originList.add(address, num, nextAddress);
}
ReverseLinkV2 trueList = originList.shift(headAddress);
trueList.reverse(k);
trueList.correct();
System.out.println(trueList);
}
}
}
题3：Pop Sequence
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
Output Specification:
For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.
Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output:
YES
NO
NO
YES
NO
解题思路：
- 当一个数被Pop出来，则必须要满足两个条件：1）小于它的数必须全部被已经push进去；2）pop前，stack的数量不能超过M。
- 设定哨兵位，a[0] = 0。然后从index=1开始读取每一位数据，当比前一位小时，说明这个数和前一个pop出来的数之间并没有push新的数；当比前一位大时，说明和前一个被pop出来的数之间有push，通过差值判断中间Push了几个数，并判断pop前是否超过M。
import java.util.Scanner;
public class StackPopSeq {
public static boolean isProb(int[] a, int M) {
int N = a.length;
int stNum = 0;
int maxNum = 0;
for (int i = 1; i < N; i++) {
if (a[i] < a[i-1])
stNum--;
else if (a[i] > maxNum) {
stNum = stNum + (a[i] - maxNum);
if (stNum > M)
return false;
maxNum = a[i];
stNum--;
}
else
return false;
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int M, N, K;
while (in.hasNext()) {
M = in.nextInt();
N = in.nextInt();
K = in.nextInt();
int[] testNums = new int[N+1];
testNums[0] = 0;
for (int i = 0; i < K; i++) {
int j = 1;
while (j < N+1)
testNums[j++] = in.nextInt();
if (isProb(testNums, M))
System.out.println("YES");
else
System.out.println("NO");
}
}
}
}
