0%

Algorithm 题解目录


算法刷题目录,方便自己查找回忆复习 之后(2018.9.27)只更新leetcode上的题了,也懒得整理源码了,leetcode上都存了,只记录思路吧

mark

Leetcode

排序

  • 75:给出一个只包含0,1,2的数列,排序形成[0,0,...,0,1,...,1,2,...,2]的形式,在原数列上修改。借鉴Lomuto partition algorithm,维护三个区间[0,i],[i,j],[j,k]为0,1,2的范围,按优先级,若当前数为2或1或0,先将nums[k]=2,k++,若当前数为1或0,则nums[j]=1,j++,若当前数为0,则nums[i]=0,i++,越往后能覆盖前面的,优先级越高。
  • 164:给出一个无序数列,请在O(n)时间复杂度内找到数列有序化后相隔元素差最大值。桶排序,设数列中最大值最小值分别为max,min,易得这个相邻元素差最大值肯定大于(max-min)/(n-1)并设这个值为gap,n是数列长度。将数列的取值区间[min,max]以(max-min)/(n-1)为间隔分成nums个桶,nums是int((max - min) / gap + 1),把数列各个元素分到桶中,每个桶只存对应区间内的最大元素和最小元素,把那么最大间隔肯定在相邻两个桶的边界处(前一个桶的最大值和后一个桶的最小值),因为桶内的最大间隔小于gap。最后遍历一遍桶就可以了。
  • 179:水题,给出一个数列,要求把各个数连起来组合成一个最大的数。字符串排序

堆、栈、队列

  • 23:合并K个有序链表为1个有序链表,用最小堆存所有链表头节点,依次取出插入到新链表中
  • 150:算术表达式,栈,python的switch写法
  • 224:带括号的算术表达式,栈,巧妙地方法处理括号,如果括号外是负号则符号乘-1否则乘1
  • 373:在2对有序数组中找出有最小和的k组数对,优先队列

组合数学

  • 47:生成n个数字的所有组合,数字有重复,依次插入数字到已生成k个数字组合的k+1个空中,排重直接用集合,Top Solution中用插入处后一个数字是否重复来排重

搜索与查找

  • 74:在一个有有特定顺序的矩阵中查找,两次二分查找
  • 78:生成子集,递归或者迭代,每个数字分加入子集或者不加入子集进行递归
  • 79:在一个字母矩阵中查找单词,深搜
  • 89:生成格雷码,迭代,每次在最前面加1或0,格雷码上下对称
  • 140:将一个字符串按给定词典加空格成句子,记忆化搜索
  • 153:一个有序数组拆成两部分再倒接一起,查找,特殊的二分查找
  • 154:153如果加入重复数字的变形,加入一个条件,二分的start和end是相邻不重复的第一个
  • 240:74的改版,每一行每一列有序,查数,对行和列分别做二分,数肯定在满足条件的行与列的交集处,还有其他解法

  • 98:判断一颗二叉树是不是查找树,即左子树都小于节点,右子树都大于节点,中序遍历看看是不是递增数列即可,递归或者栈
  • 101:判断一棵二叉树是不是对称的,递归,注意递归的是(left.left,right.right)和(left.right,right.left)即内外两队子节点,另外可以用栈实现迭代版本
  • 106:给出中序遍历后序遍历,求前序遍历。后序遍历的最后一个是根节点,在中序遍历中找到这个根节点并在后序遍历中删除,根节点以左是左子树,以右是右子树,这时后序遍历的最后一个节点就是左子树的根节点,递归即可
  • 107:从下往上从左往右输出树每一层的节点,用二维数组记录答案,如果二维数组的一维长度即层数比当前遍历的节点层数少就新建一层存答案。可以直接dfs,或者用栈和队列替代递归,如果用栈就是dfs,如果用队列就是bfs
  • 108:构造一棵二叉查找树,递归
  • 114:给一棵树,按前序遍历将其压扁,变成一棵只有右节点的树。将一个节点压扁操作定义为,把左子树置空,右子树变成原左子树,原右子树接在原左子树的尾节点上,原左子树的尾节点就是按前序遍历这个子树遍历到的最后一个点。递归,先压扁左节点,再压扁右节点,再回溯压父节点
  • 144:求一棵树的前序遍历,利用栈,弹出一个节点记录值,并先压入右节点,再压入左节点
  • 515:求二叉树每一层的最大值,BFS

图论

  • 130:水题,把一个图中被黑子包围的白子全部替换成黑子,直接从边上找出所有白子并存起来,再将整个棋盘涂黑,把白子复原。存的是top solution,写法很pythonic

数学题

  • 4:给出两个有序数列,求出两个数列合并后的中位数,要求时间复杂度O(log(m+n)),所以不能直接一个一个比较。中位数的意义是把序列拆成长度相等两部分,大部分中最小数比小部分中最大数大,根据这个原理将两个序列拆成两部分,设两个数列长度分别为m,n,设数列1在i位置拆开,数列2在j位置拆开,则需要保证:1:两个长度一样,则\(i+j=m-i+n-j\);2:两个数列的小部分的并集的任意数比两个数列大部分的并集的任意数要小,因为拆开后的部分依然有序,因此这个条件就是\(B[j-1] <= A[i] and A[i-1] <= B[j]\),i的位置确定,j的位置就确定,因此只需二分查找i的位置即可。注意奇偶性和边界判断。
  • 57:给出一组区间,插入一个新区间并合并。模拟
  • 122:水,一行代码,找一个序列中的最大相邻元素差
  • 142:给出一个链表,找出链表中环的起点。依然是快慢钟算法,设一快一慢两个指针一起从链表开始走,第一次相遇时说明存在环且他们步数之差是环的长度,而且可以推算出链表起点到环起点的距离等于相遇点到环起点的距离,就可以找到环的起点
  • 166:给出除数被除数写出结果,包括循环小数显示,数学分析题,小数不断乘10除除数,更新余数,余数出现重复即小数出现重复
  • 172:求n!中0的个数,数学分析题,0来自5*2,就看n中有多少5及其倍数
  • 202:快慢指针,求循环的一种方法
  • 263:数学题
  • 264:数学题
  • 313:数学题

字符串

  • 131:将一个字符串分成回文子串,用python的[i::-1]很好找,也是一行代码
  • 242:水题,python字典的使用
  • 301:给定字符串,删除最小数目的括号使得字符串中所有括号匹配,输出所有情况。注意两点:正序逆序各做一遍,因为有删左括号和右括号两种方案;所有情况都要输出,用集合存取所有情况
  • 451:按频率统计字母,哈希,python字典
  • 541:部分字符串翻转,模拟,注意python切片的使用

贪心

  • 134:加油站排成一圈,给定各个加油站可以加的油和站与站之间路程所耗的油,问可以走完一圈需要从哪个加油站出发,数据保证答案唯一,贪心,如果前i个加油站走不完了,那么出发点就设成i+1
  • 402:从一个大数中移除k个数字,使得新的数最小,栈,贪心
  • 452:重叠区间问题,贪心

动态规划

  • 70:经典问题爬梯子,斐波那契数列,dp
  • 96:给一个1到n的数列,问可以构造出多少不同的bst。设ans(i)为长度为i的数列能构造不同的bst的个数,我们需要找到ans(i)与ans(i-1)的关系,引入中间变量f(i,n),指以第i个数字为根构造bst,长度为n的数列能构造不同的bst的个数,这里可以找到递归关系,根左边的子数列构造出根的左子树,设有left种不同的左子树,右数列right同理,则f(i,n)应该是left*right,即f(i,n)=ans(i-1)*ans(n-i),同时以不同的i为根会有完全不同的划分,则\(ans(n)=\sum _{i=1}^n f(i,n)\),合并可以得到ans(i)=ans(0) * ans(n-1) + ans(1) * ans(n-2) + … + ans(n-1) * ans(0),边界ans(0)=ans(1)=1。
  • 139:给出词典,给出一个字符串,判断字符串是否可以完全由词典内的单词构成。设f[i]==true即前字符串前i位都可以完全由单词构成,则遍历每个单词,单词长度为k,若f[i-k]为真则f[i]为真,也可以转换为图用dfs做,i与j之间有一条边说明s[i:j]是一个单词,我们要找到一条路径从0到len(s)
  • 174:矩阵中有正数负数,在中途不为0的情况下求最小路径。动态规划,从后往前
  • 312:给出一个数列,问怎样依次消去数能得到最多硬币,得硬币的规则:消掉一个数得到这个数和相邻两个数累乘的数量的硬币。区间dp(分治),一段区间内能得到的最多硬币f[x,y]是看其最后一次消去位置在i,得到的硬币就是f[x,i-1]+num[i-1]*num[i]*num[i+1]+f[i+1,y],在这个区间内枚举位置i,其中需要左右两个小区间的位置已知,因此将区间从小到大枚举。总共三层循环:外循环区间长度,中循环区间在整个序列中的开始位置,内循环枚举区间内位置i。
  • 338:求出[1,num]内每个数字二进制中有多少个1,列举几个数分析发现对偶数n,它的二进制就是n/2的二进制左移一位,1的个数不变,对奇数n,它的二进制就是n/2的二进制左移一位并末尾加1,即1的个数多一个,显然状态转移方程 \[ f(x)= \begin{cases} f(n) & x=2n \\ f(n)+1 & x=2n+1 \\ \end{cases} \]
  • 397:一个数是偶数就除2,是奇数就变到相邻数,问最少几次变成1,根据题意可以写出状态转移方程: \[ f(x)= \begin{cases} f(n)+1 & x=2n \\ min(f(2n+2)+1,f(2n)+1) & x=2n+1 \\ \end{cases} \] 奇数情况可以化简为\(min(f(2n)+1,f(n+1)+2)\),这样就可以从1到n动规了,但是会超时 可以将方程进一步化简 If n % 4 = 3 and n != 3, then f(n) = f(n + 1) + 1. If n % 4 = 1 or n = 3, then f(n) = f(n - 1) + 1. 证明在这里
  • 472:是139的变式,依然是判断字符串是否可以由单词构成,但单词和要判断的字符串都在一个词典里,每个单词都需要判断是否完全能被其他单词组成。因为词典中无重复单词,所以先按单词长度排序,每个单词只能由它前面的单词构成,然后问题就转变成了139,第i个单词为要查询的字符串,前i-1个单词构成了查询所需的词典,一样的进行动态规划。top solution中利用了trie字典树加速,见Python中实现字典树

分治

  • 247:给出一个算式,无括号,问加括号的情况下有多少种可能的解(不要求去重),分治,取第i个运算符号,对符号左边和右边分别递归求解部分解,python中map的用法

Poj

  • C++源码
  • 1062:Dijkstra
  • 1068:模拟
  • 1094:拓扑排序
  • 1328:贪心,换求解变量
  • 1753:枚举,位运算
  • 1789:Prim,优先队列
  • 1860:bellman-ford
  • 2109:贪心,高精度乘法
  • 2965:枚举,位运算
  • 3259:建模,bellman-ford
  • 3295:模拟,栈

校内赛

  • 2017pre
  • A,集合中找有序三个数,满足和为0,求这些数平方和,Leetcode原题
  • D,求一个数的连续质数和分解,poj原题,数据大,因此没必要打表,直接对每一个输入判断
  • F,题目骗人,不需要回溯,递推公式可以写出特征方程求解
  • G,找一个集合中的最大子集,有绑定规则,选一个数必须选其他几个数,bfs
  • H,给出字符变换规则和代价,求把两个字符串变成一样的最小代价,flyod,注意两个字母可以变成第三个字母,不一定是互相变,两个字符串可能不等长,不等长直接输出-1
  • I,高中物理,求重力加速度,方程不好解,二分法逼近答案

hiho

  • hiho
  • 1505:给定一个组,问有多少种下标四元组(i, j, p, q)满足i, j, p, q两两不同,并且i < j, p < q, Ai + Aj = Ap + Aq。2sum问题,数据范围不大,直接开哈希数组,sum[i]记录两个数之和为i有多少组,利用容斥定理解。
  • 1506:投掷硬币,投n次m次朝上的概率是多少,每次投正面朝上概率不同。动态规划,记dp[i][j]为投前i次j次朝上的概率,状态转移方程为:dp[i][j]=dp[i-1][j-1]a[i]+dp[i-1][j](1.0-a[i]);a[i]为第i次正面朝上的概率,注意对j=0进行特判。
  • 1507:错误的记录,给出一棵树,给出根节点编号,在中间加一条错误边,找出所有可能的错误边。注意因为只加了一条错误边,因此情况可以分为两种:1.这条错误边连向根节点,直接输出。2.根节点正常,则这条错误边一定连在入度为2的节点上,且这样的节点只有一个,找到这个节点,将连接它的两条边分别去掉并从根节点开始dfs,如果dfs遍历完次数为n,说明这条边去掉后树依然成立,这是错误边,如果次数小于n,说明去掉这条边树就断了,形成森林,这条边不是错误边。注意边重复的情况,这时候只去掉其中一条,但是两条边是分别当错误边输出。因为错误边数小于等于2,所以dfs的次数小于等于2,加上构造去掉边的图,时间复杂度是O(n)。
  • 1515:给定一些同学之间的分数关系(A比B高或低多少分),最后对q个查询给出答案。带权并查集,每个集维护同学到这个集某一个根同学的分数差。每次输入一条关系便合并两个同学所在的并查集,并对每个并查集做一次更新,加入y被x合并,x,y之间关系值是s,更新公式是d[root of y]=d[x]-d[y]-s,并在下一次循环中更新整个并查集的值。最后直接查询。