首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
岩之痕
获赞
57
粉丝
1
关注
1
看过 TA
0
男
New York University
2019
C++
IP属地:未知
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑岩之痕吗?
发布(5)
刷题
岩之痕
2019-08-25 22:35
已编辑
C++
K点游戏题解
题目 输入:N, K, W输出:从0点开始每次增加[1, W]的随机数,直到大于等于K点。问最终点数小于等于N的概率。 符号定义: A[start, end) = A[start] + A[start+1] + ... + A[end - 1]A[start, end] = A[start] + A[start+1] + ... + A[end] 一、用过去推现在 定义P[k]为不限抽取次数,获得k点的概率。则P[k] = (P[k-1] + P[k-2] + ... + P[k-W])/W 简写作P[k-W, k) / W只需快速求出P[k-W, k),就可计算P[k]。同时记得区间[k-W...
0
点赞
评论
收藏
转发
岩之痕
2019-08-23 17:03
已编辑
C++
单调栈题解
单调栈 O(N) 两次遍历 创建一个栈来存各个值的下标。从左往右扫描数组,在将A[i]加入栈之前,将所有大于等于A[i]的元素出栈,此时栈顶元素就是左侧第一个小于A[i]的数的下标,在记录答案之后将i入栈,继续向右扫描。在此操作下,栈中元素一直保持单调递增,故称单调栈。 正确性证明:假设j < i是i左侧第一个满足A[j] < A[i]的数。由假设可得,对于每个k(j < k < i),都有A[k] >= A[i],否则与假设矛盾。这些数都会被i出栈,出栈之后栈顶元素就是j。 同理从右往左扫描即可求出右侧第一个小于A[i]的数的下标。共遍历数据两次,每个下标最多入...
0
点赞
评论
收藏
转发
岩之痕
2019-08-22 14:15
已编辑
C++
X游戏题解
暴力搜索 复杂度O(NlogN) 暴力法,需要一个函数判断一个数是否是“好数”。好数可简化为不含3,4,7的且至少含一个2或5或6或9的数。对每个数,统计每个数字的出现数量再做判断即可。时间复杂度O(NlogN),因为要取出每个数的每个数位。 数位DP 复杂度O(logN) 好数的个数 = (只含018,25,69的数字数量) 减去 (只含018)的数字数量于是需要一个函数快速求1到N中,只含0182569和只含018的数字数量。 定义:F018(n)为区间[0, n)中只含018这3个数字的数的数量。为了方便计算,需要做以下定义。1.区间包含0,且左闭右开。2.该计算方法会为每个数加上前...
0
点赞
评论
收藏
转发
岩之痕
2019-08-22 14:15
已编辑
C++
搭积木题解
题目转化 首先将题目数据按照(W, L)排序。如果(W1, L1) < (W2, L2),再加上题目给的W <= L条件,则(W2, L2)只能被放在(W1, L1)下面。如果(W1, L1) = (W2, L2),两个积木完全相等,先后顺序没有限制,在不影响答案正确性的情况下,可以自己加上限制,排序之后排在后面的被放在下面。 这样,排在后面的积木一定被放在下方,则每种可能搭成的塔对应排序后的积木序列的一个子序列。这样,最高能够搭成的塔的层数等于L值的最长非降子序列的长度。 求解最长非降子序列 方法一、长度数组+二分 构建长度数组A。A[k]表示长度为k的非降序列的最小结尾数值。在...
0
点赞
评论
收藏
转发
岩之痕
2019-08-22 14:16
已编辑
C++
滑动窗口的最大值题解
题目 数组num的长度为N,求其所有长度为W的连续区间的最大值。 一、平衡树 直接用map来对每个出现的值计数,map可以直接加入,删除,求最大。时间复杂度O(NlogW)空间复杂度O(N) 二、Sparse Table 利用Sparse_Table算法思想,将区间[A, A + W) 分解成[A, A+R) 和[A+W-R, A+W) 其中R是满足 2*R >= W的最小的2的次方。分解成的两个小区间有重叠,但由于是求最值,重叠部分不会影响答案。预处理部分中需要得到从每个下标A开始长度为1,2,4,8,...,R的区间的最值。相比Sparse_Table算法,这里的空间可以优化成O(...
0
点赞
评论
收藏
转发
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务