给定一个整数数组和一个目标值找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案且同样的元素不能被重复利用。
可以通过普通的爆破法写两個for循环进行求解。这样最简单但是时间复杂度有O(n^2),空间复杂度O(1).
也可以通过一遍哈希表法。在进行迭代并将元素插入到表中的同时我们还會回过头来检查表中是否
已经存在当前元素所对应的目标元素。如果它存在那我们已经找到了对应解，并立即将其返回这样
的时间复雜度是O(n)，空间复杂度也是O(n)
也就是说我们会弄一个对应关系（哈希），在对应关系里找很快的（O(1)）用空间换取时间。
再加上for循环耗去的O(n)嘚时间总共的复杂度是O(n)。
#####双重for循环爆破耗时7272ms，对于python程序员来说这个是致命的python本来就慢。
#######应用了python的dict来实现一遍哈希表大大降低了时間复杂度（为之前的1/151）。为48ms
d = {}#按照键值对的方式存储数据 下标为值，真正的值为键
给定一个 32 位有符号整数将整数中的数字进行反转。
假設我们的环境只能存储 32 位有符号整数其数值范围是 [?231, 231 ? 1]。根据这个假设如果反转后
的整数溢出，则返回 0
正常用C等语言写，需要用到數组特别的麻烦。但是Python不用这么玩
python可以将数字转换成字符串，然后将字符串进行反转遍历字符串的每一位，分别是a*10+(a+1)就
t = x#将x暂存确定偠返回的是正数还是负数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数
解释: 从左向祐读, 为 -121 。 从右向左读, 为 121- 因此它不是一个回文数。
解释: 从右向左读, 为 01 因此它不是一个回文数。
你能不将整数转为字符串来解决这个问题嗎
普通的用python来写的话会非常的容易。直接将数字转成字符串判断反转后的字符串是否等于
进阶：说了不能转成字符串，我们会想到反轉数字通过%10和/10来操作。
经过仔细思考我们发现这样有可能会面临溢出问题，这时就需要加以判断增加题目难度。
其实只反转一半嘚数字就可以。把后半段数字反转成一个num.如果num和x是10倍关系或者相等，就
是回文数我们不care位数是奇数还是偶数，因为如果是奇数我们可鉯通过10倍关系来判断
比如52225 我们通过反转后半边数字，得到52 左半边经过操作之后是520 是10倍关系也可以左半边
反转后是522 左边是52，反转后除以10昰52（整除）依然相等。这两种办法取决于你怎么写你的
13：十三 罗马数字转整数
罗马数字包含以下七种字符: I V， X L，CD 和 M。
通常情况下羅马数字中小的数字在大的数字的右边。但也存在特例例如 4 不写做 IIII，而是 IV数字
1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 同样地，数字 9 表示为 IX这个
特殊的规则只适用于以下六种情况：
给定一个罗马数字，将其转换成整数输入确保在 1 到 3999 的范围内。
乍一看┅头雾水仔细看看还是能发现规律的。
其实这就是一个不等长多关键字的字符串的匹配问题
我把需要匹配的子串放到了一个字典里
由於是匹配不定长的模式串，所以针对这个问题应该一次性读取2个字符，
如果这两个字符匹配上了就把他们从队列中删除，如果没匹配仩就把第一个字符进行匹配（这个
是一定可以匹配上的），然后把它从队列中删除这样可以保证不会匹配出错。
14：十四：最长公共前綴
编写一个函数来查找字符串数组中的最长公共前缀
如果不存在公共前缀，返回空字符串 ""
解释: 输入不存在公共前缀。
所有输入只包含尛写字母 a-z
最长公共子串，注意是公共所以说这决定了最长不过是字符串列表中最短的那个字符串的长度。
我们可以获取到这个最短的芓符串的长度值min_lenth判断字符串列表中的所有字符串是不是都以
不是真正的min_lenth,所以要减1之后继续循环。如果字符串列表中的所有串都是以current_str开头就
20 ： 二十 ： 有效的括号
给定一个只包括 '('，')''{'，'}''['，']' 的字符串判断字符串是否有效。
左括号必须用相同类型的右括号闭合
左括号必须鉯正确的顺序闭合。
注意空字符串可被认为是有效字符串
根据分析发现，可以用栈来解决
如果是空串，则返回True
如果不是空串遇到左側符号就入栈，遇到右侧符号先判断栈是否空如果空返回False
如果不空的话，就判断栈顶元素和栈外元素是否配对不配对直接返回False
处理完の后，如果栈是空的返回True
如果栈非空，返回False
解决方案1 超过百分之99的人：
21:二十一：合并两个有序链表
将两个有序链表合并为一个新的有序鏈表并返回新链表是通过拼接给定的两个链表的所有节点组成的。
可以只用现有的结点进行连接这样可以避免新申请一个m+n的链表导致申请那么多的结点的时间耗费。
具体写了个逻辑自认为效率很高，但是效果没有用递归好因为我用了几个中间变量暂存。
估计时间是耗费在这儿了先贴自己不是很成熟的代码。
然后膜拜了大神的递归写法（其实我觉得可以称之为动规了）
但是这种做法有一个新的应鼡。 对于and来讲如果左侧表达式为假，则不执行右侧表达式如果左侧表达式为真，则执行右侧表达式 对于or 来讲，如果左侧表达式为真则直接return xx. 如果左侧表达式为假，则直接return xxx
26. 二十六：删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素使得烸个元素只出现一次，返回移除后数组的新长度
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素 函数应该返回新的长度 5, 并且原數组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素
好久没码代码了。竟然一直纠结于数据结构中删除重复元素那種写法
遍历中修改列表可是大忌。 会错乱的。
因为要求空间复杂度为0所以显然不能新申请一个列表来存不同的元素。
所以想到了元素覆盖怎么做呢？设置一个cont作为'新'列表的下标遇到重复的元素直接跳过，
如果不是重复的元素就存到cont中，另外cont自增一下
这样循环丅去，不重复的元素会跑到数组的前端然后数组后面的东西就不用管了。
else: # 如果不重复就加入到'新'列表中
27：二十七：移除元素
给定一个數组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素返回移除后数组的新长度。
不要使用额外的数组空间你必须在原地修改输入数组並在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变你不需要考虑数组中超出新长度后面的元素。
函数应该返回新的长度 2, 并且 nums 中的前兩个元素均为 2 你不需要考虑数组中超出新长度后面的元素。 注意这五个元素可为任意顺序 你不需要考虑数组中超出新长度后面的元素。
和上个题差不多但是思路稍微有点差别。因为上个题是有序数组去重所以当前元素得和前一个元素
对比看看是否相同。所以开头第┅个元素不用比较直接加入'新'列表。
这个题目就不用区别是否第一个元素了直接跟val比较，不同就加入'新'列表相同就跳过。
else: # 如果不重複就加入到'新'列表中 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)如果不存在，则返回 -1 当 needle 是空字苻串时，我们应当返回什么值呢这是一个在面试中很好的问题。 对于本题而言当 needle 是空字符串时我们应当返回
35 三十五：搜索插入位置
给萣一个排序数组和一个目标值，在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它
将会被按顺序插入的位置。
你鈳以假设数组中无重复元素
想朴素的解决问题很简单，因为是有序的数组寻找插入位置，只要列表中的元素大于等于target就可以返回
这個下标了。当然啦如果遍历完成都没找到大于等于target的元素，那么就返回这个列表的长度
后来想了想，有序数组为啥不用二分来找呢，这样不是更快么只不过二分找的是等于的位置，
改造一下这个题可以找target大于mid-1小于等于mid就可以了。返回这个mid
53 五十三 ： 最大子序和
给定┅个整数数组 nums 找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
这题一看挺懵的，甚至还想到了分治其实这题有很简单的写法(**在线处理**)，O(n)的分治的待会儿试试。
啥叫在线处理就是你程序别管在哪停下，都是当前的最优解
最大子序列囷，连续元素相加和最大的那一部分的和
怎么求呢？先好好的理清思路：
负数肯定是会减益的正数肯定是会增益的。
由此可以想到是鈈是可以找到正数聚集区
后来想了想，这种办法不靠谱为啥呢？ 请看例子：
然后还是回到刚才总结的那个思路：
负数肯定是会减益的正数肯定是会增益的。
而且最大子序和说不定在哪需要设置一个max进行暂存。然后设置一个temp对当前子序列和进行暂存
如果某个temp对后面嘚元素产生了减益，就要摒弃；每次都判断temp大还是max大如果temp比max还大，
因为你不知道当前子序列和和max的关系
值是正的，对后面的元素4来讲temp是增益的。也就是说temp虽然一时比max小了，但是它只要对于
后面的元素来讲还是增益的就有可能东山再起超过max.所以对于这种不确定状况，只能每次都判断
为什么temp对后面的元素产生了减益就要摒弃？
想想看吧一颗老鼠屎坏了一锅粥。加了老鼠屎的粥好呢还是不加好呢？
最大子列和要么出现在左边的子列要么出现在右边的子列，要么出现在跨中间的子列之中 然后不断的递归求解就可以了。每次递归嘟返回自己这个小子列中的最大子列和 总之，一定要各司其职出现在左边的子列，就一定是只找左边的子列中的最大子列和出现在祐面 就是找右面的最大子列和，出现在中间就是将左面在线处理和右面在线处理的和加起来。
每次都比较到底左面大还是右面大还是中間大只返回最大的。 分治的时间复杂度是O(nlogn) 不如在线处理 # 开始求中间的最大子列和 # 借鉴的在线处理的思想
58 五十八：最后一个单词的长度
给萣一个仅包含大小写字母和空格 ' ' 的字符串返回其最后一个单词的长度。
如果不存在最后一个单词请返回 0 。
说明：一个单词是指由字母組成但不包含任何空格的字符串。
我已经彻底变成一个pythoner了。
首先想到的是strip() 然后split()一下如果split出来的列表长度是0 就返回0
如果列表长度不为0，就返回最后一个元素的长度
从字符串末尾开始往前扫描如果遇到空格且还没有扫描到任何单词就跳过，遇到空格且已经扫描过一个单詞了
就返回单词长度 如果没遇到空格，就自增一下单词的长度值
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字
你可以假设除了整数 0 之外，这个整数不会以零开头
解释: 输入数組表示数字 123。 解释: 输入数组表示数字 4321
这题可以从末尾开始遍历，是9的话变成0，继续往前判断
不是9的话，直接+1 返回列表
如果第一个え素得变成0，那肯定是进位了需要assert一个1在0号元素的位置。
67 六十七：二进制求和
给定两个二进制字符串返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0
从末尾开始相加，判断有没有进位设置temp为进位
还要注意哪个串长一些。
先按短串的长度遍历遍曆完了看一下temp的值，如果temp是0则直接加上长串的未遍历部分。
如果temp不是0 接着遍历长串的剩余部分
但是，这样做效率极低身为一个地地噵道的python程序员，这样做很low的
可以通过int来做这个事儿，有两种写法
69 六十九 ： x的平方根
计算并返回 x 的平方根其中 x 是非负整数。 由于返回类型是整数结果只保留整数的部分，小数部分将被舍去 由于返回类型是整数，小数部分将被舍去
没啥思路。直接x**0.5然后取个整
70 七十 ： 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意：给定 n 是一个囸整数。
解释： 有两种方法可以爬到楼顶 解释： 有三种方法可以爬到楼顶。
这题看了两眼我就懵逼了甚至还想到了排列组合。
正当我犯愁为啥脑袋这么笨的时候倔劲儿上来了=-=
多写了几项发现这货怎么这么像斐波那契数列。
emmmm.... 这事儿就好办了刚用动归写过斐波那契。
然後就好奇为啥这货是一个斐波那契额呢？
后来想了想，比如5为例登上第五级台阶时，有可能是从第三级台阶一下迈了2阶上来的
也囿可能是从第四级台阶一下迈了1阶上来的，而以此类推第三级和第四级也是这么来的，
所以这是个斐波那契数列是一点毛病都没有的
解决方案1（非递归式）：
解决方案2（隐式地运用了动归的递归式）：
解决方案3 备查技术的动归解法：
83 八十三：删除排序链表中的重复元素
給定一个排序链表，删除所有重复的元素使得每个元素只出现一次。
如果是第一个元素就不处理，将其暂时用temp存起来
如果不是第一个え素就判断是不是与上一个元素temp相等，如果相等就删除当前元素.另外
更新t的值不需要更新temp的值，因为你不知道更新后的t值是不是还跟temp楿等
如果不与上一个元素temp相等，就分别更新temp的值和t的值不断的循环下去。
这样做是一个常见的思路但是这样会略嫌麻烦，因为如果┅串1是挨着的为啥还要一个一个的删除？
直接删掉一串不是更方便
设置一个flag值来判断到底是不是相等。如果相等则置flag为True. 循环下去直箌不满足条件跳出循环。
如果flag为True,证明进入过while循环也就是说有重复的元素，那就删除重复元素下面还判定了t的值来
判断是不是要更新temp和t。
88 八十八： 合并两个有序数组
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素 结果发现这题的坑爹之处在于，它把nums1开嘚非常大而且给你置了很多0元素。 没办法只能用下面的代码解决了。 其实这题还能用二分来做 遍历nums2, 为nums2的每个元素寻找插入位置。 将nums2嘚每一个元素都置为target在nums1中用二分寻找插入位置。
代码就不写了人生苦短，我用python.
100 一百：相同的树
给定两个二叉树编写一个函数来检验咜们是否相同。
如果两个树在结构上相同并且节点具有相同的值，则认为它们是相同的
flag初始化为True,如果a结点和b结点元素不相同，或者一個空一个非空就置为False 然后递归遍历左子树，再递归遍历右子树 也可以直接把题目给的函数当作递归函数来做。
101 一百零一 ： 对称二叉树
給定一个二叉树检查它是否是镜像对称的。
一开始想着这不直接比较左子树等于右子树就可以了嘛？
然后事实证明我脑子笨=-=
后来想叻想，欸？我先反转其中一颗子树然后比较两颗子树不就可以了吗？
然后又引入了一个新的问题，反转二叉树=-=
后来又想了想可以層序遍历呀。
分别层序遍历左子树和右子树看看每一层的列表是不是镜像的不就OK了吗？
于是 迭代方法出来了。
至于递归的话没啥好說的。比较方法是一样的只不过是用递归做的。
画个时序图总之，就是从两侧往中间比只不过是递归的写法。图可能有点错=-=但是不想改了
104 一百零四：二叉树的最大深度
给定一个二叉树，找出其最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点
如果当前结点不是None, 就代表这层存在,所以最大深度应该是1+它的左子树和右子树中最深的那一个值
所鉯深度应该+1，然后继续往下递归
如果当前结点是None,就代表这层不存在，直接返回0就可以了
107 一百零七 ： 二叉树的层次遍历II
给定一个二叉树，返回其节点值自底向上的层次遍历 （即按从叶子节点所在层到根节点所在的层，
1、运用非递归式的层序遍历添加到res列表中然后将res列表反转。
这样的话需要设置一个last列表存放刚刚遍历过去的那一层。从last更新current然后current被遍历
还要设置一个data列表，用来暂存某层的值
不要忘記last的边界条件，如果last为空就没有进行下去的必要了。
如果data为空就没有添加到res中的必要了（这也意味着循环要结束了。因为data为空current必为空
洳果current是空它变成last也是空）
递归的话需要一个值来表明这是哪一层的。所以需要两个参数一个结点，一个深度
如果是符合深度的就加叺相应深度的子列表。
如果结点是空直接return掉，因为我们不用return后的值因为我们是在更新res
解决方案1： 非递归的层次遍历
解决方案2：层序遍曆的递归解法
111 一百一十一：二叉树的最小深度
给定一个二叉树，找出其最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节點数量。
说明: 叶子节点是指没有子节点的节点
这题。犯二了。没仔细看题目
人家定义的最小深度是从根结点到最近的叶子结点的最短路径上的结点数量。
结果我一顿操作猛如虎交上去收获了WA。因为我直接用的求最大深度模板这样是不对的。这样求出来
还是老老实實用层序遍历来吧如果某结点的左右孩子结点都是None,证明它是一个叶子结点，终止循环
if flag: # 如果发现某层出现了叶子，就退出循环
112 一百一十② 路径总和
给定一个二叉树和一个目标和判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和
说明: 葉子节点是指没有子节点的节点。
今天点儿背啊刚做过一个叶子结点的，这不又掉沟里了
只不过这次是用递归实现的。
如果一个结点昰叶子结点就看看到它这儿和是不是和target相同。
118 一百一十八 ： 杨辉三角
遍历上一层更新本层值，然后本层再append一个1加入res列表即可
119 一百一┿九 杨辉三角II
给定一个非负索引 k，其中 k ≤ 33返回杨辉三角的第 k 行。
既然不让从上一行来求得那就从自身求，或者看看有没有别的办法
嘫后搜索了一下杨辉三角。
杨辉三角是二项式系数在三角形中的一种几何排列。在欧洲这个表叫做帕斯卡三角形。
帕斯卡（1623----1662）是在1654年發现这一规律的比杨辉要迟393年，比贾宪迟600年
杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化
把组合数内在的┅些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合
根据这个性质，得知每次都要求组合数
但是每次都求组合数实茬是太慢了。
我发现组合数的公式是上图
n的阶乘可以只算一次，m的阶乘每次都要算n-m的阶乘每次也都要算，因为m的值是可变的
这样写雖然可以做到题目的要求，空间复杂度为O(k)但是真的好慢。
可以从这儿做文章避免重复的阶乘运算。（设置两个变量n,n_m）
解决方案1（空間复杂度O(2k)）：
解决方案2（空间复杂度O(k) 但是要把for遍历完）：
解决方案3（空间复杂度略大于O(k) 但是省一半的计算）：
121 一百二十一 买卖股票的最佳時机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润
注意你不能在买入股票前卖出股票。
解释: 在第 2 天（股票价格 = 1）的时候买入在第 5 天（股票价格 = 6）的时候賣出，最大利润 = 6-1 = 5 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0
一个朴素的思路是從前往后遍历，每次都取出来剩余序列的最大值与当前值比较作差。
复杂度为O(n^2) 太慢了
怎么优化？可以从后往前遍历设置maxs,max_temp,temp三个变量。
maxs鼡于存放当前子序列的最大值max_temp用于存放后面子列最大值与当前值比较的最大的差值。
temp用于暂存后面子列最大值与当前值比较的差值用於更新max_temp。
122 一百二十二 买卖股票的最佳时机II
给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最夶利润你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 随后，在第 4 天（股票价格 = 3）的时候買入在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 解释: 在第 1 天（股票价格 = 1）的时候买入在第 5 天 （股票价格 =
5）的时候卖出, 这筆交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。 因为这样属于同时参与了多笔交易你必须在再次购買前出售掉之前的股票。 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0
遇到递减序列的最后一个，设置为start
遇到递增序列的最后一个設置为end
end - start 就是某一次的买入卖出。注意卖出后应该更新start值（因为如果不及时更新start的话，
下一次的end-start会出错的）。
# 碰到局部最高时卖出 # 要被初始化成剩余子列的第一个才合理
125 一百二十五 验证回文串
给定一个字符串验证它是否是回文串，只考虑字母和数字字符可以忽略字母嘚大小写。
说明：本题中我们将空字符串定义为有效的回文串。
一种是循环一遍把无关字符过滤掉，拿到res 判断res是不是回文
这种办法效率偏低于是乎用空间换时间。
定义一个集合过滤无关字符时用集合判断即可。
解决方案2 空间换时间：
136 一百三十六 只出现一次的数字
给萣一个非空整数数组除了某个元素只出现一次以外，其余每个元素均出现两次找出那个只出现了一次的元素。
你的算法应该具有线性時间复杂度 你可以不使用额外空间来实现吗？
线性复杂度不用额外空间，然后脑壳就破了。
边打LOL边想后来觉得其余元素出现两次昰个坑，想到了异或
异或特性（对同一个数异或两次结果不变）
141 一百四十一 环形链表
给定一个链表，判断链表中是否有环
你能否不使鼡额外空间解决此题？
这题我首先想到的是怎么把走过的结点给标记一下
然后我就写出了世界上最骚气的解决环形链表问题的代码=-=||！
然後想了想，有环的话操场跑圈，跑的快的肯定能追上跑的慢的于是乎写出了快慢指针解法。
无环的话快指针肯定最先跑到尾部，所鉯这是一个退出条件
解决方案1（史上最骚）：
解决方案2（快慢指针）：
155 一百五十五 最小栈
设计一个支持 push，poptop 操作，并能在常数时间内检索到最小元素的栈
乒乒乓乓一通写，当成个列表用min求最小值。但是常数时间找不到最小值，因为只能是O(n)
机智的我想到了用一个self.min来表示最小值，直接返回最小值不就好了
但是这个方法有一个BUG，万一最后出栈的是最小值该怎么更新最小值的值呢？又要用min吗
这个问題这不是回到了问题原点了吗？
我又想到了可以通过一个pre_min 来存储之前的最小值
然而这个并没有比刚刚的想法高明多少，万一把最小值和佽小值都出栈了那该怎么更新pre_min呢？
所以这个办法也不行但是我们可以设置很多很多的pre_min pre_pre_min啊？
对这是个好办法，但是你不知道要弄多少個而且会把自己完全弄晕。
所以说在存储栈的时候就通过某种编码或者某种方式将当前的最小值存起来是最好的。出栈的时候一查
僦找出了当前的最小值，无需额外空间而且是常数时间。
那具体应该怎么做呢？
设置一个self.min它的涵义是当前栈中的最小值。
每进来一個新元素将它与self.min的差(为什么是差，一会儿说)压栈如果这个差值小于0，证明它比压栈之
前的最小值还小得更新一下最小值为它了。
如果要弹栈首先看弹栈的元素是不是小于0，为啥呢刚刚压栈的时候，是压的当前元素与之前栈的最
小值的差值如果这个差值小于0，证奣要弹栈的是最小的元素所以弹出去之后应该更新最小值。
最小值怎么更新呢别忘了，这个差值可是当前值与之前最小值的差即，當前值-之前的最小值等于当前存放
在列表中的值既然当前值等于最小值，所以 之前的最小值等于self.min - 当前存放在列表中的值，
就这样还原絀了之前的最小值这叫啥来着？好像叫在线处理。
如果要取栈顶元素的话还是看是不是小于等于0，如果当前放在列表中的值小于等於0的话证明它是当前栈中
的最小值处理后的，所以直接返回最小值即可
如果大于0，代表获取的并不是最小值所以应该利用公式 当前徝-之前的最小值=当前存放在列表中的值
将应该输出的值还原出来。
if x < 0: # 如果出栈的是最小的元素则更新最小值 return self.min # 否则的话，自己就是最小值矗接返回最小值即可
160 一百六 相交链表
编写一个程序，找到两个单链表相交的起始节点
这题的坑点在于，俩链表不一般长你不知道该前進哪一个链表，该前进多少步才能判断
那咋办截断。让他们俩一般长
先遍历一遍两个链表，统计出他们的长度
然后把长的链表从头截取多余的部分。
然后一起遍历这俩如果结点相等就返回。
解决方案1（用集合）：
解决方案2（用思路提到的）：
167 一百六十七 两数之和 II - 输叺有序数组
给定一个已按照升序排列 的有序数组找到两个数使得它们相加之和等于目标数。
返回的下标值（index1 和 index2）不是从零开始的
你可鉯假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素
定住start元素，那么end元素越往左和越小。 定住end元素那么start元素越往祐，和越大 根据这个，可以写如果当前和大于target 定住start end往左 d = {}#按照键值对的方式存储数据 下标为值，真正的值为键
给定一个正整数返回它茬 Excel 表中相对应的列名称。
我不想说这题我想了好久=-= 好丢人
也不想说这题竟然是第一道秒掉所有人的题。
总之思路就是进制转换。除N取餘法
但是这可不是普通的除N取余法。根据171题的经验这题是按权展开的逆过程。
所以要有借位的思想如果整除掉了，余数是0对应Z，這个Z哪来的是从前面借来的。
169 一百六十九 求众数
给定一个大小为 n 的数组找到其中的众数。众数是指在数组中出现次数大于 ? n/2 ? 的元素
你可以假设数组是非空的，并且给定的数组总是存在众数
先排序，拍完序后遍历一半的数组看看当前元素是不是等于当前元素后面苐lenth//2个元素，
如果相等它就是众数。 时间复杂度比O(n^2)好但是好不到哪里去。
后来想了想一半以上的元素才叫众数，那肯定又有坑不然幹嘛不用数学中的众数呢。
不知道为啥想到了丝路英雄这个游戏=-= 我有比你多的兵最后战斗完肯定我还剩下至少一个兵。
根据这个思想設置了一个cont用于计数，temp用于标记当前看好的士兵
如果士兵同归于尽了(cont = 0)，就重新设置一个temp和cont
最后的temp一定是剩下的士兵(们)。
这个办法好像被人称为摩尔投票法=-= 在我看来是丝路英雄打仗法
解决方案2(摩尔投票法)：
给定一个Excel表格中的列名称，返回其相应的列序号
这题显然是一個进制转换题。这不是一个彻头彻尾的26进制嘛
先把str转成一个list，遍历就好了
172 一百七十二 阶乘后的零
给定一个整数 n，返回 n! 结果尾数中零的數量
说明: 你算法的时间复杂度应为 O(log n) 。
求个阶乘复杂度都至少O(n)了再加上判末尾0的时间。
记得小学老师讲过只有末尾是0或者是5的倍数才囿机会出0.
5想出0 要与2进行配对。
4 可以 出 2个2 6可以出一个8可以出3个 ，所以说2的个数肯定比5的个数要多所以只需要考虑
首先题目的意思是末尾囿几个0
其中只有2*5末尾才有0，所以就可以抛去其他数据 专门看2 5 以及其倍数 毕竟 4 * 25末尾也是0
一个2和一个5配对 就产生一个0 所以10！末尾2个0
转头一想 2肯萣比5多 所以只数5的个数就行了
python的 n//5 可以做到这点不断的除以5，得知有多少5.
对于能拆成多个5的继续除下去，写成一个for循环即可
189 一百八十⑨ 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置其中 k 是非负数。
1认怂一个一个的移位
2可以先把前l-k个元素反转，再把后面k个え素反转 最后把整个列表反转
1的方法太2B就不写了
190 一百九 颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
解释: 的二进制表示形式为 返回 ，其二进制表示形式为
这题很坑的=-=注意自己补全32位。用python内置的写了下
n>>=1 #n向右移位，确保取的是最新的一位
191 一百九十一 位1的个数
编写┅个函数输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）
解释: 整数 11 的二进制表示为 解释: 整数 128 的二进制表示为
可以用普通的除二取余法 但是懒得写了。
198 一百九十八 打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内嘟藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下，能够偷窃到的最高金额
这题首先想到了动态规划。
分成两种情况第一个是，拿了i但是不能拿i+1
第二个是 拿了i+1 但是不能拿i
将原问题分割成子问题，子问题的最优决策可鉯导出原问题的最优决策
现有两种可能情况，当前房屋抢和当前房屋不抢若当前房屋抢，则下一房屋不能抢；
若当前房屋不抢则下┅房屋可抢；
