云海翻腾 - 个人主页动态

2021-10-16 14:38

用二分法分别找k-0.5和k+0.5应该插入的位置，位置距离即k的个数  class Solution { public: int bSearch(const vector<int> &vec, double k) { int beg = 0; int end = vec.size() - 1; while (beg <= end) { int mid = (beg + end); if (k < vec[mid]) { end = mid - 1; } else { beg = mid + 1; } } return beg; } int GetNumberO...

0 点赞评论收藏

2021-10-16 12:05

西北工业大学算法工程师

题解 | #机器人的运动范围#

从[0,0]开始向右或向下进行探索，直到不满足threshold就停止。 停止理由是如果当前坐标都不满足threshold，那么右下方就不可能有满足的坐标。 class Solution { public: char ** newMaxtrix(int rows, int cols) { char **pp = new char *[rows]; for (int i = 0; i < rows; ++i) { pp[i] = new char[cols]; memset(pp[i], 0, cols); } return pp; } int sumDigit(int num) { in...

0 点赞评论收藏

2021-11-04 11:43

已编辑

西北工业大学算法工程师

题解 | #矩形覆盖#

f(n)表示2*n（横为n，竖为2）时的结果。 当最后一列选择竖放时，即为f(n - 1) 当最后一列选择横放时，即为f(n - 2) 所以f(n) = f(n - 1) + f(n - 2)，类斐波那契数列，递归式如下： f(n)={f(n−1)+f(n−2),n>21,n=12,n=2f(n)=\left\{\begin{matrix} f(n-1) + f(n-2), & n > 2\\ 1, & n=1\\ 2, & n=2 \end{matrix}\right.f(n)=⎩⎨⎧f(n−1)+f(n−2),1,2,n>2n=1n=2  与...

0 点赞评论收藏

2021-10-16 09:17

已编辑

西北工业大学算法工程师

题解 | #二叉搜索树的后序遍历序列#

BST的特点是对任意结点，左子树小于该结点，右子树大于该结点。  后序遍历产生的序列为左子树-右子树-结点。  所以可知后序遍历序列的最后一个元素即为BST的根，再根据大小规律，可以找到左右子树对应的序列。递归处理这两个序列即可。  找左右子树序列时可采用二分查找法，虽然左右子树序列不是完全有序。  class Solution { public: int bSearch(const vector<int> &vec, int beg, int end, int k) { while (beg <= end) { int mid = (beg + end) / 2; ...

0 点赞评论收藏

2021-10-13 18:53

西北工业大学算法工程师

题解 | #扑克牌顺子#

首先对数字进行排序，排序过程中同时判断除0外是否有重复的数字，有重复则不能组成顺子。 对排好序的非0序列arr[start:end]进行计算，看要组成顺子还差几张牌，差的牌数小于等于0的个数，则能组成，否则不能组成 如2,4,7序列，则还差(4-2+1) + (7-4+1)=3张，这时只有两个0是不够的。 排序的方法可以随意。这里给出两种。 class Solution { public: /*bool sort(vector<int> &numbers, int &notZeroStart) { for (int i = 0; i < numbers.siz...

0 点赞评论收藏

2021-10-13 11:10

已编辑

西北工业大学算法工程师

题解 | #二叉搜索树与双向链表#

递归分析： 递归左子树，递归返回时左子树自然成双向链表，如图，4的左子树将变成1-2-3，当然4的左孩子还是2， 这时只要顺着2向链表的右边找到最后一个结点3将是4在链表中的直接前驱。 右子树操作与左子树对称  class Solution { public: TreeNode *searchDlistLast(TreeNode *p) { if (!p) { return NULL; } while (p->right) { p = p->right; } return p; } TreeNode *searchDlistFirst(TreeNode *p) { if (!p) ...

0 点赞评论收藏

2021-10-13 09:41

西北工业大学算法工程师

题解 | #数组中出现次数超过一半的数字#

分析 一个数字出现的次数超过数组长度的一半<=>这个数字出现的次数可以抵消所有其它数字出现的次数 首先对elem=a[0]进行计数cnt=1, 当后面a[i]为elem时，就cnt++，否则cnt--，当cnt减为0时，从elem=a[i]重复前面的动作。 这样最终所求数字只可能是elem或者不存在。 class Solution { public: int MoreThanHalfNum_Solution(vector<int> vec) { if (vec.empty()) { return 0; } int cnt = 1; int elem = vec[0]; ...

0 点赞评论收藏

2021-10-12 19:53

西北工业大学算法工程师

题解 | #丑数#

一、维护两个序列，分别叫uglys和factors uglys表示生成的丑数序列，每时刻该序列都是正确的，无需调整，初始化值只有1 factors与uglys对应，每个元素表示对应丑数当前应该乘的因子（只可能是2、3、5和-1），初始值2 二、丑数生成过程，循环执行下面的步骤  从factors中找到非-1的因子乘以对应的uglys元素，得到乘积序列A， 在A中找到一个最小值min，如果不等于uglys最后一个元素,则添加到uglys的最后，起名lastUgly，更新lastUgly对应的factors元素为2 将min对应的factors元素更新为下一值。2的下一值为3，3的下一值为5，5的...

0 点赞评论收藏

2021-10-12 19:40

西北工业大学算法工程师

题解 | #最小的K个数#

方法一 基于堆排序 构建小顶堆arr[0:n-1]后，重复k次： 将堆顶交换到堆末，即swap(arr[0], arr[n-1])，调整arr[0:n-2]，使其为小顶堆。 arr[n-1:n-k]即为所求 方法二 基于快排 对于arr[beg:end]每次递归调整后，基准元素arr[j]不小于前面的元素，不大于后面的元素 如果j >= k, 说明j后面的元素不可能是前k个最小元素，无需对j后的元素arr[j+1:end]进行递归排序，只需要对j前的元素arr[beg:j-1]进行递归排序。这是与快排的唯一区别，用于提高效率。 如果j < k, 说明j前的元素包含在前k个最小元素，...

0 点赞评论收藏

2021-10-11 19:18

西北工业大学算法工程师

题解 | #矩阵的最小路径和#

这是一个典型的动态规划问题。 从最左上结点a[0][0]到当前结点a[i][j]的最短路径dp[i][j]只取决于dp[i - 1][j], dp[i][j - 1]和a[i][j]。 当然要特殊考虑一下i或j为0的情况。 递推式为：dp[i][j] =  min(dp[i - 1][j], dp[i][j - 1]) + a[i][j], i > 0 且 j > 0 dp[i - 1][j] + a[i][j], j = 0 dp[i][j - 1] + a[i][j], i = 0  class Solution { public: vector<vector<in...

0 点赞评论收藏

2021-10-11 19:02

西北工业大学算法工程师

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

方法一 通过深度优先遍历，分别找出从根到两个结点的路径， 如1-2-3和1-2-5，那么路径的相同部分1-2的最后一个结点2即是最近祖先 方法二 递归考虑： 如果当前结点为空，返回空；否则看当前结点是否为两个结点中的一个，只要是，那么当前结点一定是最近祖先，否则，递归左树：  左树中没找到，递归右树，答案一定在右树。 左树中找到了，递归右树，右树中没找到，返回左树找到的；右树中找到了，返回当前结点  说明：方法一更直观，实现也很简单，效率略低，代码略长；方法二要站在宏观角度考虑，很精简。 程序按方法二实现 class Solution { public: TreeNode* dfsSearch...

0 点赞评论收藏

2021-10-11 18:56

西北工业大学算法工程师

题解 | #接雨水问题#

方法一 从左向右遍历，一般的，对第i个柱子，向右找j柱，使得以i柱为左边界，以j柱为右边界形成“凹水槽”。分两种情况   j柱是第一个大于或等于i柱的柱子，这时顺便计算“凹水槽”盛水量, i = j   找不到大于或等于i柱的柱子，这时的j柱为i柱右边最大的柱子，也可以顺便计算“凹水槽”盛水量（至于怎么计算，请读者自己琢磨），i = j 算法缺点：对于第2种情况，要高效的处理是比较困难的，方法可能还是存在的，但是空间代价一定不小。   方法二 对方法一改进，从两边遍历。从左向右遍历时如果遇到第二种情况，就后停下来。从右向左遍历与从左向右遍历对称。 这种算法克服了第一种情况的困难或性能差。 程序...

0 点赞评论收藏

2021-10-10 23:37

已编辑

西北工业大学算法工程师

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

采用归并排序的套路，递归将lists一直从中间拆分，直到不能再拆，在递归函数返回时，将拆分的两段list1[a:b]和list2[c:d]进行合并，合并结果保存在list1[a]中，这样，最终合并的结果在lists[0]中。 class Solution { public: ListNode * merge2lists(ListNode *list1, ListNode *list2) { ListNode node(0); ListNode *p = &node; while (list1 && list2) { if (list1->val <= lis...

0 点赞评论收藏

2021-10-10 23:18

西北工业大学算法工程师

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

设计LRU缓存结构分析 三个核心数据结构设计或选择  缓存cache明显属于key-value的数据结构，要让访问性能高，可以考虑hash表，所以可以选择c++中的unordered_map（当然unordered_map实现比较复杂，在规模大时才是hash，这里不必细纠）。 可以维护一个按照最近使用时间排序的链表list，元素为记录key，当set操作超cache大小k，需要删除cache中的记录时，直接找到list的头结点（要删除记录的key）来操作。 在进行get或set操作时，将操作的key重新排在list的末尾。要追求性，这就要求要很快找到list中key所在位置，一般list明显没...

0 点赞评论收藏

2022-07-17 14:50

已编辑

西北工业大学算法工程师

题解 | #汉诺塔问题#

汉诺塔问题采用递归法分析 问题抽象 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, b, a, c) f(1, a, b, c) = "mov number 1 to c" 说明：这里的等号与加号为抽象表示，加号不具有交换律，加号表示先完成左边，再完成右边如果需要计算移动次数的话，f(n - 1, a, c, b)与f(n - 1, b, a, c)是相等的...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：