Songjiu's Blog

What doesn't kill you makes you stronger

一维二维数组的区域和问题

力扣53、363等

求一维二维数组当中满足条件的某个子区域,一般包括求最大值,或者满足要求的某个值这两种情况。 一维数组 主要还是应用dp的思想,只不过在求满足要求的值时,可以用二分查找降低时间复杂度。 一维数组求最大连续值 lc53 def maxSubArray(self, nums: List[int]) -> int: #每一个对象要么是它本身,要么是他之前字串的和,这取决...

摩尔投票法

力扣229

该方法应用于求序列中,超过总数个数1/2、1/3…1/n的众数的情况,且该方法空间复杂度为常数,可以避免使用dict和map。 原理 超过总数个数的1/n的数字肯定小于等于n-1个,比如选择一个序列当中,超过序列总数一半(1/2)的数字,那这样的数字至多有一个(n=2,2-1=1),不可能有俩都大于总数个数二分之一的数,n等于其他时同理。 摩尔投票法,遍历整个序列,首先选中n-1个数字进入候...

线段树

力扣307

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。线段树方便与求区间段的值(如本题,正常的时间复杂度是N,而使用线段树可以达到LOG(N))、方便更新值以及求最小公倍数公约数(不知道咋弄,以后补充)。 线段树的生成 本题目当中,一个节点的值是他两个子节点的值的和。正常的线段树,应该包含:节点的值、区间段、左右孩子共四个部分。这里使用一...

Additive Number

力扣304

累加数是一个字符串,组成它的数字可以形成累加序列。 题目概述 题目概述 题目分析 dfs并减枝,利用栈,当里面不满足至少有两个数字的时候,就直接入栈,满足的话就进行检查,将合法的数字放到栈里面,不合法就出栈,继续遍历。(因为都是正整数,所以序列后面的数字长度肯定大于等于他前面的,这样dfs的时候可以减少一定的数量,但是我还没写。)注意数字0不能作为首位,因此当他出现在首位的时候,如果指示器已...

Number of digit one

力扣233

统计n以内数字1出现的次数。 题目概述 题目概述 题目分析 最早的想法就是从0到n遍历一遍,把每一个数字当中出现的1都数一遍,但是这种方法铁超时,因此考虑别的方法。从网上寻找了许多相关的解决方法之后,我感觉其中一种通过计算数字每一位当中1的数目的方式比较好,不但将代码写成python之后通俗易懂而且具有延展性,而且可以用作统计出现的2、3…n。 从该数字的个位开始向最高位遍历,确定每一位当中...

天际线

力扣218

onsite如果遇到这个题我直接GG回家谢谢惠顾。 题目概述 题目概述 题目分析 有点难度,折腾了一天才看懂别人的代码。总而言之,满足最终结果的点,如果看作高度与横坐标的二元组,其中高度满足:与前一次不同 横坐标满足:不被当前最高峰阻挡,满足这二点的二元组可以加入最终结果。 代码 def getSkyline(self, buildings: List[List[int]]) -> L...

House Robber

力扣198、213

题目概述 关于力扣打家劫舍问题的整理。该系列题型就是给定一个代表房屋价值的list,通过限定不能rob 相邻房屋来计算最终最大的利益是多少。 House Robber I 题目概述 题目分析 动态规划,共两种情况:1. rob i号房子,那么总收益为 i号 加上 i-2 的最大收益 (因为最短隔一间房子)2. 不rob i号房子,总收益为 i-1 的最大收益。因此只要比较1.2两种方式的大...

买卖股票的最佳时间问题

力扣121、122 、123、188

题目概述 关于力扣股票买卖最佳时间问题的整理。该系列题型就是给定一个代表股票价格的数组,通过不同时间的买卖来获取利益最大化。 Best Time to Buy and Sell Stock I 题目概述 题目分析 由于只能交易一次,因此需要找到在一个最小值与位于他后面的最大值,使得二者的差值在整个序列当中最大,因此遍历一次该数组,不断更新最小值以及最大值与最小值的差值即可。 代码 def ...

Dungeon game

leetcode 174

题目描述 解题思想 dp的思想,构建一个和原list相同维度的dp表,其中的每一位代表“走到该位置所需要的最小剩余生命值”,因此当构建完成该dp表之后,dp[0][0]就代表了英雄出发的最小所需要生命值。 开始构建dp表,由于需要得到dp[0][0]因此需要倒叙构建dp表,分以下三种情况: 1.dp表最后一位:也就是目的地需要的生命值,当该位置为正数时,只要生命值大于1就可以成功...

PHP一句话木马整理

如果我们通过客户端向服务器发送被执行内容,那么就会让服务器执行我们发送的脚本,挂马就实现了。想尽办法给目标网站插入这么一段会被储存起来的语句。可以是一个单独的脚本文件文件(.asp 、.php、.aspx ),或者是隐藏在某些网页下的文件、代码等。其中的value 就是客户端要发送的内容,然后通过客户端与服务器建立连接,发送控制脚本。 PHP PHP有一些危险的使用方式比如eval...