专栏虽已结束,但学习不应停止。我看到很多同学依然还在这里学习,一部分同学积极地在留言区和大家分享学习总结和练习题答案。
我几乎在每个课时的结尾都留下了一道练习题,目的是帮助你检测和巩固本课时的重点内容,抑或是引出后续课时中的内容。在我处理留言的过程中,发现很多同学想要练习题详细解答过程以及答案,所以就有了今天的这一篇加餐内容,希望对你有所帮助。
接下来我会给出每个课时练习题的解题思路和答案,如果你没有找到对应的练习题答案,那么请你在正课中查找。
【问题】 评估一下,如下的代码片段,时间复杂度是多少?
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) {
}
for (m = 0; m < n; m++) {
}
}
}
【解析】 在上面的代码中:
【问题】 在下面这段代码中,如果要降低代码的执行时间,第 4 行代码需要做哪些改动呢?如果做出改动后,是否降低了时间复杂度呢?
public void s2_2() {
int count = 0;
for (int i = 0; i <= (100 / 7); i++) {
for (int j = 0; j <= (100 / 3); j++) {
if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) {
count += 1;
}
}
}
System.out.println(count);
}
【解析】 代码的第 4 行可以改为:
for (int j = 0; j <= (100-7*i) / 3; j++) {
代码改造完成后,时间复杂度并没有变小。但由于减少了一些不必要的计算量,程序的执行时间变少了。
【问题】 对于一个包含 5 个元素的数组,如果要把这个数组元素的顺序翻转过来。你可以试着分析该过程需要对数据进行哪些操作?
【解析】 假设原数组 a = {1,2,3,4,5},现在要更改为 a = {5,4,3,2,1}。要想得到新的数组,就要找到 “1” 和 “5”,再分别把它们赋值给对方。因此,这里主要会产生大量的基于索引位置的查找动作。
【问题】 给定一个包含 n 个元素的链表,现在要求每 k 个节点一组进行翻转,打印翻转后的链表结果。例如,链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6,k = 3,则打印 321654。
【解析】 我们给出一些提示。利用链表翻转的算法,这个问题应该很简单。利用 3 个指针,prev、curr、next,执行链表翻转,每次得到了 k 个翻转的结点就执行打印。
【问题】 给定一个包含 n 个元素的链表,现在要求每 k 个节点一组进行翻转,打印翻转后的链表结果。例如,链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6,k = 3,则打印 321654。要求用栈来实现。
【解析】 我们用栈来实现它,就很简单了。你可以牢牢记住,只要涉及翻转动作的题目,都是使用栈来解决的强烈信号。
具体的操作如下,设置一个栈,不断将队列数据入栈,并且实时记录栈的大小。当栈的大小达到 k 的时候,全部出栈。我们给出核心代码:
while (tmp != null && count < k) {
stack.push(tmp.value);
tmp = tmp.next;
count++;
}
while (!stack.isEmpty()) {
System.out.print(stack.pop());
}
详细分析和答案,请翻阅 18 课时例题 1。
详细分析和解题步骤,请参考 17 课时例题 1。
详细分析和答案,请翻阅 15 课时例题 1。
详细分析和答案,请翻阅 16 课时例题 1。
【问题】 在一个有序数组中,查找出第一个大于 9 的数字,假设一定存在。例如,arr = { -1, 3, 3, 7, 10, 14, 14 };则返回 10。
【解析】 在这里提醒一下,带查找的目标数字具备这样的性质:
因此,当我们作出向左走或向右走的决策时,必须满足这两个条件。代码如下:
public static void main(String[] args) {
int targetNumb = 9;
// 目标有序数组
int[] arr = { -1, 3, 3, 7, 10, 14, 14 };
int middle = 0;
int low = 0;
int high = arr.length - 1;
while (low <= high) {
middle = (high + low) / 2;
if (arr[middle] > targetNumb && (middle == 0 || arr[middle - 1] <= targetNumb)) {
System.out.println("第一个比 " + targetNumb + " 大的数字是 " + arr[middle]);
break;
} else if (arr[middle] > targetNumb) {
// 说明该数在low~middle之间
high = middle - 1;
} else {
// 说明该数在middle~high之间
low = middle + 1;
}
}
}
详细分析和答案,请翻阅 16 课时例题 3。
【问题】 下面的代码采用了两个 for 循环去实现 two sums。那么,能否只使用一个 for 循环完成呢?
private static int[] twoSum(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { map.get(complement), i };
}
}
return null;
}
【解析】 原代码中,第 3 和第 6 行的 for 循环合并后,就需要把 map 的新增、查找合在一起执行。则代码如下:
private static int[] twoSum(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { map.get(complement), i };
}
else{
map.put(arr[i], i);
}
}
return null;
}
【问题】 如果现在是个线上实时交互的系统。客户端输入 x,服务端返回斐波那契数列中的第 x 位。那么,这个问题使用上面的解法是否可行。
【解析】 这里给你一个小提示,既然我这么问,答案显然是不可行的。如果不可行,原因是什么呢?我们又该如何解决?
注意,题目中给出的是一个实时系统。当用户提交了 x,如果在几秒内没有得到系统响应,用户就会卸载 App 啦。
一个实时系统,必须想方设法在 O(1) 时间复杂度内返回结果。因此,一个可行的方式是,在系统上线之前,把输入 x 在 1~100 的结果预先就计算完,并且保存在数组里。当收到 1~100 范围内输入时,O(1) 时间内就可以返回。如果不在这个范围,则需要计算。计算之后的结果返回给用户,并在数组中进行保存。以方便后续同样输入时,能在 O(1) 时间内可以返回。
【问题】 对于树的层次遍历,我们再拓展一下。如果要打印的不是层次,而是蛇形遍历,又该如何实现呢?蛇形遍历就是 s 形遍历,即奇数层从左到右,偶数层从右到左。
【解析】 这里要对数据的顺序进行逆序处理,直观上,你需要立马想到栈。毕竟只有栈是后进先出的结构,是能快速实现逆序的。具体而言,需要建立两个栈 s1 和 s2。进栈的顺序是,s1 先右后左,s2 先左后右。两个栈交替出栈的结果就是 s 形遍历,代码如下:
public ArrayList<ArrayList<Integer>> Print(TreeNodes pRoot) {
// 先右后左
Stack<TreeNodes> s1 = new Stack<TreeNodes>();
// 先左后右
Stack<TreeNodes> s2 = new Stack<TreeNodes>();
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
list.add(pRoot.val);
s1.push(pRoot);
while (s1.isEmpty() || s2.isEmpty()) {
if (s1.isEmpty() && s2.isEmpty()) {
break;
}
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
if (s1.peek().right != null) {
list.add(s1.peek().right.val);
s2.push(s1.peek().right);
}
if (s1.peek().left != null) {
list.add(s1.peek().left.val);
s2.push(s1.peek().left);
}
s1.pop();
}
} else {
while (!s2.isEmpty()) {
if (s2.peek().left != null) {
list.add(s2.peek().left.val);
s1.push(s2.peek().left);
}
if (s2.peek().right != null) {
list.add(s2.peek().right.val);
s1.push(s2.peek().right);
}
s2.pop();
}
}
}
return list;
}
【问题】 给定一个链表,删除链表的倒数第 n 个节点。例如,给定一个链表: 1 -> 2 -> 3 -> 4 -> 5, 和 n = 2。当删除了倒数第二个节点后,链表变为 1 -> 2 -> 3 -> 5。你可以假设,给定的 n 是有效的。额外要求就是,要在一趟扫描中实现,即时间复杂度是 O(n)。这里给你一个提示,可以采用快慢指针的方法。
【解析】 定义快慢指针,slow 和 fast 并同时指向 header。然后,让 fast 指针先走 n 步。接着,让二者保持同样的速度,一起往前走。最后,fast 指针先到达终点,并指向了 null。此时,slow 指针的结果就是倒数第 n 个结点。比较简单,我们就不给代码了。
【问题】 小明从小就喜欢数学,喜欢在笔记里记录很多表达式。他觉得现在的表达式写法很麻烦,为了提高运算符优先级,不得不添加很多括号。如果不小心漏了一个右括号的话,就差之毫厘,谬之千里了。因此他改用前缀表达式,例如把 (2 + 3) * 4
写成* + 2 3 4
,这样就能避免使用括号了。这样的表达式虽然书写简单,但计算却不够直观。请你写一个程序帮他计算这些前缀表达式。
【解析】 在这个题目中,输入就是前缀表达式,输出就是计算的结果。你可以假设除法为整除,即 “5/3 = 1”。例如,输入字符串为 + 2 3,输出 5;输入字符串为 * + 2 2 3,输出为 12;输入字符串为 * 2 + 2 3,输出为 10。
假设输入字符串为 * 2 + 2 3,即 2*(2+3)。第一个字符为运算符号 *,它将对两个数字进行乘法。如果后面紧接着的字符不全是数字字符,那就需要暂存下来,先计算后面的算式。一旦后面的计算完成,就需要接着从后往前去继续计算。因为从后往前是一种逆序动作,我们能够很自然地想到可以用栈的数据结构进行存储。代码如下:
public static void main(String[] args) {
Stack<Object> stack = new Stack<Object>();
String s = "* + 2 2 3";
String attr[] = s.split(" ");
for (int i = attr.length - 1; i >= 0; i--) {
if (!(attr[i].equals("+") || attr[i].equals("-") || attr[i].equals("*") || attr[i].equals("/"))) {
stack.push(Integer.parseInt(attr[i]));
} else {
int a = (int) stack.pop();// 出栈
int b = (int) stack.pop();// 出栈
int result = Cal(a, b, attr[i]); // 调用函数计算结果值
stack.push(result); // 结果进栈
}
}
int ans = (int) stack.pop();
System.out.print(ans);
}
public static int Cal(int a, int b, String s) {
switch (s) {
case "+":
return a + b;
case "-":
return a - b;
case "*":
return a * b;
case "/":
return a / b;
}
return 0;
}
以上这些练习题你做得怎么样呢?还能回忆起来每道题是源自哪个算法知识点或哪个课时吗?
你可以把课后习题和课程中的案例都当作一个小项目,自己动手实践,即使有些题目你还不能写出完整的代码,那也可以尝试写出解题思路,从看不明白到能够理解,再到能联想到用什么数据结构和算法去解决什么样的问题,这是一个循序渐进的过程,切勿着急。
通过留言可以看出,你们都在认真地学习这门课程,也正因如此,我才愿意付出更多的时间优化这个已经完结的专栏。所以,请你不要犹豫,尽管畅所欲言,在留言区留下你的思考,也欢迎你积极地提问,更欢迎你为专栏提出建议,这样我才能更直接地看到你们的想法和收获。也许你的一条留言,就是下一篇加餐的主题。