mooc-ii

数据结构
mooc, 数据结构

mooc 数据结构第二节作业

一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

1
2
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例

1
2
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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
import java.util.Scanner;
class Node {
    Node next;
    int value;
    int exp;
    public Node(int value, int exp) {
        this.value = value;
        this.exp = exp;
    }
    public void add(int value, int exp) {
        if(this.next == null) {
            this.next = new Node(value, exp);
        } else {
            this.next.add(value, exp);
        }
    }
}
public class Main {
 
    public static Node funAdd(Node p1, Node p2) {
        int value = 0, exp = 0;
        Node p3 = null;
        while(p1 != null && p2!= null) {
            if(p1.exp > p2.exp) {
                if (p3 == null) {
                    p3 = new Node(p1.value, p1.exp);
                } else {
                    p3.add(p1.value, p1.exp);
                }
                p1 = p1.next;
            } else if (p1.exp < p2.exp) {
                if(p3 == null) {
                    p3 = new Node(p2.value, p2.exp);
                } else {
                    p3.add(p2.value, p2.exp);
                }
                p2 = p2.next;
            } else if (p1.exp == p2.exp) {
                if (p1.value + p2.value == 0) {
                    value = 0;
                    exp = 0;
                } else {
                    value = p1.value + p2.value;
                    exp = p1.exp;
                }
                if (p3 == null) {
                    p3 = new Node(value, exp);
                } else {
                    p3.add(value, exp);
                }
                p1 = p1.next;
                p2 = p2.next;
            }
        }
        while (p1 != null) {
            if (p3 == null) {
                p3 = new Node(p1.value, p1.exp);
            } else {
                p3.add(p1.value, p1.exp);
            }
            p1 = p1.next;
        }
        while (p2 != null) {
            if (p3 == null) {
                p3 = new Node(p2.value, p2.exp);
            } else {
                p3.add(p2.value, p2.exp);
            }
            p2 = p2.next;
        }
        return p3;
    }
  
    public static void print(Node p) {
        if (p.value == 0) {
            System.out.println("0 0");
        } else {
            while (p != null) {
                if (p.value != 0) {
                    System.out.print(p.value + " " + p.exp);
                }
                p = p.next;
                if (p != null) {
                    if (p.value != 0) {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }
    public static Node funMulti(Node p1, Node p2) {
        int value = 0, exp = 0;
        Node temp = p2;
        Node p = null, p3 = null;
        int i = 1;
        while (p1 != null) {
            while (p2 != null) {
                if (p1.value * p2.value == 0) {
                    value = 0;
                    exp = 0;
                } else {
                    value = p1.value*p2.value;
                    exp = p1.exp + p2.exp;
                }
                if (i == 1) {
                    if (p == null) {
                        p = new Node(value, exp);
                    } else {
                        p.add(value, exp);
                    }
                } else {
                    if (p3 == null) {
                        p3 = new Node(value, exp);
                    } else {
                        p3.add(value, exp);
                    }
                }
                p2 = p2.next;
            }
            i = 2;
            p = funAdd(p, p3);
            p1 = p1.next;
            p2 = temp;
            p3 = null;
        }
        return p;
    }
    public static Node scanIn(Scanner scanner,int T, Node p) {
        while(T-- != 0) {
            int value = scanner.nextInt();
            int exp = scanner.nextInt();
            if (p == null) {
                p = new Node(value, exp);
            } else {
                p.add(value,exp);
            }
        }
        return p;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Node p1 = null, p2 = null;
        int T1 = scanner.nextInt();
        int temp1 = T1;
        p1 = scanIn(scanner, T1, p1);
        int T2 = scanner.nextInt();
        int temp2 = T2;
        if (T2 == 0) {
            p2 = new Node(0, 0);
        }
        p2 = scanIn(scanner, T2, p2);
        if (temp1 != 0 && temp2 != 0) {
            Node p = funMulti(p1, p2);
            print(p);
        } else {
            System.out.println("0 0");
        }
        Node p = funAdd(p1, p2);
        print(p);
    }
}

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 (≤10
​5
​​ ) 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:

1
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:

1
2
3
4
5
6
7
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

1
2
3
4
5
6
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        int first, n, k;
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = buf.readLine().split(" ");
        first = Integer.parseInt(str[0]);
        n = Integer.parseInt(str[1]);
        k = Integer.parseInt(str[2]);
        int temp;
        int[] data = new int[100005];
        int[] next = new int[100005];
        for (int i = 0; i < n; i++) {
            str = buf.readLine().split(" ");
            temp = Integer.parseInt(str[0]);
            data[temp] = Integer.parseInt(str[1]);
            next[temp] = Integer.parseInt(str[2]);
        }
        
        buf.close();
        int[] list = new int[n];
        int sum = 0;
        while (first != -1) {
            list[sum++] = first;
            first = next[first];
        }
        int[] result = new int[100005];
        for (int i = 0; i < sum; i++) {
            result[i] = list[i];
        }
        for (int i = 0; i < k; i++) {
            result[i] = list[k - 1 - i];
        }
        for (int i = 0; i < sum - 1; i++) {
            System.out.printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
        }
        System.out.printf("%05d %d -1\n", result[sum-1] , data[result[sum-1]]);
    }
}

但是运行时间方面不如C++，C++版本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
int main() {
    int first, k, n;
    cin >> first >> n >> k;
    // 把地址为temp的数的数值存入data[temp]中，把temp的下一个结点的地址存入next[temp]中。
    int temp;
    int data[100005];
    int next[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp];
        cin >> next[temp];
    }
    
    int list[100005];
    int sum = 0;//不一定所有的输入的结点都是有用的，加个计数器
    while (first != -1) {
        list[sum++] = first;
        first = next[first];
    }
    int result[100005];
    for (int i = 0; i < sum; i++) {
        result[i] = list[i];
    }
    
    for (int i = 0; i < (sum - sum % k); i++) {
        result[i] = list[i / k * k + k - 1 - i % k];
    }
    
    
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
    printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);
    return 0;
}

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:

1
2
3
4
5
6
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:

1
2
3
4
5
YES
NO
NO
YES
NO

思路：

按照要求进行模拟。先把输入的序列接收进数组v。然后按顺序1~n把数字进栈，每进入一个数字，判断有没有超过最大范围，超过了就break。如果没超过，设current = 1，从数组的第一个数字开始，看看是否与栈顶元素相等，while相等就一直弹出栈，不相等就继续按顺序把数字压入栈~最后根据变量flag的bool值输出yes或者no

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String[] row = buf.readLine().split(" ");
        int m = Integer.parseInt(row[0]);
        int n = Integer.parseInt(row[1]);
        int k = Integer.parseInt(row[2]);
        for (int i = 0; i < k; i++) {
            boolean flag = false;
            Stack<Integer> st = new Stack<Integer>();
            int[] v = new int[n+1];
            row = buf.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                v[j] = Integer.parseInt(row[j - 1]);
            }
            int current = 1;
            for (int j = 1; j <= n; j++) {
                st.push(j);
                if (st.size() > m) break;
                while (!st.isEmpty() && st.peek() == v[current]) {
                    st.pop();
                    current++;
                }
            }
            if (current == n+1) flag = true;
            if (flag) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}
Compartir Comentarios