我要出去乱说

分类

C++(2) 程序员代码面试指南(20) 题解(2)

/ 注册

TA的专栏 50篇文章 3人订阅

程序员代码面试指南（C++版题解）

41篇文章 592人学习

我的面经汇总

9篇文章 21587人学习

全部文章（共42篇）

程序员代码面试指南 2.4：反转单链表与双链表来自专栏

1、思路模板题，记下来就好。 2、代码 //反转单链表 list_node * reverse_list(list_node * head) { if (head == nullptr || head->next == nullptr) return head; list_...

C++

2022-04-11

1 335

程序员代码面试指南 2.3：删除链表的中间节点来自专栏

1、思路删除第K个节点，往前走K - 1步再跳过下一节点即可；要注意删除第一个节点的情况，所以声明了一个虚拟头结点。 2、代码 list_node * remove_kth_node(list_node * head, int K) { if (head == nullptr |...

C++

2022-04-11

1 364

程序员代码面试指南 1.9：求最大子矩阵的大小（单调栈）来自专栏

1、思路用一个height数组来统计以当前行作为底的情况下，每个位置往上的1的数量；使用单调栈的方法遍历height数组进栈，栈中存放height数组元素的下标，目的是寻找数组中每个元素向左右两边最大能扩展的距离（即找到左右两边第一个比它小的数）；利用单调栈计算矩阵每一行所代表的height...

C++

2022-04-05

1 361

程序员代码面试指南 1.8：单调栈结构来自专栏

1、思路维护一个单调栈来寻找数组中每个元素左右两个方向上离它最近且比它小的元素；遍历数组，让数组元素的下标进栈，栈中元素所代表的的值从下往上是单调递增的；若当前元素小于栈顶元素，说明找到了栈顶元素右边第一个小于它且离它最近的数，且该栈顶元素左边第一个小于它且离它最近的数就是栈顶的后一个元素；...

C++

2022-04-03

1 428

程序员代码面试指南 1.7：生成窗口最大值数组来自专栏

1、思路初见这个题可能会想到用两个指针来代表窗口的前后边界，但这样实现代码会非常复杂。最好的方式应该是用一个双端队列deque来构造单调栈，队列中存放的是元素下标，队头为窗口内最大元素的下标，当队头元素（下标）已经超出窗口范围时，我们把这个元素叫作过期元素，需要弹出。主要的四个步骤如下：队列不...

C++

2022-04-02

1 297

程序员代码面试指南 1.5：用一个栈实现另一个栈的排序来自专栏

1、思路使用一个辅助栈help来对原栈stk进行排序，在stk上执行pop操作，弹出的元素记为cur：若cur ≤ help.top()，则cur压入help栈中；若cur > hel.top()，则将help中元素逐一弹出并压入stk中，直到cur ≤ help.top()为止，...

C++

2022-04-01

1 359

程序员代码面试指南 1.3：用递归函数和栈逆序一个栈来自专栏

1、思路递归地每次取得栈底元素，当达到最后一层递归时取得的就是栈顶元素了，再利用递归返回，将栈顶元素push入栈底即可。 2、实现需要构造两个递归函数来实现栈的逆序： getAndRemoveLastElement()方法能够递归把栈弹出，取得并移除栈底元素后，再恢复栈； reverse(...

C++

2022-04-01

1 308

程序员代码面试指南 1.2：由两个栈组成的队列来自专栏

解法一两个栈倒来倒去的常规解法。 #include <iostream> #include <string> #include <stack> using namespace std; stack<int> stk1, stk2; //将一...

C++

2022-03-31

1 311

程序员代码面试指南1.1：设计getMin功能的栈来自专栏

思路用两个栈来实现，其中一个作为最小栈，操作思路： push时，只有最小栈为空或者当前元素 ≤ 最小栈顶元素时，才push到最小栈中； pop时，只有栈顶元素等于最小栈顶元素时，才将最小栈顶元素弹出。由于数据保证没有不合法的操作，这里就不做判空异常了。 #include <iost...

C++

2022-03-31

1 342

题解 | #最长回文子串#

中心扩展法。 typedef pair<int, int> PII; #define x first #define y second class Solution { public: PII expand(const string& A, int left, int ...

2021-07-02

1 427