2 Anxdada

尚未进行身份认证

多读书多看报, 少吃零食多睡觉

等级
TA的排名 5k+

LeetCode #4 寻找两个有序数组的中位数

传送门题意:给定两个有序数组,求中位数思路:中位数实际上就是找中间那最多两个数,然后两个数组又是有序的,所以可以转换成求两个有序数组合并后的第k大问题,所以我们需要有一个函数求对于两个有序数组求第k大,那么如何最快的求第k大了,很明显我们在两个数组中同时各取一半的数字(k/2),如果第一个数组的这位置(起始位+k/2-1)的数字比第二个的小,那么说明这第k大肯定是不在第一...

2019-08-15 14:20:24

LeetCode 560 Subarray Sum Equals K【前缀和】

传送门题意:有多少个连续子序列和为给定的k,思路:连续,就要想到前缀和,所以我们利用前缀和的性质,相减等于中间的和,那么直接记录每个前缀的次数,然后累加即可,注意这类问题0这个数都是会作为默认点加的!不要忘了,想想也是对的ACCodeclassSolution{public:intsubarraySum(vector<int>&...

2019-04-21 23:08:09

LeetCode 1,167, 15, 18 (2, 3, 4)数之和相关问题

传送门1这类题都是给定个类似a+b+…=x,问有方案数.我们对于这种都用拆分的思想,然后用小的去解决大的,首先我们说2sum.我们对n个数先排序,然后两个指针,一个开头,一个结尾,然后往中间动,如果x-b>a(b是后面的指针指的值,a是前面的指针指的值),很明显如果再让j(后面的指针)动,那么x-b会越大,所以要让i(前面的指针)动,...

2019-04-21 22:46:34

LeetCode 124 Binary Tree Maximum Path Sum

传送门题意:跟定一颗带点权二叉树,问其任意一条路径的最大值是多少.(路径,任意一点出发和结束的路径)思路:其实就两种情况,一是左右子树加上本身结点构成一条路,二是将自己和左右子树更优的连接起传给父亲结点成路.所有的情况就是这两种情况的综合,所以按照这个写就行了.ACCode/***Definitionforabinarytreenode.*struct...

2019-04-19 01:46:20

LeetCode 4 Median of Two Sorted Arrays【经典题目】

传送门题意:给定两个有序数组,要求在O(log(m+n))的复杂度之内求出合并后的中位数思路:数据水,线性的也能过.但是面试遇到就不一定能过了.所以还是得想正解.有个log,所以我们用二分来做,具体做法就是每次算一算第k/2在哪里,分别取出中间的来比较,再按照大小关系递归算出,第k大在哪里,每次递归减少k/2,所以就是logk(k≈m+n),所以复杂度合理!A...

2019-04-19 01:42:36

LeetCode 342 4的幂

传送门题意:就是判断一个数是不是4的幂思路:2的幂已经写烂了,4的幂的话也是在2的幂的基础上考虑的,首先要保证是2的幂,然后观察4的幂的性质,发现2进制的1一定在奇数位上,那么我们需要一个用来验证奇数位上1的数字,那就是0x55555555,因为0x5=0101,所以可以验证,同理类似的题目都是这样做.ACCodeclassSolution{public:...

2019-04-18 23:50:50

LeetCode 137 只出现了一次的数组||

传送门题意:只有一个数字出现了一次,其余数字都出现了三次.问一次的那个数字是多少.思路:相信2次的已经做烂了,那么这道改编的了?一个二进制位只能表示0或者1。也就是天生可以记录一个数出现了一次还是两次。x^0=x;x^x=0;要记录出现3次,需要两个二进制位。那么上面单独的x就不行了。我们需要两个变量,每个变量取一位:ab^00=ab;ab^a...

2019-04-18 21:35:17

Codeforces #251 D题 Devu and his Brother 【三分】

传送门题意:给定一个长度为n的a数组,和一个长度为m的b数组,每次可以选任意一个数组的任意一个元素,让它+or-1,问最少执行多少步,可以使得a数组的最小值>=b数组的最大值.思路:很明显,我们需要找到那个临界值,并且一定是处于一个中间水平,太大或者太小都不行,所以可以用三分处理,然后统计答案就行,详情看代码实现.ACCodeconstintma...

2019-03-20 01:40:08

西北大学校赛B题 北境之都 【三分】

传送门题意:给定n座房子的高度,要求任意两座房子的高度差在m以内,每个房子只能改变一次高度,将一个房子的高度改变k米的花费是k^2万元,求最低要花费多少万元思路:很明显,将一个房子的高度放在过高或者过低的都是不最优,而是中间的某个值,比如样例就是45,所以我们可以三分一下最低高度x,然后x+m作为最高高度,比x小的变为x,比x+m大的变为x+m,然后取最优值...

2019-03-19 21:35:20

LeetCode 834 Sum of Distances in Tree

传送门题意:给定一棵树,输出每个点到其他点的距离之和.思路:首先我们先dfs一遍,存下每个点的子节点数(包括自己),和一个值称dp,dp[u]表示u的所有子节点到u的距离之和,那么很容易也可以在第一次dfs中维护,那么此时dp[0](假设0是根节点),就是0的答案,那么其他的答案了,实际上可以通过父亲的ans来转移,此时ans[0]=dp[0],那么假设0的字...

2019-03-19 15:04:46

HDU 6446 Tree and Permutation【思维】好题!

传送门题意:给定一个n,那么1-n是一个排列,定义某个排列(xyz)的值为x-y,x-z在树上的最短距离和,求这个排列的全排列的值相加等于多少,树的形态会给出.思路:算边的贡献,首先对于任意一个排列,它是树上某点到其他点的距离之和,然后由于全排列,实际上就是树上任意两点之间的距离之和(考虑顺序),首先树上任意两点之间的和我们会求(考虑每条边的贡献,即边的两...

2019-03-19 14:58:10

LeetCode 810 Chalkboard XOR Game【思维】

传送门题意:给定n个数,两个人轮流上去删除一个数字,如果在某个人删除后,剩下的数字异或等于0,那么这个人就输了,Alice先手,如果它能赢returnTRUE.思路:考思维,首先全部数字异或等于0需要二进制的每一位上1出现偶数次,那么如果刚开始就异或等于0,Alice肯定就赢了嘛,否则如果剩下的数字是偶数Alice也一定能赢,因为每次删除一个数字后剩下的数量一定是奇数...

2019-03-19 14:45:03

LeetCode 793 Preimage Size of Factorial Zeroes Function【思维】

传送门题意:给定一个x!后零的个数k(<1e9),问满足x的数字有多少个.思路:很好的一道题,我们一步步解决.1:如何求x的阶乘末尾0的个数?10进制中只有2和5相乘才会得到10,也就是每有一对2和5,就多一个末尾的0而阶乘又是从1开始乘到x,所以2的个数总是比5多,那么问题转化为求x!中有多少个5作为因子公式为k=x/5+x/5^2+x/5^3+...

2019-03-19 14:36:14

LeetCode 995 Minimum Number of K Consecutive Bit Flips【思维】

传送门题意:给定一个长度为n的01数组,每次可以将连续的k位翻转(o->1,1->0),问能否将整个数字变成全1,能的话最少翻转多少次.思路:很明显可以分析出的是,一但遇到0了,那么一定要翻转,并且以后都不能再翻转它了,也就是跟着翻转下去,所以一个很暴力的想法就出来,直接每次暴力翻转连续的k位,那么复杂度是接近于n^2的,所以我们就不写了,那么我...

2019-03-19 14:31:25

leetcode 1015 Numbers With Repeated Digits

传送门题意:给定一个N,求1-N中,输出至少有一位数字是重复的数字的个数.思路:很明显,这道题要用数位dp,考虑两点,一是前导零的影响,二是记录的应该是每一位的次数,而不能是简单的标记和清空标记,比如101和110.所以状态想好为dp[i][j][k]表示起始位i,当前位j,是否已经有重复位数k(0or1),然后做记忆化搜索就行,没啥坑点.ACCo...

2019-03-18 20:40:13

小米OJ编程比赛 2月常规赛 Carryon 数数字

传送门题意:给定l,r通过以下步骤求答案1:需要将l到r之间的数全部转化成16进制,然后连起来2:将连起来的数又转化成10进制3:将最终结果对15取模数据范围:1<=L<=R<=1e12思路:首先推导,假设区间[L,R]转化为16进制后连起来为xyz.那么答案是多少了.ans=(x*16^2+y...

2019-03-18 19:30:32

HDU 2089 数位dp解法

传送门(数位dp入门题)题意:就是求给定区间内数字中不含4和连号62思路:很入门的数位dp,dp[len][state]表示当前第len位,并且前一位是否是6,然后记忆化搜索即可,因为每到一个位置的数字,都有两种状态,需要分开考虑.lldp[30][2],shu[30];lldfs(intst,intstate,intlimit){if(s...

2019-03-18 17:34:59

LightOJ 1205 Palindromic Numbers

传送门题意:求给定区间内回文数字的数量思路:很明显求区间内满足某种条件的数字个数,就用数位dp,然后想好状态,我这是三维dp[st][cur][state]表示起始位是st,当前位是cur,是否构成回文数字(state1是,.0否)然后就是内部循环怎么写了,总体思路就是前一半的位置上的数字任意填,然后到可以填后一半时,不仅要填,还要对称的填,然后依次记忆化搜索即可l...

2019-03-18 17:21:37

谈数位DP

在了解数位dp之前,先来看一个问题:例1.求a~b中不包含49的数的个数.0<a、b<2*10^9注意到n的数据范围非常大,暴力求解是不可能的,考虑dp,如果直接记录下数字,数组会开不起,该怎么办呢?要用到数位dp.数位dp一般应用于:求出在给定区间[A,B]内,符合条件P(i)的数i的个数.条件P(i)一般与数的大小无关,而与数的组成有关.这样,我...

2019-03-17 22:54:38

牛客练习赛 41 B 题 【简单的dp计数】

传送门题意:就n个数,开始分数为0,第i次操作可以有两种选择1:给分数加上a[i]2:给分数乘-1问n次过后分数为-666并且任意一次操作后分数不能是666的方案数是多少?(%1e8+7)思路:很明显的dp计数,dp[i][j]表示i次操作后分数为j的方案数,那么转移方程是dp[i][j]=dp[i-1][j-a[i]]+dp[i-1][-j];去掉...

2019-03-02 15:27:47

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。