云海翻腾

分类

C++(5) 程序/算法设计(2) 题解(29)

/ 注册

全部文章（共36篇）

题解 | #在二叉树中找到两个节点的最近公共祖先#

方法一通过深度优先遍历，分别找出从根到两个结点的路径，如1-2-3和1-2-5，那么路径的相同部分1-2的最后一个结点2即是最近祖先方法二递归考虑：如果当前结点为空，返回空；否则看当前结点是否为两个结点中的一个，只要是，那么当前结点一定是最近祖先，否则，递归左树：左树中没找到，递归右树...

C++ 二叉树递归深度优先搜索

2021-10-11

0 362

题解 | #接雨水问题#

方法一从左向右遍历，一般的，对第i个柱子，向右找j柱，使得以i柱为左边界，以j柱为右边界形成“凹水槽”。分两种情况 j柱是第一个大于或等于i柱的柱子，这时顺便计算“凹水槽”盛水量, i = j 找不到大于或等于i柱的柱子，这时的j柱为i柱右边最大的柱子，也可以顺便计算“凹水槽”盛水量（至于...

C++ 双指针

2021-10-11

0 392

题解 | #合并k个已排序的链表#

采用归并排序的套路，递归将lists一直从中间拆分，直到不能再拆，在递归函数返回时，将拆分的两段list1[a:b]和list2[c:d]进行合并，合并结果保存在list1[a]中，这样，最终合并的结果在lists[0]中。 class Solution { public: ListNode...

C++ 分治归并排序

2021-10-10

0 454

题解 | #设计LRU缓存结构#

设计LRU缓存结构分析三个核心数据结构设计或选择缓存cache明显属于key-value的数据结构，要让访问性能高，可以考虑hash表，所以可以选择c++中的unordered_map（当然unordered_map实现比较复杂，在规模大时才是hash，这里不必细纠）。可以维护一个按照最近使...

C++ 链表双向链表哈希表

2021-10-10

0 408

题解 | #汉诺塔问题#

汉诺塔问题采用递归法分析问题抽象 f(n, a, b, c)表示将n个盘子(从上到下分别记作1,2,3...n)从a柱借助b柱移动到c柱递归公式 f(n, a, b, c) = f(n - 1, a, c, b) + "mov number n to c" + f(n - 1...

C++ 递归

2021-10-09

0 346

题解 | #重排链表#

方法一求出链表的长len，将链表从中间分成两个链表list1和list2。其中list1为前半段，长度为(len + 1) / 2 将list2逆置。可以采用头插法，即遍历list2，将每个节点从头部插入到初始为空的链表newList中。将list1与newList合并。这步就很简单了方法...

C++ 链表

2021-10-09

0 366