- 博客(204)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 多路归并问题
264. 丑数 II 313. 超级丑数 373. 查找和最小的K对数字 632. 最小区间 719. 找出第 k 小的距离对 786. 第 K 个最小的素数分数 1439. 有序矩阵中的第 k 个最小数组和 1508. 子数组和排序后的区间和 1675. 数组的最小偏移量
2023-05-28 08:37:41
72
原创 组合数计算
华为笔试题里出现了组合数计算的问题，在此记录一下解法：求的核心公式是这个公式可以从直观上很好地理解：从n个物品里选k个的方法数，等于 选第n个物品，在前n-1个物品里选k-1个的方法数 + 不选第n个物品，在前n-1个物品里选k个的方法数。也可以从杨辉三角中推出。那么求组合数的问题就变成了动态规划问题：这样计算可以有效避免求组合数时乘法溢出。如果只需要求固定n的，那么可以进一步优化空间到一维：，注意 j 要从右向左更新。 int cnk[MAXN] = {0}; .
2020-08-30 20:41:33
441
原创 OPPO C++软件开发笔试题 2020.8.29
三道编程题都是竞赛题，难度很大。1.第k大斜率https://www.luogu.com.cn/problem/P4479在平面直角坐标系上，有 n 个不同的点。任意两个不同的点确定了一条直线。请求出所有斜率存在的直线按斜率从大到小排序后，第 k 条直线的斜率为多少。为了避免精度误差，请输出斜率向下取整后的结果。输入格式：第一行，包含两个正整数 n 和 k 。接下来 n 行，每行包含两个整数 xi,yi，表示每个点的横纵坐标。输出格式：输出一行，包含一个整...
2020-08-30 15:09:12
1791
原创 大疆嵌入式软件笔试题2020.8.16
嵌入式软件岗，两道编程题都是动态规划。第一题：求出数组中两个不重叠的子数组的最大和。POJ 2479Maximum sumhttp://poj.org/problem?id=2479考试的时候没想出来。#include <vector>#include <cstdio>using namespace std;int helper(const vector<int>& v){ int n = v.size(); vect.
2020-08-17 14:51:55
2842
2
原创 单调队列
单调队列往往用来解决滑动窗口最值问题。目录1.239. 滑动窗口最大值2.剑指 Offer 59 - II. 队列的最大值3.862. 和至少为 K 的最短子数组1.239. 滑动窗口最大值给定一个数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出:...
2020-08-13 13:48:14
232
原创 子矩阵求和问题
两道类似的子矩阵求和问题，都是化二维为一维去做，一维子数组求和问题有：和为K的子数组个数、最大子数组和，二维子矩阵求可以使用同样的方法。1074. 元素和为目标值的子矩阵数量class Solution {public: int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) { int row[300] = {0}; unordered_map&
2020-08-12 11:17:43
910
原创 牛客上需要复习的华为机试题
1. 放苹果https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebftpId=37&&tqId=21284&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking题目描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1是同一种分法。输入每个用例包含二个整数.
2020-08-01 16:41:31
581
转载 linux 内核poll/select/epoll实现剖析
转载自https://www.iteye.com/blog/watter1985-1614039f_ops.poll和wait_queuepoll/select/epoll的实现都是基于文件提供的poll方法(f_op->poll)，该方法利用poll_table提供的_qproc方法向文件内部事件掩码_key对应的的一个或多个等待队列(wait_queue_head_t)上添加包含唤醒函数(wait_queue_t.func)的节点(wait_queue_t)，并检查文件当前就绪的状态返回
2020-07-22 19:48:04
238
原创 计算几何两题
判断直线是否相交和判断线段是否相交似乎是高频面试题，总结一下这两道题目的解法。首先，二维向量内积 v1 · v2 = x1 * x2 + y1 * y2。二维向量外积 v1×v2 = x1*y2 - x2*y1。1. 直线是否平行或垂直http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_AParallel/OrthogonalFor given two liness1ands2, print "2" i...
2020-07-19 16:39:04
267
原创 C++17 string_view 加速子串问题
C++17引入了 string_view 类，适用于需要生成子串的问题，避免了字符串复制操作，但不允许修改子串，相当于提供一个子串的视图。基本用法如下：string str = "hello world";string_view sv(str);string_view sub = sv.substr(0, 2);unordered_map<string_view, int> mp;除了构造时需要使用string类对象外，取子串的方式和string基本相同，注意使用string_
2020-07-09 13:46:02
493
原创 旋转排序数组
Leetcode上有四道旋转排序数组的题目，都是使用二分法。使用二分法的关键点是想到这样一个事实：每次二分，左半边和右半边肯定有一边是能确定有序的。那么，无论是找最小值，还是搜索某个数，先在确定有序的那边找，没找到的话再对不确定有序的那边继续二分。首先要确定，nums[mid] 究竟和 nums[left] 以及 nums[right] 中的哪一个比较，可以把目标值套在一个可确定的区间里。1. 找最小值问题如果是找最小值，那么应当使得每次收缩区间，最小值仍然在区间内。 nums[mid] num
2020-06-21 10:40:08
1533
原创 摩尔投票法
摩尔投票法可以用来寻找数组中的多数元素。经典的摩尔投票法用来寻找数组中出现次数超过一半的元素。如leetcode 169:1.169. 多数元素给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例1:输入: [3,2,3]输出: 3示例2:输入: [2,2,1,1,1,2,2]输出: 2一个数组中出现次数大于n/2的元素最多只有1个。考虑这样一...
2020-06-17 21:19:53
1516
原创 几道技巧性的数组题
1.面试题03. 数组中重复的数字找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例 1：输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3限制：2 <= n <= 100000因为一共有n个数，每个数都在 0~n-1之间，那么可以考虑把每个数放到对应的位置上。即：nums[i]..
2020-06-17 10:51:19
283
原创 几道递归生成所有可能的树的问题
1.894. 所有可能的满二叉树满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。答案中每个树的每个结点都必须有 node.val=0。你可以按任何顺序返回树的最终列表。输入：7输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,nu
2020-06-11 08:12:44
217
原创 博弈问题
记录leetcode中的博弈DP问题1.292. Nim 游戏你和你的朋友，两个人一起玩Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。示例:输入: 4输出: false解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛； 因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友...
2020-06-10 12:17:26
623
原创 划分K个等和子集
698. 划分为k个相等的子集正确解法：class Solution {private: int n; int target; bool dfs(int k, int tmpsum, int used, vector<int>& nums) { if(k == 1) return true; for (int i = 0; i < n; ++i) { if(used
2020-06-07 10:12:52
436
原创 两道使用后序遍历的二叉搜索树问题
1373. 二叉搜索子树的最大键值和(https://www.nowcoder.com/questionTerminal/380d49d7f99242709ab4b91c36bf2acc)#include <map>#include <unordered_map>#include <cstdio>#include <vector>using namespace std; struct TreeNode{ int val; .
2020-06-05 15:17:05
149
1
原创 前缀和
记录下leetcode里关于前缀和的题目。前缀和的概念很简单， sum[i+1] = sum(a[0]...a[i])， 计算 a[i]...a[j]的和就是 sum[j+1] - sum[i]。但是暴力枚举符合条件的(i, j)对往往超时，需要结合hash表记录。1.和为k的子数组https://leetcode-cn.com/problems/subarray-sum-equals-k/给定一个整数数组和一个整数k，你需要找到该数组中和为k的连续的子数组的个数。示例 1 :输...
2020-05-27 16:16:47
233
原创 区间DP
1. 合并石子https://www.nowcoder.com/questionTerminal/6d3ccbc5b6ad4f12b8fe4c97eaf969e0有 N 堆金币排成一排，第 i 堆中有 C[i] 块金币。每次合并都会将相邻的两堆金币合并为一堆，成本为这两堆金币块数之和。经过N-1次合并，最终将所有金币合并为一堆。请找出将金币合并为一堆的最低成本。其中，1 <= N <= 30，1 <= C[i] <= 100输入描述:第一行输入一个数字 N..
2020-05-26 06:45:00
324
原创 双序列DP
1. 两个子序列的最大点积https://leetcode-cn.com/problems/max-dot-product-of-two-subsequences/给你两个数组nums1和nums2。请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5]是[1,2,3,4,5]的一个子序列而[1,5,3]不是。...
2020-05-25 23:15:14
519
原创 华为笔试题
一、全量字符集与已占用字符集输入描述：输入一个字符串，字符串中包含了全量字符集和已占用字符集，两个字符集用@相连。@前的字符集合为全量字符集，@后的字符集为已占用字符集合。已占用字符集中的字符一定是全量字符集中的字符。字符集中的字符跟字符之间使用英文逗号分隔。字符集中的字符表示为字符加数字，字符跟数字使用英文冒号分隔，比如a:1，表示1个a字符。字符只考虑英文字母，区分大小写，数字只考虑正整形，数量不超过100，如果一个字符都没被占用，@标识符仍在，例如a:3,b:5,c:2@输出描述：可用.
2020-05-24 21:36:41
517
原创 OJ平台循环读取输入的方式
链接：https://ac.nowcoder.com/acm/contest/320/G题目描述计算一系列数的和输入描述:输入数据有多组, 每行表示一组输入数据。每行不定有n个整数，空格隔开。(1 <= n <= 100)。输出描述:每组数据输出求和的结果示例1输入1 2 34 50 0 0 0 0输出690这算是循环读输入里面比较麻烦的题目了。如果一行只有两个数，那么可以用while(cin >> a >..
2020-05-24 17:19:08
1615
原创 华为笔试题街区监控
街区监控题目描述一个街区，为提高街区安全性，需在街区的路灯上安装若干摄像头，用一个二叉树表示街区的路灯，每个节点表示一个路灯，在路灯上安装摄像头。每个摄影头都可以监视其父对象、自身及其直接子对象。为保证每个路灯都被监控，请计算街区所需的最小摄像头数量。输入描述:输入一串字符，代表由前序排列的二叉树表示的路灯，字符由‘0’和‘#’组成，每个‘0’表示一个要监控路灯，‘#’表示子节点为空。输出描述:所需最小摄像头数量。示例1输入输出示例仅供调试，后台判题数据一般不包含示例输入00##0#0.
2020-05-24 10:29:05
835
原创 有向图环路
华为的笔试题里出现了找出有向图环路的问题（最多只有一个环），这里记录一下解法：使用两个数组 visited 和 onpath，visited数组记录当前节点是否被访问过，onpath数组某个节点是否在搜索路径上。再使用一个栈，记录当前的搜索路径。对于节点k，如果它没被访问过，那么对它的所有邻接点dfs，并标记 visited[k] = true, onpath[k] = true, stack.push(k)；如果它被访问过，那么如果它也在搜索路径上（在栈里），那么栈中从k到栈顶的所有节点，组成了一个环
2020-05-23 23:19:09
2072
原创 单调栈
这篇博客记录Leetcode刷题中遇到的单调栈问题，对于单调栈，要想明白是递增还是递减，栈顶元素代表什么，当遍历到比栈顶元素大或小的元素时，要怎么操作？(A）求下一个最大元素(NGE: Next Greater Element)：A.1496. 下一个更大元素 I给定两个 没有重复元素 的数组nums1 和nums2，其中nums1是nums2的子集。找到nums1中每个元素在nums2中的下一个比其大的值。nums1中数字x的下一个更大元素是指x在num...
2020-05-20 23:42:33
244
原创 背包问题
这篇博客记录在leetcode刷题中遇到的一些背包问题。(1)完全背包问题(A)https://leetcode-cn.com/problems/coin-change-2/ 518. 零钱兑换 II给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。示例 1:输入: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+15=2+1+1+15=1+1+...
2020-05-11 13:04:18
241
原创 leetcode中归并排序的应用
（A)逆序对个数：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。思路：这一题是典型的归并排序的应用。归并过程中，[left, mid] 和 [mid + 1， right]分别有序。之后将 nums[i] 和 nums[j]逐个比较。①考虑右半部分的每个元素对应逆序对的数量，即出现 nums[
2020-05-08 18:41:21
633
原创 C++正则表达式简单用法
最近学习了一下C++11引入的正则表达式用法，对于处理字符串问题带来很大方便。下面基于几个简单应用介绍一下用法：(1) 判断字符串是否匹配某一模式，例如，判断输入字符串是否符合“5-15位数字，并且首位不能是0”这一模式。#include <bits/stdc++.h>using namespace std;int main(){ string str; ...
2020-05-01 18:44:04
1357
转载 Ubuntu突然无法上网解决
https://blog.csdn.net/qq_33680024/article/details/83239890
2019-10-01 11:21:04
109
转载 Ubuntu /boot 占满解决方案
https://blog.csdn.net/weixin_37272286/article/details/79897636
2019-09-30 22:31:09
153
原创 动态规划问题记录
Ⅰ：凑零钱问题：①给出不重复的数组 coins 表示硬币的面额，数字 amount 表示需要凑成的金额。如果每种金额的硬币只能用一次，输出所有不重复的可能的组合的总数。递归：class Solution {private: int helper(vector<int>& coins, int index, int amount) { ...
2019-09-21 16:49:08
147
原创 递归 回溯 leetcode 问题记录
leetcode 17：17. 电话号码的字母组合给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。接口：class Solution {public: vector<string> letterCombinations(string digits) { ...
2019-09-15 16:53:18
159
原创 PAT A1155 Heap Paths (30 分) 堆
题目大意：给出一棵完全二叉树，判断它是否是最大堆或者最小堆。并输出从根节点到所有叶子节点的路径。要求位于左子树的比右子树的叶子节点先输出。 因为是完全二叉树，从下标为0开始计，根节点下标为0，下标为 i 的左子树下标为 2*i + 1，右子树下标为 2 * i +2。最后一个非叶子节点的下标是(N - 2) /2, N是节点数。输出某一个叶子节点的路径是容易实现的，不断向前递推...
2019-09-10 15:16:05
91
原创 PAT A1154 Vertex Coloring (25 分) 图
题目大意：给出一张图的信息，要求每条边的两个端点颜色不同。给出K种上色序列，判断是否符合条件。 用邻接表实现，遍历顶点 i 的所有邻接顶点，如果有和 i 的颜色相同的，就不符合条件。颜色的种类数可以用set存储。AC代码：#include <vector>#include <cstdio>#include <set>using ...
2019-09-10 15:15:51
130
原创 PAT A1153 Decode Registration Card of PAT (25 分) 排序 map
题目大意：给出N名考生的准考证号和成绩，要求按三种方式进行查询：① 根据等级查询，查询所有等级为 T/A/B的考生。② 根据考场查询，输出查询考场的总人数和总成绩。③ 根据考试日期查询，输出在查询日期那一天 有考生参加考试的考场的序号，以及该考场在那一天的总人数和总成绩。 还是阅读理解题。查询①容易做到，将对应等级的考生存放在 map<string, vector<s...
2019-09-10 15:15:46
95
原创 PAT A1152 Google Recruitment (20 分) 素数
题目大意：给出长为L的字符串，找到第一个出现的长度为K的素数，这里的长度包括前面的0。 依次遍历判断是否是素数即可。 i = L - K是最后一个长度为K的字符串的起点。AC代码：#include <iostream>#include <cmath>using namespace std;bool isPrime(int num){ ...
2019-09-10 15:15:42
169
1
原创 PAT A1151 LCA in a Binary Tree (30 分) 二叉树
题目大意：给出二叉树的先序和中序遍历，输出节点U和V的最低公共祖先。 可以直接用PAT A1143 Lowest Common Ancestor的第一种方法做，先建树，再从根节点出发dfs找到到达节点U和V的两条路径，之后找到两条路径的分叉点，就是最低公共祖先。AC代码：#include <iostream>#include <vector>...
2019-09-09 13:48:05
82
原创 PAT A1150 Travelling Salesman Problem (25 分) 图
题目大意：给出图的信息，判断给定的顶点序列是否是 TS cycle, TS simple cycle。所谓 TS cycle，是指从一个顶点出发，最后回到这个顶点，并且图中的每个顶点都被经过。所谓 TS simple cycle，是指在TS cycle的基础上，除了起点经过两次，中间每个顶点都只经过一次。并计算所有给出序列中，满足TS cycle条件的路径的最小长度。如果给定的序列不是一条...
2019-09-09 13:48:01
96
原创 PAT A1149 Dangerous Goods Packaging (25 分) 模拟
题目大意：给出N对不能相容的物品id，之后给出M个序列，判断这些序列中是否存在不相容的物品。 想出来两种思路，测试了下第二种思路整体上快一些：① 因为id是五位数，用set<int> incompatiable[MAXN]来存储每个货物的不相容id，之后对读入的序列，用二重循环遍历(i , j)，判断 j是否在 i 的不相容列表里，如果是则存在不相容物品。这种方法...
2019-09-09 13:47:57
88
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人