dsaHomeworkTemp/content.tex at main · hakuna-max/dsaHomeworkTemp · GitHub

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
%!TEX root = main.tex
% !TEX encoding = UTF-8
% content.tex
% 请在这里撰写你所有的作业内容

\section{}

请完成Leetcode上的“接雨水”问题（Trapping Rain Water），并在下面给出你的代码实现和简要的思路说明。

\small{\url{https://leetcode.com/problems/trapping-rain-water/description/}}

\subsection*{解：}

\begin{minted}{python}
    def trap(height):
        # 在这里补充你的代码
\end{minted}


\section{}

请完成Leetcode上的“解码字符串”问题（Decode String），并在下面给出你的代码实现和简要的思路说明。

\small{\url{https://leetcode.com/problems/decode-string/description/}}

\subsection*{解：}

\begin{minted}{python}
    def decodeString(s):
        # 在这里补充你的代码
\end{minted}

\section{用两个栈实现一个队列。}

请描述如何只使用两个栈（以及基本的变量），来实现一个队列的 \mintinline{python}{enqueue} 和 \mintinline{python}{dequeue} 操作。并分析你所设计的 \mintinline{python}{enqueue} 和 \mintinline{python}{dequeue} 操作的摊还时间复杂度。

\subsection*{解：}

\section{用一个队列实现一个栈。}

请描述如何只使用一个队列（以及基本的变量），来实现一个栈的 \mintinline{python}{push} 和 \mintinline{python}{pop} 操作。并分析你所设计的 \mintinline{python}{push} 和 \mintinline{python}{pop} 操作的时间复杂度。

\subsection*{解：}

\section{用两个栈实现一个队列。}

请描述如何只使用两个栈（以及基本的变量），来实现一个队列的 \mintinline{python}{enqueue} 和 \mintinline{python}{dequeue} 操作。并分析你所设计的 \mintinline{python}{enqueue} 和 \mintinline{python}{dequeue} 操作的摊还时间复杂度。

\subsection*{解：}

\section{实现带尾指针的链表队列}

请参考本章 \mintinline{python}{LinkedQueue} 的实现，为其添加一个 \mintinline{python}{rotate(k)} 方法。该方法能将队首的 \mintinline{python}{k} 个元素，依次移动到队尾，且整个操作的时间复杂度应尽可能高效。例如，一个队列 \mintinline{python}{[A, B, C, D, E]}，执行 \mintinline{python}{rotate(2)} 后，应变为 \mintinline{python}{[C, D, E, A, B]}。

\subsection*{解：}

\begin{minted}{python}
    class LinkedQueue:
        # 在这里补充你的代码
        def rotate(self, k):
            # 在这里补充你的代码
\end{minted}

\section{用栈检查括号匹配}

编写一个函数 \mintinline{python}{is_valid_parentheses(s)}，接收一个只包含 \mintinline{python}{'(', ')', '{', '}', '[', ']'} 的字符串 \mintinline{python}{s}，判断该字符串中的括号是否有效匹配。
\begin{itemize}
    \item 有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
    \item 示例：\mintinline{python}{"()[]{}"} 是有效的，\mintinline{python}{"(]"} 和 \mintinline{python}{"([)]"} 是无效的。
\end{itemize}

\subsection*{解：}

\begin{minted}{python}
    def is_valid_parentheses(s):
        # 在这里补充你的代码
\end{minted}


\section{实现循环队列（\mintinline{python}{size}计数版）}

请参考本章关于循环队列的讨论，编程实现一个 \mintinline{python}{SizedCircularQueue} 类。该类使用一个固定大小的数组和一个 \mintinline{python}{size} 计数器来管理队列，其容量应被完全利用（即可存储 \mintinline{python}{capacity} 个元素）。请完整实现 \mintinline{python}{enqueue}, \mintinline{python}{dequeue}, \mintinline{python}{is_empty}, \mintinline{python}{is_full} 等核心方法。

\subsection*{解：}

\begin{minted}{python}
    class SizedCircularQueue:
        # 在这里补充你的代码
\end{minted}


\section{ (挑战题)用队列实现“烫手山芋”问题}
有 $n$ 个人围成一圈，从第 1 个人开始按顺时针方向报数，报到第 $m$ 个人时，该人出局；然后从出局的下一个人开始，重新从 1 开始报数，报到第 $m$ 个人时，该人再次出局……如此循环，直到剩下最后一个人。请编写一个函数 \mintinline{python}{find_survivor(n, m)}，返回最后剩下那个人的原始编号。请使用队列来模拟这个过程。

\subsection*{解：}

\begin{minted}{python}
    def find_survivor(n, m):
        # 在这里补充你的代码
\end{minted}