夕林山寸-CSDN博客

原创剑指 Offer（第 2 版）出现频率从高到低已经完结100题

剑指 Offer 03. 数组中重复的数字遍历+mpclass Solution {public: int mp[100007]; int findRepeatNumber(vector<int>& nums) { for(auto x:nums){ mp[x]++; if(mp[x]>1)return x; } return nums[0]; }}

2020-11-22 11:15:56 831

链表问题一般使用快慢指针来找中点或判是否有环141. 环形链表/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: bool hasCycle(ListNode *head) .

2021-01-07 20:02:02 337

原创 25. K 个一组翻转链表链表问题

链表操作问题，熟悉操作后就好做了，每次选取k个，进行翻转，记录头尾，和上一次的末尾节点，进行反转拼接即可。在纸上画出来就清晰了/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(n

2020-12-25 20:42:37 148

原创牛客编程巅峰赛S2第11场 - 钻石&王者ABC题解

A牛牛浇树用前缀和快速维护区间和，最后算奇偶性即可。const int M =2e5+7;class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 返回m天后高度为奇数的树的数量 * @param n int整型 * @param m int整型 * @param l int整型vector * @param r int整型vector ..

2020-12-22 21:18:39 187

原创 lc字节题库模拟面试 27. 移除元素 421. 数组中两个数的最大异或值 48. 旋转图像

27. 移除元素swap交换即可class Solution {public: int removeElement(vector<int>& nums, int val) { int n=nums.size(); int r=n-1; for(int i=n-1;i>=0;i--){ if(nums[i]==val)swap(nums[i],nums[r]),r--; }

2020-12-21 21:02:53 135

原创牛客编程巅峰赛S2第10场 - 钻石&王者 ABC

反思一下:简单题没想好就急着敲，浪费时间，难的题反而做的快，因为想好了后代码是不会出问题的。所以还是要先想清楚过程确定没问题在敲代码，主要是想的时间。A:奇怪的排序问题想清楚每次操作的过程就好做了：肯定是从高往低去处理，(因为无论你怎么动矮的，都不会让高的人往后走)对于当前最高的人x，如果他不是最后面的一个，则需要花费1次把他移动到最后排。（且他原本的位置置为空）如果他是当前最后排，则不需要移动。处理过程注意维护空的位置即可。const int M = 1e6 + 10;

2020-12-18 21:05:06 180 1

原创 lc字节跳动题库系列——3. 无重复字符的最长子串滑动窗口

滑动窗口On搞一搞即可。class Solution {public: int lengthOfLongestSubstring(string s) { int n = s.length(); if(n==0)return 0; int l=0,r=-1; int mp[227]={0}; int mx=0; for(int i=0;i<n;i++){ while(r

2020-12-18 11:19:03 160

原创第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海） C Sum of Log 数位DP

看到这个是式子，本能的去考虑枚举一些东西。显然logx 最多有30种取值枚举log(i+j)是一个不错的选择。log(i+j) == x时，2^x <= i+j <= 2^(x+1) - 1;相当于求i、j的方案数，满足i/j二进制下至少有一个第x位取1，然后高位全取0，且低位每一位做多一个数取1，且满足X,Y的上界要求。显然这是一个经典的数位DP。直接暴力搞即可。但是裸的数位DP刚好会T，30*30*4*100000 刚好T掉。。评测机不行啊。所以我们要利用

2020-12-18 10:57:38 190

原创剑指 Offer 43. 1～n 整数中 1 出现的次数数位DP

比较简单的数位dp不用思考。简单粗暴class Solution {public: int dp[2][11][11];//是否达到上界,到第几位数,前面已经有j位1，这种情况下可构造出的数中1的个数。 int d[11],len; int dfs(int len,bool limit,int nm){ if(len==0){ return nm; } if(~dp[limit][len][nm])r

2020-12-15 11:28:27 132

原创剑指 Offer 64. 求1+2+…+n 递归 || 快速加

1：利用&&先判前面，若前面为假则不判后面的技巧class Solution {public: int sumNums(int n) { //(1+n)*n/2; (n>1) && (n += sumNums(n-1)); return n; }};2：利用快速幂，手写whlie循环，最多14次class Solution {public: int sumNums(int

2020-12-15 11:03:14 132

原创字节题库模拟面试——根到叶路径上的不足节点、验证IP地址、平行课程

根到叶路径上的不足节点一遍dfs，记录根到当前点的距离，和叶子节点到当前点距离最大值。然后判断以下是否删除即可。链表维护的树，写了半小时。。太慢了/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), rig

2020-12-11 16:23:39 131

原创字节题库——440. 字典序的第K小数字树上递归优化

经典的树上前缀和找第k个节点。比如权值线段树就用到了这个技巧。typedef long long ll;class Solution {public:/*11 21 2 1 2*/ ll cal(ll pre,ll n){ ll nxt=pre+1; ll ans=0; while(pre<=n){ ans+=min(n+1,nxt)-pre; pre*

2020-12-10 20:09:59 138

原创字节题库系列——LCP 22. 黑白方格画状态枚举 || 数学

状态压缩枚举注意n*n == k 的情况class Solution {public: int a[7][7]; int paintingPlan(int n, int k) { int nm=0; if(k==n*n||k==0)return 1; for(int sta=0;sta < ( 1 << (2 * n) );sta++){ memset(a,0,sizeof(a));

2020-12-10 19:18:32 133 1

原创剑指 Offer 44. 数字序列中某一位的数字数学分析迭代

class Solution {public: int findNthDigit(int n) { /* 1 10 2 90 3 900 4 9000 5 90000 6 900000 7 9000000 */ if(n<=9)return n; n-=9; long long nm=90,tp...

2020-12-10 17:09:07 103

原创 470. 用 Rand7() 实现 Rand10() 随机数的技巧

经典面试题。使用拒绝采样法可以让大的rand实现小的rand。比如：rand10() -> rand7()只取1-7，其余重新随机即可。现在就是让rand7扩域。可以考虑如下式子:rand49() = 7*(rand7() - 1) + rand7();然后利用好每个数进行优化：40以内取模，40以上变成rand9()再处理一次。变成：rand63()，60以下取模，以上变成 rand3()再处理一次。最后变成rand21().20以下取模，...

2020-12-09 11:51:53 202

原创牛客编程巅峰赛S2第7场 - 钻石&王者 ABC

A:注意是子序列，也就是分三段，ABC段，结果为min(na,nb,nc)(na:A段中'a'的个数，nb:B段中'b'的个数，nc:C段中'c'的个数)由于这里的特殊性，我们可以用双指针。枚举a，c的个数。然后l，r指针向中间移动，直到'a','c'都加1，预处理出'b'的个数，在指针移动时更新nb。每次更新完求值即可。const int M =1e6+7;class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿

2020-12-08 21:19:54 158

原创剑指 Offer 41. 数据流中的中位数大根堆+小根堆设计

这题思路很好想。但我刚开始复杂度算错了。。。差点用主席树刚。。。class MedianFinder {public: /** initialize your data structure here. */ priority_queue<int>g; priority_queue<int, vector<int>, greater<int> >s; MedianFinder() { while(g.s

2020-12-08 19:12:47 154

原创剑指 Offer 59 - I. 滑动窗口的最大值单调队列

单调队列入门题。即使排除非最优解。适用于有单调性的答案最优性求解。class Solution {public: int q[100010],l,r; vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n=nums.size(); l=0,r=-1; vector<int>v; for(int i=

2020-12-08 18:39:13 100

原创剑指 Offer 30. 包含min函数的栈辅助栈的使用

。。。又是刚开始没思路，但看了tag后直接想到用递减栈维护（注意这里不是单调栈）然后啪的一下很快啊，就敲出来过了。维护一个普通栈A，递减栈B（B的栈顶始终维护站内最小元素，即B栈维护的元素a[i],是1-i中最小的元素）。比如：5 3 8 7 1 6 5B栈： 5 3 1当弹出到与B栈顶元素相同的元素时，弹出B栈class MinStack {public: /** initialize your data structure here. */ stack&.

2020-12-05 16:53:52 180

原创 leetcode 链表专题（c++）出现频率从高到底

21. 合并两个有序链表直接(模拟数组归并排序的合并)合并即可。后面链表排序，会用到这个知识点。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} *

2020-12-05 16:05:12 233

原创牛客编程巅峰赛S2第6场 - 钻石&王者 ABC

A：String II枚举最后子序列是什么字符，然后暴力处理结果即可。class Solution {public: /** * * @param k int整型表示最多的操作次数 * @param s string字符串表示一个仅包含小写字母的字符串 * @return int整型 */ int a[1100]; int string2(int k, string s) { // write co.

2020-12-04 21:00:38 236

原创剑指 Offer 66. 构建乘积数组前缀和后缀和 || 前后遍历进行空间优化

leetcode面试题比较喜欢优化空间。。这是ACMer比较少干的事情，需要习惯。。。直接前后扫两边算贡献即可。const int M = 1e5+7;class Solution {public: vector<int> constructArr(vector<int>& a) { int n=a.size(); vector<int>b(n,1); int tp=1; for

2020-12-04 19:58:44 126

原创 850. 矩形面积 II 线段树+扫描线，acmer的简洁代码

acm经典线段树入门题，leetcode的困难题。。const int M = 410;typedef long long ll;const int mod = 1e9+7;#define ls o*2#define rs (o*2+1)class Solution {public: struct LINE{ ll x,y1,y2,op; bool operator < (const LINE &r)const{

2020-12-04 16:23:54 265

原创剑指 Offer 65. 不用加减乘除做加法 C++位运算模拟加法

我们知道异或是不进位的加法，对于二进制来说，当某一位均为1时需要进位。则a&b的值中位数为1的位表示需要进位，由于后面的进位不会超过1，则某一位最多进位1次。a+b = a^b + (a&b)<<1；这里的加法还是无法解决，但转化为了子问题，即可以递归解决。当a||b为0时，结果显然。class Solution {public: int gao(int a,int b){ if(a==0)return b; i.

2020-12-03 19:08:01 250

原创剑指 Offer 04. 二维数组中的查找双指针搞一搞

双指针搞一搞class Solution {public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { if( matrix.size()==0||matrix[0].size()==0)return false; int n=matrix.size(); int m=matrix[0].size(); i

2020-12-03 17:14:38 185

原创剑指 Offer 56 - I. 数组中数字出现的次数

若对n个数每一位的个数出现次数统计后：显然对于二进制下的每一位，若nm%3==1则是只出现一次数字的二进制位。则有了两种方法：第一种比较简单，但时间复杂度多个常数32.直接按位计算每一位出现次数，然后最后求ans即可。方法二：设立有限状态机，根据关系推导出公式，一般化到每一位即可。//ab /* 总共三种状态：当前位%3==0 a=0,b=0; 当前位%3==1 a=0,b=1; 当前位%3==2 a=1,b=0; */ ...

2020-12-03 17:03:22 170

原创剑指 Offer 33. 二叉搜索树的后序遍历序列 DFS递归+单调栈性质分析

1：dfs递归直接模拟后序遍历即可class Solution {public: bool gao(int l,int r,vector<int>& p){ if(l>r)return true; int rt=p[r],mid=r-1; for(int i=l;i<r;i++){ if(p[i]>rt){ mid=i-1;

2020-12-03 15:42:41 195

原创剑指 Offer 60. n个骰子的点数动态规划

为啥最近老是忘了dp啊，每次都是先写暴力。。。思维退化了嘛。。这题简单的DP：dp[i][j],投第i个筛子，总和j的个数class Solution {public: int dp[12][67]; vector<double> dicesProbability(int n) { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=n;i++){...

2020-12-02 20:13:11 194

原创剑指 Offer 52. 两个链表的第一个公共节点巧妙的双指针

方法一：固定长度起点，然后同时往下走。方法二：双指针看代码就懂了。。设公共部分C，A长度A+C,B长度B+C；最终会在A+B+C处相遇/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution

2020-12-02 19:57:01 159

原创剑指 Offer 19. 正则表达式匹配经典字符串匹配dp

之前刷CF的时候经常碰到字符串DP。但刚开始做的时候以为是个模拟，想了好一会没思路，看了动态规划这个tag后直接秒了。。一般字符串DP的状态设置：dp[i][j],a串匹配前i个，b串匹配前j个，的方案/状态/合法与否。然后就是一些细节处理了。。class Solution {public: int dp[1100][1100]; int a[1110],b[1100]; bool isMatch(string s, string p) { i

2020-12-02 19:32:46 157

原创剑指 Offer 07. 重建二叉树 dfs递归 + 栈迭代两种方法

方法一：dfs对于一颗子树，前序遍历的第一个点一定是根节点。然后在中序遍历中找到对应的根节点，左边的点就是左子树，右边是右子树。然后根据左子树的个数找到右子树在前序遍历对应的根节点即可。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : va

2020-12-02 18:30:29 386

原创牛客编程巅峰赛S2第5场 - 钻石&王者 ABC

a:双指针#include <bits/stdc++.h>using namespace std;typedef long long ll;#define re register#define ls (o<<1)#define rs (o<<1|1)//#define m (l+r)/2#define pb push_backtypedef pair<int,int> pii;const double PI= acos(-1.0);

2020-12-01 21:14:14 240

原创（计网：自顶向下P69小练习）用telnet向Web服务器发送HTTP请求 WIN10全部过程配图详解

目录1：打开控制面板2：点开程序与功能3.点击启动或关闭Windows功能4.勾选Telnet Client5.输入win + R 、键入cmd 打开dos命令行6.键入：telnet gaia.cs.umass.edu 80 （现在就打开了一个到主机gaia.cs.umass.edu的80端口的TCP连接）7. 启动本地回显（注意这几步要块，否则Web服务器会自动断开TCP连接）进入黑屏dos框后按： CTRL + ]然后输入： set localecho 启...

2020-11-30 17:01:34 1008

原创牛客编程巅峰赛S2第3场 - 钻石&王者 ABC

A:简单的公式先看a:显然有a[2]=3*a[1];a[3] = 3 * a[2]; 显然能找到规律：a[n]=3*a[n-1];b同理。然后证明：a[n] = 2*a[n-1] + 3*a[n-2];若a[n-1] = 3*a[n-2] ,则a[n] = 3*a[n-1]; (带入上式可得)由于n<=2 时 a[n]=3 * a[n-1];所以这个关系可以递推到全部。b同理。class Solution {public: /** ...

2020-11-24 21:35:57 219

原创剑指 Offer 37. 序列化二叉树 C++ ostringstream istringstream 的使用

这题是困难完全是因为输出和输出格式的问题。。具体用法见代码。。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Codec {public:

2020-11-24 16:20:45 209

原创剑指 Offer 11. 旋转数组的最小数字&&154. 寻找旋转排序数组中的最小值 II 奇怪的二分

能退化的二分。。。这复杂度最坏是On的。看来跟ACM还是有点区别啊，实际中碰到的基本都是随机数据，在随机上跑的优秀就行，就像快排？class Solution {public: int findMin(vector<int>& numbers) { int n=numbers.size(); int l=0,r=n-1; while(l<r){ int m=(l+r)/2;

2020-11-24 15:49:49 174

原创剑指 Offer 62. 圆圈中最后剩下的数字约瑟夫环倒着递推

分析过程在代码里了。约瑟夫环这种倒推思路好久不写，竟然没想出来怎么做。。class Solution {public: int lastRemaining(int n, int m) { /* 从最后一轮往前推，倒数第i-1轮有i-1人，假设最后剩下的人再当前轮次的标号是index。则倒数第i轮被杀的人的标号为：(m-1) % i, 其中标号为 m % i,的人是第i+1轮

2020-11-24 15:09:47 183

原创面试题 16.25. LRU 缓存 && 146. LRU 缓存机制双向链表 + hash_map

之前牛客多校用数组模拟链表写过一次100多行的。。。这次用链表写个简单点的：map里存链表对应key的迭代器class LRUCache {public: int cap; unordered_map<int ,list<pair<int,int> >:: iterator>cache; list<pair<int,int> >lt; LRUCache(int capacity) {

2020-11-22 16:53:54 176

空空如也

空空如也