MYSDB-CSDN博客

原创【LeetCode】2015. Average Height of Buildings in Each Segment 每段建筑物的平均高度

扫描线（Sweep Line）算法。从左到右遍历每个出现过的坐标（不管是作为building起始还是结束）。关键思想是：永远维护一个[cur_s, x)的平均高度before（初始时假设为None）处理坐标x处的所有出点和入点（顺序无关），得到处理之后的平均高度after如果处理之后，平均高度发生了变化，那么就把[cur_s, x, before]加进去实现扫描线可以用哈希数组或者堆。heapfrom heapq import heappush, heappopclass Sol...

2022-05-23 14:01:54 239

原创【LeetCode】2250. Count Number of Rectangles Containing Each Point

基本上就是Binary Search简单二分因为题目的height只有100种可能，我的naive的想法是统计每个height的width，然后遍历到每个点(x, y)的时候，把height>=y的每个width数组都二分查找一遍……from collections import defaultdictfrom bisect import bisect_leftclass Solution: def countRectangles(self, rectangles: List...

2022-05-23 11:38:17 172

原创【LeetCode】1483. Kth Ancestor of a Tree Node 1483. 树节点的第 K 个祖先

由于O(N^2)的存储会超内存限制，所以直接记忆化肯定凉了。只能考虑O(NlogN)的存储，方法就对每个node都记下，它k=1,2,4,8,…时候的k祖先。比如，可以用f[h][node]表示node的2**h祖先是谁。需要注意的是，记这个的时候也得做一些优化，直接暴力遍历还是会超时。原理就是：node的2h2^h2h距离的祖先就是它2h−12^{h-1}2h−1祖先的2h−12^{h-1}2h−1祖先，f[h][node] = f[h-1][f[h-1][node]]。然后在query的时候，.

2022-05-17 08:09:18 197

原创【LeetCode】569. Median Employee Salary 员工薪水中位数

第一次做到SQL的题。window functionselect id, company, salaryfrom ( select *, (count(salary) over (partition by company)) / 2.0 as cnt, row_number() over (partition by company order by salary) as rk from Employee) t..

2022-05-17 04:25:38 210

原创【LeetCode】471. Encode String with Shortest Length 编码最短长度的字符串

题解这题其实分成了两个部分：DP：把大问题分割成小问题判断循环节：这样才能知道某段字符串可不可以缩DP/问题切割给定一段字符串s，如果存在某个中间位置k，把字符串分割成2部分s[:k]和s[k:]：如果s[:k]由循环节组成，假设已知它可以缩成substr，那么问题就变成了F(s)=substr+F(s[k:])F(s) = \text{substr} + F(s[k:])F(s)=substr+F(s[k:])类似地，如果s[k:]由循环节组成，同样假设它可以被缩成substr，那么.

2022-05-17 02:41:57 302

原创【LeetCode】1655. Distribute Repeating Integers 分配重复整数

一题多解。首先理解问题，可以抽象为：有若干物品，大小分别为quantity[i]。假如某个数字重复x次，可理解为有一个容量为x的背包要把物品放进背包里，问能不能放完DFS暴力解法，直接遍历所有可能，甚至也没有怎么剪枝，竟然也不超时……class Solution: def canDistribute(self, nums: List[int], quantity: List[int]) -> bool: packages = list(sorted(Coun.

2022-05-16 12:28:58 169

原创【LeetCode】1580. Put Boxes Into the Warehouse II 把箱子放进仓库里 II

简单贪心。因为题目的规则，很容易可以想到不管从左边还是从右边塞入，warehouse的容量肯定是一直递减的。所以很明显，最高的box如果从左边第一个，或者右边第一个开始就塞不进了，那么它就永远不可能塞进了。而如果它可以塞进去，那么塞进左边第一个（或右边第一个）会是最优的吗？是的。因为假设左边第一个位置不塞这个最高的，塞了次高的，那么由于后面的warehouse容量更小了，在最好的情况下也只能把最后的n-2个塞完，最高的这个永远塞不进去。所以：不塞这个最高的box不可能导致更差的结果。那么...

2022-05-15 09:06:07 216

原创【LeetCode】1654. Minimum Jumps to Reach Home 到家的最少跳跃次数

BFS.坑：因为不能后跳2次，通过-b往回跳的点，依然可以试图利用+a走一次。因为通过+a走到的点既能前跳又能后跳，不用再遍历了；而通过-b走到的点只能前跳，所以可能的情况下还是要通过+a走一次探索一下后跳的可能性。由于坐标一定是非负的，这里我用负数来表示某坐标是通过后跳走到的，这样就和前跳分开记录visited了。可以把visited和forbid用一个set记录由于x轴无限长，有可能无限尝试都得不到-1，尤其是在a<b的情况下。在a>b的情况下容易证明最远走x+b就可以了。而a&.

2022-05-11 07:41:31 245

原创【LeetCode】1353. Maximum Number of Events That Can Be Attended 最多可以参加的会议数目

明显的贪心，把区间从小到大排序之后，发生的越早的、持续时间越短的会议越优先参加。需要记录一下当前available的最早的天数（cur_s）。比如：[1, 2], [1, 4], [2, 2], [3, 3], [5, 6]的情况我们决定在第一天参加[1, 2]之后，cur_s就变成了2。需要注意的是：这时候在第2天才开始的会议就要加在一起讨论了！而那些在第1天开始的会议已经等价于在第2天才开始了（因为第1天已经被用了），也就是说，我们需要比较[2, 4]（原[1, 4]）和[2, 2]参加哪..

2022-05-11 03:30:38 128

原创【LeetCode】1901. Find a Peak Element II 找出顶峰元素 II

题目形容得很形象了，其实只要从任意一点出发，沿元素变大的方向走，走到再也走不了的时候，就遇到了峰值。如果我们当前在某行的最大值处：* 如果同一列的下面那行比它大，也就是说往下能继续找到峰顶* 吃果同一列的上面那行比它大，也就是说往上继续能找到峰顶* 都不是，那么当前点就是峰顶因此我们可以对行进行二分：class Solution: def findPeakGrid(self, mat: List[List[int]]) -> List[int]: M = len..

2022-05-10 13:47:00 371

原创【Leetcode】959. Regions Cut By Slashes 959. 由斜杠划分区域

解法就是并查集，把每个1x1的方格再划分成4个格子，比如这样：class Solution: def regionsBySlashes(self, grid: List[str]) -> int: n = len(grid) # print(n) num = n*n f = list(range(4*num...

2019-08-30 23:43:16 271

原创【Leetcode】795. Number of Subarrays with Bounded Maximum 795. 区间子数组个数

解法就是最大值不超过R的子数组里，也包括了最大值<L的子数组，以及最大值在[L,R]里的子数组，而这两部分是不相交的，所以利用互斥性，直接计算出【最大值不超过R的子数组】以及【最大值<L的子数组】的个数，然后相减即可class Solution: def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) ...

2019-08-27 13:43:35 170

原创【Kickstart】2019 Round C - Catch Some

解法假如最后必须返回终点，可以DP每个颜色记录狗的位置，从小到大排序对于f[i][s]表示，只考虑前i个颜色时，访问s个狗需要的最小时间那么有:f[i][s] = min(f[i-1][s], f[i-1][s-j-1]+2*P[i][j] for j in range(P[i])但是现在需要考虑最后不回家，那么需要增加一维，f[i][s][0]表示只考虑前i个颜色并且没有选择最后颜色...

2019-08-25 20:21:52 193

原创【Kickstart】2019 Round C - Circuit Board

解法算出每列往左的长度，然后就能转化成求直方图最大矩形的问题至于如何求第i行第j列往左有多长，需要每行维护两个双向队列minStack、maxStack和一个左边界l，对于范围(l,j]，minStack队头是这个范围内最小值（以及它在的位置），从队头到队尾，值和索引都是递增的类似地，maxStack队头是这个范围内最大值（以及它在的位置），从队头到队尾，值递减，索引都是递增的现在如果ma...

2019-08-25 19:59:14 214

原创【Kickstart】2019 Round C - Wiggle Walk

解法rc个点映射到一维ID，然后维护4个方向的并查集：比如E方向的并查集，最开始，每个点都代表它自己，当某个点被访问过之后，如果有人向东走到了这个点，那么它应该直接走到这个点东边第一个没有被访问的点，那就是这个点的root所以算法应该是这样的，对于每个被访问到的点x，找到它周围四个点e``w``s``n，然后E.join(x,e)，……join的时候要注意顺序，使得根永远是一个没被访问过的...

2019-08-25 19:58:39 220

原创【Kickstart】2019 Round E - Street Checkers

解法就是要求[L,R]里的每个整数中，有多少个整数的奇因子和偶因子个数之差不超过2.对于奇数来说，它只可能有奇因子，那么需要奇因子个数少于2，那么只能是质数或1对于偶数来说，假设x=2m⋅nx = 2^m\cdot nx=2m⋅n，其中n是奇数，那么x的因子有这几种情况：奇x偶：那么应该是(a,b⋅2m)(a,b\cdot 2^m)(a,b⋅2m)，其中ab=n，这时候不管a和b相不...

2019-08-25 19:54:26 379

原创【Kickstart】2019 Round E - Code-Eat Switcher

解法对于每天的a和b，我们不妨假设所有的时间都用来coding，这样能得到totalC的coding时间显然，如果totalC<a，这天显然不能完成否则，我们假设able = totalC-a，这表示多出来了able的coding时间，这些时间可以转化成吃饭时间我们肯定更prefer效率高的转化，比如我同样减少1单位的coding时间，在不同的timeslot可能会增加不同的吃饭时...

2019-08-25 19:37:46 326

原创【Kickstart】2019 Round E - Cherries Mesh

解法就是想求最小生成树，但是边的权重只有1和2，而且给出了权重为1的边，剩余边权重都为2显然，可以用最小生成树的某个算法，权重为1的边只加上那些能联通两个不同集合的边输入完毕之后会得到k个联通分量，需要k-1条权重为2的边，所以ans要再加上2(k-1)#include <stdio.h>#include <string>#include <iostrea...

2019-08-25 19:26:23 245

原创【Leetcode】1144. Decrease Elements To Make Array Zigzag 1144. 递减元素使数组呈锯齿状

解法可以从左向右扫一遍，直接取最少次数就好但是还有一种巧妙的解法如果对于数字a,b,c，想使得a>b<c，那么只需要令b = max(b, min(a,c)-1)，就能获得最少的操作次数那么对于其中一种pattern，就是使偶数位置满足a>b<c，另一种pattern，就是使奇数位置满足a>b<cclass Solution: def...

2019-08-23 20:05:03 311

原创【Leetcode】1153. String Transforms Into Another String 1153. 字符串转化

解法遍历一遍str1，就知道str1的每个字符应该映射到谁了但是1个字符不能映射到2个字符同时 str1里的字符个数应该少于str2里的字符个数此外，如果str2有26个字符时，除非两个字符串相等，否则不可能转化成功，因为str1此时也得有26个字符，但是不管动了哪个字符，映射完之后就只有25个字符了，这时候无法再映射回26个字符class Solution: def can...

2019-08-23 19:52:26 2872

原创【Leetcode】723. Candy Crush

解法……基本思路就是先标记要删的，然后重新生成table掉下来之后再次消除的方法原来就是重复一次上一轮操作啊……我还以为能有什么优化= =class Solution: def candyCrush(self, board: List[List[int]]) -> List[List[int]]: m = len(board) if m==0:...

2019-08-15 15:05:59 527

原创【Leetcode】713. Subarray Product Less Than K 乘积小于K的子数组

解法呃……竟然忘记了尺取法……class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: if k<=1: return 0 n = len(nums) l = 0 pro...

2019-08-13 20:44:39 100

原创【Leetcode】678. Valid Parenthesis String 有效的括号字符串

解法跟没有*的时候原理差不多，贪心，不断统计待匹配的左括号(的数量left，能匹配的时候尽量匹配*可以被分成三类：未转化的：它既可以转化成(，也可以转化成)转化成)的：它可以通过跟一个遇不到左括号的)交换，重新变成未转化的假设现在是这样的场景(A*B)，其中那个左括号是之前和*匹配的那个左括号，而右括号是一个遇不到左括号的右括号。首先，A和B肯定是合法括号串。因为A里的左括号必须...

2019-08-10 21:05:28 196

原创【Leetcode】651. 4 Keys Keyboard

解法解法一：基本DP基本思想是维护一个数组f[i]f[i]f[i]表示使用i次操作时能得到的最大长度假如最后一次是多加一个A，那么得到长度f[i-1]+1最后的操作是连续k个粘贴，那么全选+复制+k个粘贴一共k+2个操作，能得到f[i-(k+2)]*(k+1)长度那么，状态转移方程就是从这里面取最大值，时间复杂度为O(N)class Solution: def maxA...

2019-08-09 21:40:06 366

原创【Kickstart】2019 Round A - Parcels

解法BFS+二分，首先通过BFS能遍历得到每个位置到最近的office的距离，同时也能得到最大值r与些同时设置l=0，然后就开始对[l,r]进行二分查找判断k是否可行的条件是：是否存在一个位置(i,j)，使得在这里放一个office之后所有grid的距离都不超过k，找到一个最小的k即可具体说来，需要将曼哈顿距离进行转换：dis(⟨x1,y1⟩,⟨x2,y2⟩)=max{abs((x1+y1...

2019-07-18 01:08:25 209

原创【Kickstart】2019 Round B - Energy Stones

解法乍一看，如果是搜索的题，要枚举所有吃的顺序，那应该是O(n!)复杂度，估计吃不消所以得往DP方向考虑，那么就有点像01背包问题，能量是物品的价值，而背包大小则是所有石头食用时间的总和但是跟01背包问题不同的是，最后的能量和吃的顺序有关，而01背包里最后的能量跟物品放进背包的顺序无关，所以能拆解成子问题想了半天也不会做看完解答之后很有启发，对于这种跟顺序有关的情况，如果给定任何一个石头...

2019-07-17 12:34:29 464

原创【Kickstart】2018 Round H - Let Me Count The Ways

解法用容斥原理做假设P(n,i)表示n对夫妇时，有i队夫妇粘在一起的种类数：我们选出i对夫妇，有C(m,i)种可能，把粘在一起的夫妇算做一个人，总共有2n-i个人全排列种排法，每个粘在一起的夫妇都有2种排法，所以总共有P(n,i)=2i(2n−i)!CmiP(n,i) = 2^i(2n-i)!C_m^iP(n,i)=2i(2n−i)!Cmi种可能，整个问题的种类数就为：S(n,m)=P(...

2019-07-11 17:55:22 217

原创【Kickstart】2018 Round H - Mural

解法这题主要靠分析……太牛逼了首先，肯定最后会涂上连续的K=⌊N+12⌋K = \lfloor\frac{N+1}{2}\rfloorK=⌊2N+1⌋块，我们需要判断这个区间在哪而所有可能的位置都可以实现！！！假设我们的想涂上[i,i+K)部分，我们只需要从中间开始如果是奇数，那么从中间石块开始画如果是偶数，最中间有2个石块，选择离边缘更近的那个开始画：比如K=4的场景oo123...

2019-07-11 17:54:46 140

原创【Kickstart】2018 Round F - Palindromic Sequence

解法这个题我看解答都想了好久= =对于小数据集，当N<=100时，可以通过计算出以S为前缀的字符串有多少个来慢慢遍历，记作PN(S)P_N(S)PN(S)为了方便大数据集的分析，我们把空串也算上，空串是K=0对应的串处理过程伪代码如下：def solve(l,N,K): prefix = "" while True: if K < P(prefix+"$")...

2019-07-09 15:53:16 392

原创【Kickstart】2018 Round G - Cave Escape

解法看到陷阱只有15个能反应过来是状态DP，但是不知道怎么个DP法……首先，不考虑能量够不够，每个状态直接用DFS/BFS可以得到一个最终能量值E[s]，这个状态下能够到但是不在状态里的陷阱集合adjTrap[s]，还有这个状态能不能出去isAble[s]这三个东西出来之后就可以DP了，设f为状态s可以取得的最大能量：f[s]初始为-1如果isAble[s]==true，那么f[s]=...

2019-07-09 01:37:49 279

原创【Kickstart】2018 Round G - Combining Classes

解法C++的整数长度真是令人头秃解法本身不难，假如我们有个大小为10910^9109的数组，Line Sweep遍历每个下标的时候可以得到该下标的点的个数但是数组太大了，只能采取离散化的思想，用map记录坐标轴每个R+1，表示多一个新区间，每个L-1-1，表示离开一个区间最后从后往前遍历map，遍历到i的时候累加的前缀和grp（还没加上map[i]时的值)表示的是(i,i->nex...

2019-07-07 01:10:41 297

原创【Kickstart】2018 Round G - Product Triplets

解法靠测试数据过的……19年没有测试数据恐怕要凉……比较简单，统计每个数字的出现次数times[i]当其中2个数的乘积为d时：d=0，乘积为0可以是3个0，和2个0加上一个非0数，所以增加C(times[0],3)+C(times[0],2)*(n-times[0])d=1，乘积为1只可能是三个1，所以增加C(times[1],3)d>1，最后这种情况比较简单，对d进行因子分解...

2019-07-07 01:09:56 314

原创【Kickstart】2018 Round F - Specializing Villages

解法是Google Kickstart公开课里的解法：首先，需要分析出，当每个点都找它们直接相邻的边里的最小值时，距离最近。每个点都只取与它直接相连且距离最小的那条边时，我们可以得到一张子图：[外链图片转存失败(img-AzLi7slT-1562315720963)(quiver-image-url/31F02DCC828C6FB099EE1387BFD57340.jpg =90x94)]...

2019-07-05 16:35:58 344

原创【Kickstart】2018 Round E - Milk Tea （与官方解答不同）

解法每一位置0或者置1会得到的投诉数很容易算，就是竖着求和如果没有forbidden做法，就是很简单的DP每个状态都检索感觉挺大的，标准答案的做法是每扩展一位，都挑出投诉数最小的101个方案，因为只会ban掉100个方案，所以这最小的101个里肯定有可以用的我用了TRIE，把forbidden pattern放到一棵trie里，然后dfs这棵树，比如我们总共10位，遍历到前缀1001时...

2019-07-04 18:24:13 193

原创【Kickstart】2018 Round E - Yogurt

解法基于比较的排序这个比较简单，就是贪心法#include <stdio.h>#include <string>#include <iostream>#include <memory.h>#include <stdlib.h>#include <unordered_set>#include <map&g...

2019-07-04 18:11:46 131

原创【Kickstart】2018 Round D - Funniest Word Search

解法第一步，分别统计以(i,j)结尾的，长度不超过k的单词总长度，横着和竖着分别记作h[i,j,k]和v[i,j,k]然后我们考虑DP，状态为f[i1,j1,i2,j2]四重循环遍历的时候：i2每增加1的时候，总是从f[i1,j1,i2,j1]开始的，这是竖着的一列，所以我们需要知道这一列里：横着，以区间(i1,j1)到(i2,j1)之间的字符结尾，长度不超过1的单词总长度，假设这...

2019-07-02 23:25:20 258

原创【Kickstart】2018 Round D - Paragliding

解法对于每个气球(x,y)，如果它可以被拿到，那么需要有塔，其塔尖(p,h)在阴影部分：分析可知需要满足：h≥∣p−x∣+yh\ge |p-x|+yh≥∣p−x∣+y，即x+y≥p+hx+y\ge p+hx+y≥p+h且y−x≥h−py-x\ge h-py−x≥h−p把每个点从(x,y)进行坐标变换成(x+y,y-x)所以对于每个气球，只要找有没有横纵坐标都比它大的塔即可。#inc...

2019-07-02 19:39:18 170

原创【Kickstart】2018 Round D - Candies

解法首先，跟区间和和滑动窗口有关系计算区间和，首先要把前缀和算出来总之，要先固定一个区间的端点，可以是左，也可以是右。假如我固定的是左端点l，要找合适的右端点r。要保证这个区间奇数个数不超过o个然后需要找到r，使得P[r]-P[l-1]是满足P[r]-P[l-1]<=d且最大的那个，也就是说，P[r]要是不超过P[l-1]+d但最接近它的一个这个得用upper_bound来做（如...

2019-07-02 16:23:15 323

原创【Kickstart】2018 Round C - Kickstart Alarm

解法就是数学优化+快速幂+除法取模结合在一起首先，数学优化比较容易，最后肯定是要变成每遍历一个数就加一次。对于ama_mam，它可以是子数组里的第1,2,…,m个，而它是第i个的子数组一共有(N+1−m)(N+1-m)(N+1−m)个，当计算POWERj{POWER}_jPOWERj时，它的系数就是1j1^j1j，2j2^j2j，3j3^j3j,…,mjm^jmj，所以最后ama_mam...

2019-07-01 00:47:16 209

原创【Kickstart】2018 Round C - Planet Distance

解法就是有个无向图，保证只有一个环，求每个点到环的距离首先找到环上的点从环上的点开始dfs找环有很多种方法，DFS，BFS还有拓扑都可以找#!/usr/bin/env python# -*- coding: utf-8 -*-from collections import defaultdict,dequedef solve(n,edges): circle = s...

2019-07-01 00:45:35 144

空空如也

空空如也