寒假作业Day 12
一、选择题
队列是先进先出的线性表，既能插入数据，也能删除数据
A：ABCD，一进栈就出栈；B：DCBA，全部进栈之后再出栈
C：ACBD，先进A，然后出，进BC，然后出，最后进D然后再出
D：DCAB，CD限制了AB的顺序，所以出栈只有可能是BA，故D错误
有四个不同的组成：ABC,CBA,ACB,BAC
分别由这几个字符串组成：①“A”，“B”，“C”
②“CBA”
③“A”，“CB”
④”BA“，“C”
重复的是A和C，所以至多可以组成6个不同的字符串
4、已知栈 s 允许在两端出栈，但只允许在一端入栈;队列 Q 只允许在一 端入队列，在另一端出队列。设栈 s 和队列 Q 的初始状态为空, e1,e2,e3, e4,e5,e6 依次通过栈 S ,一个元素出栈后即进队列 Q ，则不可能得到的出队列的顺序是（ ）
A. e2,e4,e3,e5,e1,e6 B. e2,e5,e1,e3,e4,e6
C. e5,e1,e6,e3,e2,e4 D. e4,e1,e3,e5,e2,e6
按照123456的顺序进栈
A. e2,e4,e3,e5,e1,e6
这里详细写一下：1进栈；2进栈，2出栈；3，4进栈，然后一起出栈；5进栈，5和1一起出栈；6进栈，然后6出栈（这里都是从上方出栈）
B. e2,e5,e1,e3,e4,e6
这个顺序也看似合理，1，2进栈，2出栈；3，4，5进栈，5出栈；1，3出栈（从下面）；6进栈，4，6一起出栈（从下方）
C. e5,e1,e6,e3,e2,e4
这个顺序不太可能，因为 e5 在 e1 和 e6 之前出栈意味着 e5 是最早入栈的元素之一，但它不能是第一个入栈的元素，因为那样 e1 就不可能在 e5 之前出栈。同时，e2 和 e4 在 e3 之后出栈也不太可能，除非在它们入栈之前有其他元素已经出栈并入队列。这种顺序在标准栈操作中难以实现。（经过尝试，516可以，但后面的234出栈不可能是324这个样子）
D. e4,e1,e3,e5,e2,e6
1，2，3，4进栈，4出栈（从上面），1出栈（从下面），3再出栈（从上面）；5进栈，5和2一起出栈（从上面）；6进栈，6出栈
5、现有使用数组实现的一个循环队列， front 指向队列的首元素， rear 指向队列末尾元素的下一个位置， rear指向的位置不保存元素；循环队列长度为 N 。其队内有效长度为？（front和rear都是数组下标）（ ）
A. (rear - front + N) % N + 1
B. (rear - front + N) % N
C. (rear - front) % (N + 1)
D. (rear - front + N) % (N - 1)
选择B，考虑到循环队列的特性，我们不能简单地使用 rear - front 来计算差值，因为当 rear 小于 front 时，这种计算会得到一个负数。为了处理这种情况，我们可以加上队列的长度 N，然后使用模运算来确保结果是一个在 [0, N-1] 范围内的数。
因此，正确的计算公式是：
队内有效长度 = (rear - front + N) % N
二、编程题
typedef struct ListNode ListNode;
ListNode* CreateNode(int x){
ListNode* node=(ListNode*)malloc(sizeof(ListNode));
if(node==NULL){
perror("malloc fail");
return NULL;
}
node->val=x;
node->next=NULL;
return node;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
ListNode dummy; // 使用一个哑节点简化链表头部的处理
ListNode* tail = &dummy;
int carry = 0; // 初始化进位为0
while (l1 || l2 || carry) {
int sum = carry; // 初始化sum为进位值
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10; // 更新进位值
tail->next = CreateNode(sum % 10); // 创建新节点存储当前位的值
tail = tail->next; // 移动tail指针到下一个节点
}
return dummy.next; // 返回哑节点的下一个节点作为结果链表的头节点
}
照样还是用题目举个例子：
7->1->6 5->9->2
即617+295=912
*这里的代码是模拟了竖式相加进位的模式
*首先while(l1||l2||carry)，如果了l1和l2链表结束，并且carry=0，那么这个循环就直接退出，这种就可以判断一开始如果l1和l2都为空，或者l1与l2一个为空一个不为空的情况
*从7和5开始，sum=12，carry=1，进位1，于是tail->next为剩下来的约数2
*而1和9，约数为1（sum初始值为上一个carry），carry=1，进位1，这个位数为1
*6和2，约数为9，carry=0，不进位，这个尾数为9
*相信大家看了这个例子也能很容易搞懂
#define MAX(a,b) ((a)>(b)?(a):(b))
int maxDepth(char* s) {
int ans=0,size=0;
int len=strlen(s);
for(int i=0;i<len;i++){
if(s[i]=='('){
++size;
ans=MAX(ans,size);
}
else if(s[i]==')'){
--size;
}
}
return ans;
}
这道题很简单，遇到左括号size++，然后存储ans值，右括号–，自己写一个例子会很明晰
