- 这道题和49字符大小写排序那道题很一样，可以分别使用快排和归并排序
- 对于快排，要熟练掌握2路排序和3路排序，在后面的题中会用到。
- 整数ｋ不一定是数组中的元素
- 因为这道题并没有说完全按照
<k ,==k, >k的顺序，所以我们可以使用2路排序将其排列为<k, >=k的元素即可
- 概念问题,第ｋ大元素实际上是从小到大排的话，那就是第ｎ-k+1名元素了
- 快排求解，对于后面的逆序对用归并求解，这是常见的两个思路 3. 还有一个问题就是在partition后的partition的过程中，ｋ是不变的，不会变成k-p，因为partition传入的索引一直是原数组中的索引。
- 这道题要注意的是
partition需要严格分<1=1>1三种，因此需要三路排序 - 使用三个索引
lt,i,gt，使得[l,lt] <1 (lt+1,i)=1 [gt,r)>1.
- 遍历A中每个元素，然后二分法在B中查找与该元素最接近的元素。
- 在二分法查找的过程中，对于A[mid]元素要特别注意，当根据mid分区间的过程时，如果A[mid]!=该元素，那么就需要将smallest与mid这个元素与该元素差值进行比较更新，以防止在mid两边的区间中找不到该元素的情况。
- 因为这道题已经说数组有序了，所以我们在拿到第一个数之后，得到target-num，然后对剩下的数组进行二分查找，这样时间复杂度为O(nlogn)。
- 此题也可以那哈希表做，我们将每次的target-num放到map集合中，每次都搜寻一下，搜索到了自然就是最后的结果。
- 首先对数组按从小到大顺序排序，然后锁定两个数i,j之后，只需要考虑j之后的部分（因为数组有序，所以能与i和j组成0的已经在之前考虑过了。
- 在j之后进行二分法搜索确定第三个数
- 去重问题，题中要求不能重复，所以对于(a,b,c)这个三元组来说，若遍历到的i，j与前一个元素相等那么必定是重复的，跳过即可。
- 参考文献：两数和、三数和、四数和
- 这道题和上面那道挺像的，但是不需要去重了。
- 在二分搜索是我借鉴了387题最小差的思路。
- 目前时间复杂度是O(n^2logn)。
- 还是插入排序的思路，但是和数组不同的是，在链表中，因为我们不知道该元素的上一个元素指针，所以我们只能从前向后比较
- 注意边界问题，尤其是最开始的while循环
- 先对数组排序，然后从1到n-1个元素开始循环合并区间，这个过程中要注意不断更新end的值
- 由于是到n-1，所以第n个元素会无法正确比较，最后结果可能是一个空集，所以我们在对排序后的数组的最后加入一个（INT_MAX，INT_MAX）区间。
- 这里只需要给出一组结果即可。
- 依次遍历数组A，将从0到第i个数的和保存到B中并排序，这样任意B中两个元素相减都是A中的一个子数组和，进而寻找最接近0的。
- 这里我使用了插入排序
- 可以进行一下优化，比如对于swap来说，可以只进行一次，在while过程中找到那个没有排好序的索引，将之前的内容往后移，然后将最后一个元素插入到这里。
- 用排序是完全行得通的，只不过时间复杂度高了些
- 直接遍历数组然后统计每个颜色的种类，然后按序输出即可。
- 空间复杂度是O(K),需要优化
- 哈哈，这道题RTKLIB中也有用到在nextobsf函数中应该
- 思路很简单就是先对数组排序，然后如果相等就加进去，如果不等，就看看谁大谁小，把小的索引+1，大的索引不动。
- 注意去重。
- 就是归并排序的merge
- 可以优化（不会。。。）
- 最暴力的思路就是找出旋转基rotate，然后拷贝一个新数组，然后拷贝。
- 参考了别人的思路，旋转，从[0,rotate] 和 [rotata,n] 和 [0,n]旋转三次即可。
- 使用两个变量max和d，max保存的是到当前遍历的地方为止最大的子数组之和，对于d来说就是保存的从某个位置开始的子数组之和，当这个d小于0的时候，不管下一个数是正是负，这个d都会“拖累”下一个数，所以直接舍弃。
- 实际上这里的每一步的max都是到当前i为止的一个局部最大值。
- 利用41最大子数组中的第二点，前后遍历两次，分别将到i前后最大值分别存在两个数组中
- 对最后的结果进行一次遍历，找出最大值即可。
- 和41最大子数组思路完全一样。
- 和42最大子数组II思路一样
- 要注意不一定是左边数组最大而右边数组最小，结果可能在反过来的情况中，所以要都考虑到。
- 首先题目要求时间复杂度为o(logn)，因此还是适用二分法
- 由于题目中确保了至少存在了一个峰值，所以当
A[mid] < A[mid+1]时，我们就能得到在mid的右边是至少存在一个峰值的所以可以直接让数组向右走，反过来，让数组直接想左二分即可。
- 维持两个指针i，j,遍历j，每次当nums[j]!=nums[i]的时候，就表明遇到了一个新的不重复的num，此时赋值给nums[++i]即可。最后i+1就是数组的长度。
- 和上一题一样，只需加一个计数器即可。
- 对于两个字符串A{A0,A1,A2,...,Am},B{B0,B1,B2,...Bn},字符串Z{Z0,Z1,Z2,...,Zk}是他们的一个公共子序列，那么有：
- 如果Am=Bn,那么Zk=Am=Bn，而且Zk-1也是Am-1和Bn-1的一个LCS
- 如果Am!=Bn，那么Zk!=Am，则Zk是Am-1和Bn的一个LCS
- 如果Am!=Bn，那么Zk!=Bn，则Zk是Am和Bn-1的一个LCS
- 根据1可得到一个递推式：
- 题中要求时间复杂度为O(n)，那很容易想到我们需要一个工具来记录。
- 我们选择map来记录，当我们遇到一个数字时，首先判断在不在map中，若不在map中，那我们就看下这个数字-1 和 +1 在if不在，然后分别判断，若在，则说明之前已经记录过他们的长度，那我们跟着这个记录很容易回到这个序列的第一个和最后一个，更新记录即可。
- 直接用的归并排序的merge函数
- 这道题要求不占用额外空间，我见其他人都是直接两重循环做那样复杂度就是O(n2)，如果我先排序(onlogn)，然后在遍历一遍，这样最后是O(nlogn)。
- 维护两个索引i,j，让j一直遍历，只要不与target相同，就给num[i]赋值，i++，最后i的值就是新的数组的长度
- 最直观的做法就是对数组排序，然后遍历找出缺失的正整数即可，但是这样的时间复杂度就是o(nlogn)了。
- 参考CSDN上一个人的做法，首先要想明白因为是要找最小的正整数，所以我们只需要考虑0-size+1之间的即可，当有一个无穷大的正数时，那它必然占用了一个0-size之间的位置，所以我们遍历数组，将1-size之间的数放在该放的位置，1放在0，2放在1的位置，然后在遍历就能找出这个缺失的数了。
- 要注意重复情况比如[2,2,2,2]这种，处理不当可能会死循环。
- 从题中的图可以看出，数组是先增后减，所以那个最大值的地方就是我们分水岭，相对于左边来说，这个值就是右边的最大值，那我们就从0开始遍历到这个位置，每次都取一个最大值，代表了左边能接到雨水的最大值，依次累积。然后在从右往左遍历即可。
- 这道题和363.接雨水很像
- 数组左右维护两个指针i,j，要注意的是这里没有“墙壁”的厚度了，所以i,j能接的最大水容量就是min(arr[i],arr[j])*(j-i)，即便i,j之间有比arr[i]和arr[j]更大的“墙壁”也不碍事。
- 然后保存这个值，移动i,j(若左边的墙壁的高度小于右边的，就++i,否则就++j)。
- 和快排的partition操作类似
- 找出规律，递归即可
- 应该要有更简单的方法
- 这里最关键的应该是排序了，可以将数字变为字符串，然后遍历排序，也可以将他们互相颠倒顺序相加。
- 要注意数组中0的情况
- 很简单的思路就是算一下n个数每个数有几种排列，然后和k比较。
- 代码的第11行是因为在第20行可能会得出index=1，这种情况，如果没有k-=1这句话的话就会多算一种情况，把k-1，当k<n的时候仍然不会影响。
- 这个题一个前提假设就是每个人都在为自己争取最大的利益。
- 第一种解法:就是动态规划，实际上对于1个硬币，第一个人肯定赢，对于2两个硬币，第二个人也能赢，对于3个硬币呢，我们看1个硬币和2个硬币第一个人都能赢，这也就意味着当到3个硬币的时候，第一个人能拿走第一个硬币或者前两个硬币，不管是这两种那哪种情况，第二个人都可以一下全部收走，这样递推下去就行。
- 第二种思路参考CSDN上的，就是判断
n%3!=0就行，因为要想让第二个人赢，只有当剩3个硬币的时候第二个人才可以赢。
- 这道题最开始我一直想着从前向后做，可是这样发现，每次我想拿到第i个值的状态，他都和后面未拿到的值的状态有关，于是反过来思考。
- 因为是要拿到最大值，所以每个硬币第一个人都是有可能拿到的，所以我们这么想，当我们在第i个硬币的位置时，我们可以拿一个硬币，也可以拿两个硬币，当我们拿一个硬币时，第二个人可能拿一个，也可能拿两个，这道题实际上暗示了一个假设就是每个人都在为自己争取最大的利益，所以第二个人不管是拿一个还是拿两个，最终目的都是为了让自己利益最大，反过来也就是让第一个人利益最小，此时我们就有了一个状态转移方程：
式中dp[i+2]代表着第二个人拿了一个硬币，那我们就要从第i+2个硬币开始拿。
- 类比于上式，我们可以得到最终的状态转移方程:
- 最终我们求得的dp[0]就是第一个人能拿到的最大硬币值，让所有硬币值减去第一个人的就是第二个人拿到的，两个值比较就可得出输赢。
- 动态规划的简单应用。dp[i]表示到i个数字为止，最长上升子序列的长度，其动态转移方程为：
- 因为题目要求从右向左也是可以的，所以我们反过来再算一次，求出所有
dp[i]的最大值即可。
- 这道题和有一道动态规划很像，等找到了补上去
- 因为要求是连续子数组，所以我们从0开始依次累加，当我们的
sum<0时，这个i就是新的分割点，因为sum<0，所以我们不管加一个什么值都会比sum小，这时可以在拿max与sum比较更新索引。
- 因为要求是连续子数组，所以我们从0开始，每个元素我们加一次，然后更新最短距离就好。
- 还可以说当我们的子数组和大于target时，我们可以让left+1，让right以此向右，然后直到子数组和在此小于target时更新最短距离。
- 注意一点就是最后一位需要进位的情况。
- 两根指针
- 因为不能修改数组，所以不能使用排序
- 这道题用了很经典的二分法的思路我们只要把left和right当做是重复值的下上界限就能别有洞天。接着开展二分搜索中的搜索过程：mid取中值，那么nums中的数就被分成了
[left , mid - right]两端了。然后我们遍历一遍nums，统计所有<=mid的值count，如果count > right - left + 1，说明[ left - mid ]段的数字中存在重复（重复值为其区间的值），所以令right = mid。反之就是[ mid - right ]的数字，所以令left = mid + 1
- 我们把每一个结点指向反过来，最后最后一个结点就是头结点。
- 注意最后边界问题。
- 和上一题一样的思路，但是这里需要先找到前一个结点和后一个结点
- 注意head问题。
- 这道题我用的哈希表做的，只是简单统计即可。
- 对于链表来说，这里我们常常引入一个dummy结点，让
dumm->next = head作为哨兵结点，为什么？因为对于类似的head=node这样的赋值来说，是不能改变链表的走向的，我们只能说dummy->next=node才可以改变链表。 - 本来用的是快排的partition操作，可是题中要求不能改变相对顺序，于是加入两个头结点，从head开始遍，分别将小于k和大于k的指向两个结点，最后将两个结点汇总到一起。
- 快排，我尝试用快排做了，但是快排是平均复杂度是O(nlogn),所以按照最简单的快排来做的话，是出现LTE，就只能每次先随机选择一个数，但是链表不支持随机访问，这样会很复杂，就没有往下做。
- 第二种就是归并了，对于链表来说，归并好做，但是很多小细节要注意：
- 如何找中间节点，这里就是利用快慢节点关系，快结点每次走两个结点，慢节点每次走1个结点，这样相同的时间，当快结点到终点时，慢节点就恰好在中间节点的位置上，但是这里对偶数结点，最终是偏左还是偏右和代码的第71行的初值有关。
- 就是边界问题要考虑清楚。
题目： 给定一个单链表L:L0->L1->L2->...->Ln-1->Ln,重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2->... ,必须在不改变结点值的情况下进行原地操作。例如给出链表 1->2->3->4->null，重新排列后为1->4->2->3->null
分析：
- 因为不能改变结点值，且原地操作，所以我们首先想到先找到mid结点，然后将mid结点一直到end翻转一下，然后将这个新链表插入到前半个链表即可。
- 这里要注意
node = next和node->next = next的区别。
题目： 给定一个链表，判断它是否有环。
分析：
- 最直观的思路就是一直遍历下去，然后对每个结点标记，如果一旦遍历到标记过的结点，那就代表该链表有环。
- 另一种思路就是将这道题看做为追及问题，A和B分别以v和2v的速度在n米操场跑步，那么他们必然在n/v时第一次相遇。那我们就可以拿两个指针，一个每次走一个结点，一个走两个结点，这样一旦他们相等，则必然有环。
题目： 给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。例如：给出 -21->10->4->5, tail connects to node index 1，返回10。
分析：
- 首先利用102.带环链表的思路判断链表是否有环，然后将快慢指针分别保存下来。
- 我们假设链表长度为l，从起点到环的第一个结点共有m个结点，那当快慢指针第一次相遇时，我们假设所用时间为t，快指针一定比慢指针多跑了一圈，所用就有如下方程
所用此时慢指针已经跑了l-m个结点，也就是一个环，那我们再让他跑m个结点，就跑了l个结点，此时应该刚好回到环的开始，而m个结点的距离刚好又是从链表起点到环开始的距离，所用我们就在用一个start指针，让他们同时跑，最后相遇时，就是环的起始结点。
给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。返回一个深拷贝的链表.
- 第一次遍历的时候使用一个map（哈希表）来记录旧链表和新链表，然后在遍历一次即可。
合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。例如给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null.
- 直接两个两个mrge即可。
- 使用最小堆，首先将每个列表的头结点加入堆中，然后每次取出最小元素，然后将这个取出这个结点的下一个结点（如果不为NULL）加入到堆中，直到最后堆为空，结束循环。
题目： 给定一个排序链表，删除所有重复的元素每个元素只留下一个。例如给出 1->1->2->3->3->null，返回 1->2->3->null
分析：
- 这道题目很简单，我们只需要遍历一遍链表即可。
题目： 给定一个排序链表，删除所有重复的元素只留下原链表中没有重复的元素。例如：给出1->2->3->3->4->4->5->null，返回 1->2->5->null
分析：
- 遍历链表，我们在while循环在加一个while循环用来跳过重复元素，然后到一个新的元素后，我们判断他和后面的是不是相同，如果相同则继续进入while，如果不同，则加入到新的链表中去。
- 此题的一个需要注意的地方就是开头结点可能删去，所以我们加一个dummyhead结点，这也是链表题常用的做法。
题目： 将两个排序链表合并为一个新的排序链表。例如：给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。
分析：
- 和数组的归并排序中的merge操作是一样的，这里要简化的一步就是当某个链表走到头的时候，我们直接退出循环，将另外一个链表追加上即可。
题目： 找到单链表倒数第n个节点，保证链表中节点的最少数量为n。例如：给出链表 3->2->1->5->null和n = 2，返回倒数第二个节点的值1.
分析：
- 最直接的思路就是遍历求得链表长度，然后循环即可。
- 对于链表找结点，通常就是构造两个特殊的一快一慢指针，控制他们的速度，差距。对于本题来说，我们只需让快结点领先慢结点
n个结点，然后开始遍历，当快结点走到最后时，慢结点的位置就是要找的的结点。
题目： 假定用一个链表表示两个数，其中每个节点仅包含一个数字。假设这两个数的数字 相反 排列，请设计一种方法将两个数相加，并将其结果表现为链表的形式。例如：给给出两个链表 3->1->5->null和 5->9->2->null，返回 8->0->8->null
分析：
- 保存一个add变量用来记录每次相加后进位结果。
- 特别要注意的两种情况：
- 两个链表加完之后，仍需进位。
- 一个链表用完后，另一个链表还有数字。
题目： 假定用一个链表表示两个数，其中每个节点仅包含一个数字。假设这两个数的数字 顺序 排列，请设计一种方法将两个数相加，并将其结果表现为链表的形式。例如：给出 6->1->7 + 2->9->5。即，617 + 295。返回 9->1->2。即，912。
分析：
- 思路和上一题一样，但是首先要将链表反转，然后保存一个add变量用来记录每次相加后进位结果。
- 特别要注意的两种情况：
- 两个链表加完之后，仍需进位。
- 一个链表用完后，另一个链表还有数字。
题目： 给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数。例如：给出链表1->2->3->4->5->null和k=2,返回4->5->1->2->3->null.
分析：
- 首先确定链表长度，然后找到翻转点，反过来即可。
- 要注意的是：
- 当
k==0时 - 当
k>=length时
- 当
题目： 给定一个链表，删除链表中倒数第n个节点，返回链表的头节点。例如：给出链表1->2->3->4->5->null和 n = 2。删除倒数第二个节点之后，这个链表将变成1->2->3->5->null.
分析：
- 首先按照166. 链表倒数第n个节点的思路找到倒数第n+1个结点，然后让
n->next = n->next->next即可。 - 这里要注意当最后删除的结点是第一个结点的情况，为了让整个循环统一，我们可以用一个哨兵结点。
题目： 设计一种方式检查一个链表是否为回文链表。例如： 1->2->1 就是一个回文链表。
分析：
- 从中间结点将链表断开，将右边的链表反转，然后比较。
- 注意当链表长度是奇数时，我们从中间向右一个的结点断开，然后反转后开始比较，当右边链表结束时即可。
题目： 给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。例如：Linked list is 1->2->3->4, and given node 3, delete the node in place 1->2->4。
分析：
- 我们让这个结点变为下个结点的值，然后直接指向下下个结点就可以了。
题目： 请写一个程序，找到两个单链表最开始的交叉节点。
分析：
- 我们将两个链表连接在一起，如果链表交叉结点，那么新的链表必然有环。
- 最终问题转化为链表是否有环的问题。
题目： 给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。链表元素个数不是k的倍数，最后剩余的不用翻转。例如：给出链表 1->2->3->4->5 和k = 2, 返回2->1->4->3->5.
分析：
- 就是维护一个fast和slow指针，让fast领先slow指针n个节点，然后依次翻转，向前推进即可。
题目： 给一个链表，两两交换其中的节点，然后返回交换后的链表。例如：给出 1->2->3->4, 你应该返回的链表是 2->1->4->3。
分析：
- 遍历链表，两两交换
head和head->next即可，若剩余1个节点也无需考虑，因为我们交换两个节点并不改变链表的全局顺序。
题目： 删除链表中等于给定值val的所有节点。例如：出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。
分析：
- 注意当删除的元素是第一个节点时的情况。
题目： 计算链表中有多少个节点.例如：给出 1->3->5, 返回 3。
分析：
- 链表的简单遍历。
题目： 给你一个链表以及两个权值v1和v2，交换链表中权值为v1和v2的这两个节点。保证链表中节点权值各不相同，如果没有找到对应节点，那么什么也不用做。例如：给出链表1->2->3->4->null ，以及v1 = 2， v2 = 4，返回结果1->4->3->2->null。
分析：
- 分两种情况：
- 当两个结点相邻时
- 不相邻时
- 注意有结点在head的位置时，需要增加哨兵结点处理
题目： 给出一棵二叉树，返回其节点值的前序遍历。
分析：
- 递归
- 对于迭代遍历，我们可以自己先手动遍历下，会发现一个规律，其实前序遍历就是从根节点开始一直沿着左节点往下遍历，然后在从叶子节点向上遍历右节点，此时我们可以用一个栈，来保存从上而下遍历时的右子节点。
题目： 给出一棵二叉树，返回其节点值的中序遍历。
分析：
- 递归
- 和66. 二叉树的前序遍历思路一样，我们发现中序遍历是从左侧自底向上，所以我们仍然用一个栈来保存我们经历的各个节点，然后依次弹出。
将一个二叉查找树按照中序遍历转换成双向链表。
- 利用67. 二叉树的中序遍历的迭代版。
题目： 给出一棵二叉树，返回其节点值的后序遍历。 分析：
- 递归
- 和66. 二叉树的前序遍历思路一样，我们仍然是从左子数根部开始，但是此时我们需要加一个上次访问的结点，来判断根节点是否要加入，因为在到根节点时，如果根节点有右子数，但是我们循环如果不判断的话，是会死循环的。
题目： 在二叉树中寻找值最大的节点并返回。
分析：
- 递归, 可分别将三种非递归版本的遍历在实现一遍。
题目： 给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）。
分析：
- 递归(DFS)Binary Tree Level Order Traversal II。
- 队列(BFS)。只用一个队列，我们同样每次保存一个每一层最右边的节点，当到这个节点时我们就把
vector<int>加入到vector<vector<int>>。
题目： 给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）.
分析：
- 就是将69. 二叉树的层次遍历的答案reverse一下，还有其他方法么？
题目： 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的距离。
分析：
- 分治。
- 二叉树中常用的思想就是分治或者递归，实际上分治也利用了递归。
题目： 给定一个二叉树，找出其最小深度。二叉树的最小深度为根节点到最近叶子节点的距离。
分析：
- 递归。
题目： 翻转一棵二叉树。就是镜像对称。
分析：
- 递归。
- 非递归，使用栈。
题目： 深度复制一个二叉树。给定一个二叉树，返回一个他的克隆品。
分析：
- 递归。
- 因为二叉树的特殊结构，所以二叉树实现递归较多。
题目： 给定一个二叉树，找出所有路径中各节点相加总和等于给定目标值的路径。一个有效的路径，指的是从根节点到叶节点的路径。
分析：
- 递归。
题目： 给一棵二叉树，找出从根节点到叶子节点的所有路径。
分析：
- 递归,和376. 二叉树的路径和思路一样
题目： 将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说，用二叉树的right指针，来表示链表中的next指针。
分析：
- 递归,每次交换左右节点，将右节点放在左节点的最右子节点上，将最新的左节点放到右节点上。
题目： 给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。注意：假设给出的两个节点都在树中存在。
分析：
- 这道题可以这样想，既然要找最近公共祖先，那我不妨先在左子树中寻找，如果一旦在左子树中寻找，然后在右子树寻找，如果找到就返回。
- 但是有一种特殊情况就是两个节点分布在左右子树中，此时很明显他们的最近公共祖先就是root，所以当我们在左子树中寻找时，我们只要碰到一个结点，我们就返回这个节点，右子树也这样处理。
- 又因为两个节点是一定存在的，所以当我们右子树返回的
NULL（即右子树一个节点也没找到）那说明两个节点都在左子数中，那我们在左子树中碰到的第一个节点就是他们的最近公共祖先，同理右子树也是这样。 - 当左右子树分别返回一个节点时，那很显然他们的最近公共祖先就是root。
题目： 给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）.
分析：
- 思路和88. 最近公共祖先很一样首先我们还是用分治的思想来想这道题，要求最大路径，我们不妨先在左子树中求一下，然后在在右子树中求一下，当我们在左右子树都求出来后，很有可能答案就在这两个里面。
- 但是还有一种情况就是某条路径跨越了这个节点，此时我们就需要求一下从左节点开始的最大路径以及从右节点开始的最大路径，结构体中的singlepath既是这个，然后我们将这三种求最大值就是所要求的了。
题目： 有两个不同大小的二叉树：T1有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。
分析：
- 注意子树的概念。
- 递归。
题目： 给定一棵二叉查找树和一个新的树节点，将节点插入到树中。你需要保证该树仍然是一棵二叉查找树。
分析：
- 递归。
题目： 给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。
分析：
- 二叉搜索树的中序遍历就是升序.
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
- 节点的左子树中的值要严格小于该节点的值。
- 节点的右子树中的值要严格大于该节点的值。
- 左右子树也必须是二叉查找树。
- 一个节点的树也是二叉查找树。
- 我们可以中序遍历判断是否是递增的，注意我们不需要把每个结点的值都保存下来，我们只需要一个上一个遍历到的结点的值和这次根节点比较即可。
- 分治。
根据前序遍历和中序遍历树构造二叉树.
- 递归。
- 对于一个树前序[1 2 4 5 3 6 7]
中序[4 2 5 1 6 3 7]
首先我们根据中序的4在前序找到4的位置，根据前序的遍历顺序必然可知
[4 2 5]是左子树 [6 3 7]是右子数 中序遍历
它们对应的前序遍历分别是[2 4 5] [3 6 7]
依次递归即可。
根据中序遍历和后序遍历树构造二叉树
- 递归。和73. 前序遍历和中序遍历树构造二叉树思路一样。
设计实现一个带有下列属性的二叉查找树的迭代器：
- 元素按照递增的顺序被访问（比如中序遍历）
next()和hasNext()的询问操作要求均摊时间复杂度是O(1)
- 迭代版的中序遍历，参考68. 二叉树的后序遍历
给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。
- 首先要想到有序数组可以是BST的中序遍历，那么数组的中间节点就是根节点，左边是左子树，右边是右子数，迭代即可。
- 注意这里LintCode有一个bug就是当你的数组范围是[b,e)，即左开右闭取得mid时，LintCode会通不过，LeetCode没问题。
给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
- 和177. 把排序数组转换为高度最小的二叉搜索树一样的思路，每次寻找链表的中间节点作为根节点。
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
- 序列化这里就是采用题中的BFS算法，即层序遍历，69. 二叉树的层次遍历，空节点用
#表示，注意最后结点的空节点直接省略。在层序遍历中，我们要注意对空节点的处理。 - 反序列化中就是将
1反过来，所以还是要利用一个队列来做，这里要引入一个变量来说明当前是左子树还是右子数，每次在右子数时，就要注意弹出队列后面的结点，让该节点推到队前。 - 对于c++来说需要实现一个split的函数。
给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）
- 一个关键点就在于我如何知道我到了这一层的最后一个结点，我在这里用了一个私有的成员来表示最后一个结点，具体可以看代码注释。
给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。
给出二叉树 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A) 3 B) 3
/ \ \
9 20 20
/ \ / \
15 7 15 7
二叉树A是高度平衡的二叉树，但是B不是这里要注意的是我们写的函数不仅仅需要判断是否是平衡二叉树，还需要知道子树的高度，因为只有有了高度才能判断是否是平衡二叉树，所以我们就设计一个结构体，来保存这样的结果。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
struct ResultType{
bool isBalanced;
int depth;
ResultType(bool is, int d): isBalanced(is), depth(d){}
};
/*
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
bool isBalanced(TreeNode * root) {
// write your code here
// verson 1
// ResultType r = help(root);
// return r.isBalanced;
// verson2
return maxDepth(root) != -1;
}
ResultType help(TreeNode *root){
if(root == nullptr) return ResultType(true, 0);
ResultType r = help(root->right);
ResultType l = help(root->left) ;
if(!r.isBalanced || !l.isBalanced){
return ResultType(false, -1);
}
if(abs(r.depth - l.depth) > 1)
return ResultType(false, -1);
return ResultType(true, max(l.depth, r.depth) + 1);
}
int maxDepth(TreeNode *root){
if(root == nullptr) return 0;
int l = maxDepth(root->left);
int r = maxDepth(root->right);
if(l == -1 || r == -1 || abs(l - r) > 1) return -1;
else return max(l, r) + 1;
}
};线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:
- 根节点的
start和end由build方法所给出。 - 对于节点
A的左儿子，有start=A.left, end=(A.left + A.right) / 2。 - 对于节点
A的右儿子，有start=(A.left + A.right) / 2 + 1, end=A.right。 - 如果
start等于end`, 那么该节点是叶子节点，不再有左右儿子。
实现一个build方法，接受start和end作为参数, 然后构造一个代表区间[start, end]的线段树，返回这棵线段树的根。
- 递归。
对于一个有n个数的整数数组，在对应的线段树中, 根节点所代表的区间为0 - n-1, 每个节点有一个额外的属性max，值为该节点所代表的数组区间start到end内的最大值。
为SegmentTree设计一个query的方法，接受3个参数root, start和end，线段树root所代表的数组中子区间[start, end]内的最大值。
- 分治查询，只需要分清楚
mid和start和end的关系即可。
对于一个数组，我们可以对其建立一棵线段树, 每个结点存储一个额外的值count来代表这个结点所指代的数组区间内的元素个数. (数组中并不一定每个位置上都有元素)
实现一个query的方法，该方法接受三个参数root, start和end, 分别代表线段树的根节点和需要查询的区间，找到数组中在区间[start, end]内的元素个数
- 和202. 线段树的查询完全一样的思路，但是要注意的是这里既然要统计，就会出现查询范围比数组范围大，或者为
NULL的情况。 - 分治，只需要分清楚
mid和start和end的关系即可。
对于一棵 最大线段树, 每个节点包含一个额外的 max 属性，用于存储该节点所代表区间的最大值。
设计一个modify 的方法，接受三个参数 root、 index 和 value。该方法将 root 为根的线段树中 [start, end] = [index, index] 的节点修改为了新的 value ，并确保在修改后，线段树的每个节点的 max 属性仍然具有正确的值。
和202. 线段树的查询基本一样的思路，只需要在递归基的时候加一行赋值代码即可。
给定一个整数数组 （下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），以及一个 查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。
这道题实际上就是将线段树综合起来，可以在此重新写一遍线段树的构造，修改，查询。
给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 [start, end]。 对于每个查询，计算出数组中从下标 start 到 end 之间的数的最小值，并返回在结果列表中。
对于数组 [1,2,7,8,5]， 查询 [(1,2),(0,4),(2,4)]，返回 [2,1,5]
每次查询在O(logN)的时间内完成
利用线段树查询。
/**
* Definition of Interval:
* class Interval {
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* }
*/
struct SegmentNode{
public:
int start, end, min;
SegmentNode *left, *right;
SegmentNode(int start, int end, int min) {
this->start = start;
this->end = end;
this->min = min;
this->left = this->right = nullptr;
}
};
class Solution {
public:
/*
* @param A: An integer array
* @param queries: An query list
* @return: The result list
*/
vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
// write your code here
SegmentNode *root = build(0, A.size() - 1, A);
// for(int i = 0; i < A.size(); i++)
// insert(root, i, A[i]);
vector<int> r;
for(int i = 0; i < queries.size(); i++){
r.push_back(query(root, queries[i].start, queries[i].end));
}
return r;
}
private:
SegmentNode *build(int start, int end, const vector<int> &A){
if(start == end){
return new SegmentNode(start, end, A[start]);
}
SegmentNode *root = new SegmentNode(start, end, INT_MAX);
int mid = start + (end - start) / 2;
root->left = build(start, mid, A);
root->right= build(mid+1, end, A);
root->min = min(root->left->min, root->right->min);
return root;
}
int query(SegmentNode *root, int start, int end){
if(root == nullptr) return INT_MAX;
if(start < root->start) start = root->start;
if(end > root->end) end = root->end;
if(start == root->start && end == root->end){
return root->min;
}
int mid = root->start + (root->end - root->start) / 2;
int lmin = INT_MAX, rmin = INT_MAX;
if(start >= mid + 1){
rmin = query(root->right, start, end);
}
else if(end <= mid){
lmin = query(root->left, start, end);
}
else{
lmin = query(root->left, start, mid);
rmin = query(root->right,mid+1, end);
}
return min(lmin, rmin);
}
};
给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 [start, end] 。 对于每个查询，计算出数组中从下标 start 到 end 之间的数的总和，并返回在结果列表中。
对于数组 [1,2,7,8,5]，查询[(1,2),(0,4),(2,4)], 返回 [9,23,20]
每次查询在O(logN)的时间内完成
利用线段树。
/**
* Definition of Interval:
* classs Interval {
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
*/
struct SegmentNode{
int start, end;
long long count;
SegmentNode *left, *right;
SegmentNode(int start, int end, long long count = 0){
this->start = start;
this->end = end;
this->count = count;
this->left = nullptr;
this->right = nullptr;
}
};
class Solution {
public:
/*
* @param A: An integer list
* @param queries: An query list
* @return: The result list
*/
vector<long long> intervalSum(vector<int> &A, vector<Interval> &queries) {
// write your code here
SegmentNode *root = build(0, A.size() - 1, A);
vector<long long> r;
for(int i = 0; i < queries.size(); i++){
r.push_back(query(root, queries[i].start, queries[i].end));
}
return r;
}
private:
SegmentNode *build(int start, int end, const vector<int> &A){
if(start == end){
return new SegmentNode(start, end, A[start]);
}
SegmentNode *root = new SegmentNode(start, end);
int mid = start + (end - start) / 2;
root->left = build(start, mid, A);
root->right= build(mid+1, end, A);
root->count= root->left->count + root->right->count;
return root;
}
long long query(SegmentNode *root, int start, int end){
if(root == nullptr) return 0;
if(start < root->start) start = root->start;
if(end > root->end) end = root->end;
if(root->start == start && root->end == end){
return root->count;
}
long long l = 0, r = 0;
int mid = root->start + (root->end - root->start) / 2;
if(start > mid){
r = query(root->right, start, end);
}
else if(end <= mid){
l = query(root->left, start, end);
}
else{
l = query(root->left, start, mid);
r = query(root->right,mid+1, end);
}
return l+ r;
}
};
线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:
- 根节点的 start 和 end 由 build 方法所给出。
- 对于节点 A 的左儿子，有 start=A.left, end=(A.left + A.right) / 2。
- 对于节点 A 的右儿子，有 start=(A.left + A.right) / 2 + 1, end=A.right。
- 如果 start 等于 end, 那么该节点是叶子节点，不再有左右儿子。
- 对于给定数组设计一个build方法，构造出线段树
给出[3,2,1,4]，线段树将被这样构造
[0, 3] (max = 4)
/ \
[0, 1] (max = 3) [2, 3] (max = 4)
/ \ / \
[0, 0](max = 3) [1, 1](max = 2)[2, 2](max = 1) [3, 3] (max = 4)利用线段树。
/**
* Definition of SegmentTreeNode:
* class SegmentTreeNode {
* public:
* int start, end, max;
* SegmentTreeNode *left, *right;
* SegmentTreeNode(int start, int end, int max) {
* this->start = start;
* this->end = end;
* this->max = max;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/*
* @param A: a list of integer
* @return: The root of Segment Tree
*/
SegmentTreeNode * build(vector<int> &A) {
// write your code here
return build(0, A.size() - 1, A);
}
SegmentTreeNode *build(int start, int end, const vector<int> &A){
if(start > end){
return nullptr;
}
if(start == end){
return new SegmentTreeNode(start, end, A[start]);
}
SegmentTreeNode *root = new SegmentTreeNode(start, end, INT_MIN);
int mid = start + (end - start) / 2;
root->left = build(start, mid, A);
root->right= build(mid+1, end, A);
root->max = max(root->left->max, root->right->max);
return root;
}
};
在一条数轴上，有n个城市，编号从0 ~ n – 1 , 约翰打算在这n个城市做点生意，他对Armani的一批货物感兴趣，每个城市对于这批货物都有一个价格prices[i]。对于城市x,约翰可从城市编号为[x - k, x + k]购买货物，然后卖到城市x,问约翰在每个城市最多能赚到多少钱？
注意事项
prices.length 范围为[2, 100000], k <= 100000。给出 prices = [1, 3, 2, 1, 5], k = 2,返回 [0, 2, 1, 0, 4]。
解释：
i = 0，约翰可去的城市有0~2因为1、2号城市的价格比0号城市的价格高，所以赚不了钱，即 ans[0] = 0。
i = 1，可去的城市有0~3，可以从0号或者3号城市购买货物赚取的差价最大，即ans[1] = 2。
i = 2，可去的城市有0~4，显然从3号城市购买货物赚取的差价最大，即ans[2] = 1。
i = 3，可去的城市有1~4，没有其他城市的价格比3号城市价格低，所以赚不了钱，ans[3] = 0。
i = 4，可去的城市有2~4，从3号城市购买货物赚取的差价最大，即ans[4] = 4。给出 prices = [1, 1, 1, 1, 1], k = 1, 返回 [0, 0, 0, 0, 0]。
解释：
所有城市价格都一样，所以不能赚到钱，即所有的ans都为0。利用线段树。
struct SegmentNode{
int start, end;
int min;
SegmentNode *left, *right;
SegmentNode(int start, int end, int min){
this->start = start;
this->end = end;
this->min = min;
this->left = nullptr;
this->right= nullptr;
}
};
class Solution {
public:
/**
* @param A: The prices [i]
* @param k:
* @return: The ans array
*/
vector<int> business(vector<int> &A, int k) {
// Write your code here
SegmentNode *root = build(0, A.size()-1, A);
vector<int> r;
for(int i = 0; i <A.size(); i++){
int min_prices = query(root, i-k, i+k);
cout << min_prices << endl;
r.push_back(max(0, A[i] - min_prices));
}
return r;
}
private:
SegmentNode *build(int start, int end, const vector<int> &A){
if(start == end){
return new SegmentNode(start, end, A[start]);
}
SegmentNode *root = new SegmentNode(start, end, INT_MAX);
int mid = start + (end - start) / 2;
root->left = build(start, mid, A);
root->right= build(mid+1, end, A);
root->min = min(root->left->min, root->right->min);
return root;
}
int query(SegmentNode *root, int start, int end){
if(root == nullptr) return INT_MAX;
if(root->start == start && root->end == end){
return root->min;
}
if(start < root->start) start = root->start;
if(end > root->end) end = root->end;
int mid = root->start + (root->end - root->start) / 2;
int lmin = INT_MAX, rmin = INT_MAX;
if(start > mid){
rmin = query(root->right, start, end);
}
else if(end <= mid){
lmin = query(root->left, start, end);
}
else{
rmin = query(root->left, start, mid);
lmin = query(root->right, mid+1, end);
}
return min(lmin, rmin);
}
};
给定一个整数数组 （下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），以及一个 查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。
这道题实际上就是将线段树综合起来，可以在此重新写一遍线段树的构造，修改，查询。
如果一棵二叉树所有节点都有零个或两个子节点, 那么这棵树为满二叉树. 反过来说, 满二叉树中不存在只有一个子节点的节点.
- 分治。
给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。
基本思路二分法，二分法并不难，但是关键的地方在于当找不到元素的时候如何正确的返回比target大的最小值的元素。在循环过程中不断的向target逼近。
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。 如果目标值不在数组中，则返回[-1, -1]
- 和60搜索插入位置类似都是二分查找法
- 要注意的是对于重复元素，这样就只能用60搜索插入位置的版本1来做。
写出一个高效的算法来搜索 m × n矩阵中的值。这个矩阵具有以下特性：
- 每行中的整数从左到右是排序的。
- 每行的第一个数大于上一行的最后一个整数。
先对行首元素进行一次二分，找到插入位置60.搜索插入位置，然后对该行进行二分。
我们正在玩猜数游戏。 游戏如下：
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个号码。
每次你猜错了，我会告诉你这个数字是高还是低。
你调用一个预定义的接口 guess(int num)，它会返回 3 个可能的结果(-1，1或0):
二分法，注意这里不能按照往常使用[l,r)，可能会溢出。
实现 int sqrt(int x) 函数，计算并返回 x 的平方根
二分法，注意溢出。
- 基本思路仍是二分法，只是现在找出mid后，mid可能只有一边有序，另一边无序了，但是我们可以拿有序那边做判断，因为是有序，很容易判断出target在不在，如果不在就直接将范围缩小到另一端。
跟进62.搜索旋转排序数组，假如有重复元素又将如何？
是否会影响运行时间复杂度？
如何影响？
为何会影响？
写出一个函数判断给定的目标值是否出现在数组中。
代码同62搜索旋转排序数组一样
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。
你可以假设数组中不存在重复的元素。
- 二分法，思路和62.搜索旋转排序数组是一样的，我们主要来判断mid这个位置左右是不是均有序的。
- 关键是如何判断mid左右是否有序，我们直接和最左端和最右端的元素比较就行。
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。
数组中可能存在重复的元素。
- 二分法，思路和159. 寻找旋转排序数组中的最小值是一样的
- 唯一的不同在31行代码处，加入了去重。
给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且平均值最大。
给出 nums = [1, 12, -5, -6, 50, 3], k = 3
返回 15.667 // (-6 + 50 + 3) / 3 = 15.667
首先最后要找的平均值肯定在这个nums的最小值min和最大值max之间，所以我们是对min和max进行二分，然后每次取到一个mid，就看看这个数组里是否有这样的子数组的平均值大于这个mid，如果大于mid，那我们就在[mid, max]之间寻找，否则就在[min,mid]寻找。
然后我们如何在nums里查找是否有其子数组平均值大于mid，此时我们需要用一个新的数组num[nums.size() + 1]，然后我们让num[0]=0，然后我们遍历nums，每次都让num[i+1] = num[i] + nums[i] - mid，这样对于num数组的每个元素都代表了从索引0到当前索引的元素之和与mid的差值，同时num[i + 1]-num[j]代表了从i到j子数组的平均值，然后当我们遍历k个数之后，就开始判断这个差值，这个差值大于0的时候，就可以说有这么一个子数组符合条件。
代码的minaverage = min(minaverage, array[i + 2 - k]);是要找到当前位置k个数之前的所有子数组的平均值的最小值，这样我们那当前位置的num[i]减去这个最小值即为当前平均值的最大值。
正如标题所述，你需要使用两个栈来实现队列的一些操作。
队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。
pop和top方法都应该返回第一个元素的值。
我们只需要保存两个stack，用第二个栈来保存第一个栈的依次出栈元素即可。
给一个连续的数据流,写一个函数返回终止数字到达时的第一个唯一数字（包括终止数字）,如果在终止数字前无唯一数字或者找不到这个终止数字, 返回 -1.
给一个数据流 [1, 2, 2, 1, 3, 4, 4, 5, 6] 以及一个数字 5, 返回 3
给一个数据流 [1, 2, 2, 1, 3, 4, 4, 5, 6] 以及一个数字 7, 返回 -1
- 使用哈希做，我们只需要保存每个数字的出现顺序，直到出现target停止，然后再遍历数组，找到第一个出现一次的数字即可。
- 队列，暂未实现。
给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。
括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]"则是无效的括号。
- 栈的简单应用。
在经典的汉诺塔问题中，有 3 个塔和 N 个可用来堆砌成塔的不同大小的盘子。要求盘子必须按照从小到大的顺序从上往下堆 （如，任意一个盘子，其必须堆在比它大的盘子上面）。同时，你必须满足以下限制条件：
- 每次只能移动一个盘子。
- 每个盘子从堆的顶部被移动后，只能置放于下一个堆中。
- 每个盘子只能放在比它大的盘子上面。
请写一段程序，实现将第一个堆的盘子移动到最后一个堆中。
理解汉诺塔。
给定一个文档(Unix-style)的完全路径，请进行路径简化。
"/home/", => "/home"
"/a/./b/../../c/", => "/c"
- 你是否考虑了 路径 =
"/../"的情况？在这种情况下，你需返回"/"。 - 此外，路径中也可能包含双斜杠
'/'，如"/home//foo/"。在这种情况下，可忽略多余的斜杠，返回"/home/foo"。
这道题最难的部分在于考虑挑战部分提出的两条，另外还有一种情况就是当路径是"\"的情况，为了统一，我们均在路径后面追加"."，然后我们在循环的过程中，遇到了".." 或者 "."的时候，我们就首先判断栈是否是空，如果是空，我们就push一个"\"表示根节点，其余的路径名依次push到栈中。
给出一个表达式 s，此表达式包括数字，字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式)，请将这个表达式展开成一个字符串。
S = abc3[a] 返回 abcaaa
S = 3[abc] 返回 abcabcabc
S = 4[ac]dy 返回 acacacacdy
S = 3[2[ad]3[pf]]xyz 返回 adadpfpfpfadadpfpfpfadadpfpfpfxyz
你可以不通过递归的方式完成展开吗？
这里不用递归的话，可以考虑栈，当我们遇到']'的时候就可以pop，知道我们遇到'['，然后继续pop，拿到重复次数（这里有是两位或者三位数）。
实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。
你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。
如下操作：push(1)，pop()，push(2)，push(3)，min()， push(1)，min() 返回 1，2，1
要注意pop的情况，当栈pop的时候最小值可能会发生变化,所以我这里是在引入一个stack，每次push的时候，我都会判断一下这个值与之前最小值，然后把最小值push进去，同样，在pop的时候，两个栈同时都pop，也就是对于每个元素，新引入这个栈都会保存一个到当前元素为止最小的元素。
求逆波兰表达式的值。
在逆波兰表达法中，其有效的运算符号包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰计数表达。
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6按照逆波兰表达式顺序依次计算即可。
给你一个嵌套的列表，实现一个迭代器将其摊平。
一个列表的每个元素可能是整数或者一个列表。
给出列表 [[1,1],2,[1,1]]，经过迭代器之后返回 [1,1,2,1,1]。
给出列表 [1,[4,[6]]]，经过迭代器之后返回 [1,4,6]。
递归。
这部分的题目我们可以用STL中的priority_queue来做，或者自己写MinHeap来处理。
将 k 个排序数组合并为一个大的排序数组。
给出下面的 3 个排序数组：
[
[1, 3, 5, 7],
[2, 4, 6],
[0, 8, 9, 10, 11]
]合并后的大数组应为：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]在 O(N log k) 的时间复杂度内完成：
N是所有数组包含的整数个数。k是数组的个数。
和104.合并k个排序链表一样的思路。
在一个数组中找到前K大的数
给出 [3,10,1000,-99,4,100], k = 3.
返回 [1000, 100, 10]
可以用STL中的priority_queue来做，或者自己写MinHeap来处理。
给出一个整数数组，堆化操作就是把它变成一个最小堆数组。
对于堆数组A，A[0]是堆的根，并对于每个A[i]，A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子。
什么是堆？
- 堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。
什么是堆化？
- 把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素
A[i]，我们将得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]
如果有很多种堆化的结果？
- 返回其中任何一个。
给出 [3,2,1,4,5]，返回[1,2,3,4,5] 或者任何一个合法的堆数组
O(n)的时间复杂度完成堆化
这里要注意的是我们只需要从最后一个叶子节点的父亲节点开始依次进行shiftDown即可。
给一个单词列表，求出这个列表中出现频次最高的K个单词。
注意事项:
你需要按照单词的词频排序后输出，越高频的词排在越前面。如果两个单词出现的次数相同，则词典序小的排在前面。给出单词列表：
[
"yes", "lint", "code",
"yes", "code", "baby",
"you", "baby", "chrome",
"safari", "lint", "code",
"body", "lint", "code"
]如果 k = 3, 返回 ["code", "lint", "baby"]。
如果 k = 4, 返回 ["code", "lint", "baby", "yes"]。
用 O（n log k)的时间和 O(n)的额外空间完成。
如果你能够用 O(n) 的时间和O(k)的额外空间，那就更好不过了。
和544. 前K大数一样的思路，我们只需要自己定义一个比较函数即可。
实现一个数据结构，提供下面两个接口
add(number)添加一个元素topk()返回前K大的数
s = new Solution(3);
>> create a new data structure.
s.add(3)
s.add(10)
s.topk()
>> return [10, 3]
s.add(1000)
s.add(-99)
s.topk()
>> return [1000, 10, 3]
s.add(4)
s.topk()
>> return [1000, 10, 4]
s.add(100)
s.topk()
>> return [1000, 100, 10]
就是将heapify、shiftDown、shiftUp综合到一起。
给定一些 points 和一个 origin，从 points 中找到 k 个离 origin 最近的点。按照距离由小到大返回。如果两个点有相同距离，则按照x值来排序；若x值也相同，就再按照y值排序。
给出 points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
返回 [[1,1],[2,5],[4,4]]
和471. 最高频的K个单词一样的思路。
给一些movie（编号从0开始）的rating和他们的联系关系，联系关系可以传递(a和b有联系，b和c有联系，a和c也认为有联系)。给出每个movie的直接联系list。再给定一个movie编号为S，找到和S相联系的movie中的rating最高的K个movie（当与S相联系的movie少于K个时，输出所有。输出答案时可以按照任意次序，注意联系movie并不包括S。）
注意事项:
movie个数 n <= 20000。
保证编号为0 ~ n-1。（n为movie个数)。
保证联系的边，2个编号都属于0 ~ n-1。
保证总边数 m <= 100000。
保证每个movie的rating都为int范围内的整数，且互不相同。给出 ratingArray = [10,20,30,40], contactRelationship = [[1,3],[0,2],[1],[0]], S = 0, K = 2，返回[2,3]。
解释:
在contactRelationship中，0号与[1,3]有联系，1号与[0,2]有联系，2号与[1]有联系，3号与[0]有联系。
所以最终和0号movie相联系的有[1,2,3]，按他们的rating从高到低排列为[3,2,1]，所以输出[2,3]。这道题给的G可以作为图，我要找到与指定点直接连接或者间接连接的所有点，这里可以用DFS也可以使用BFS，然后再遍历图的过程中将所有的值加入优先队列中，最后取出前k个即可。
在一个排序矩阵中找从小到大的第 k 个整数。
排序矩阵的定义为：每一行递增，每一列也递增。
给出 k = 4 和一个排序矩阵：
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]返回 5。
使用O(k log n)的方法，n为矩阵的宽度和高度中的最大值。
？
实现一个 Trie，包含 insert, search, 和 startsWith 这三个方法。
注意事项
你可以假设所有的输入都是小写字母a-z。insert("lintcode")
search("code") // return false
startsWith("lint") // return true
startsWith("linterror") // return false
insert("linterror")
search("lintcode) // return true
startsWith("linterror") // return true
单词树的基本实现，参考字典树定义
设计一个包含下面两个操作的数据结构：addWord(word), search(word)
addWord(word)会在数据结构中添加一个单词。而search(word)则支持普通的单词查询或是只包含.和a-z的简易正则表达式的查询。
一个 . 可以代表一个任何的字母。
注意事项
你可以假设所有的输入都是小写字母a-z。addWord("bad")
addWord("dad")
addWord("mad")
search("pad") // return false
search("bad") // return true
search(".ad") // return true
search("b..") // return true
这里的关键是.的处理，这里可以直接递归搜索。
备注
字符串其他问题分别放在文中各个分类中
给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)
对于字符串 "abcdefg".
offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"在数组上原地旋转，使用O(1)的额外空间
涉及到字符串旋转的，我们可以分别在[1,offset],[offset+1,length],[1,length]进行三次reverse即可达到目的。
class Solution {
public:
/**
* @param str: An array of char
* @param offset: An integer
* @return: nothing
*/
void rotateString(string &str, int offset) {
// write your code here
if(str.size() == 0) return;
offset = str.size() - 1 - offset % str.size();
reverseString(str, 0, offset);
reverseString(str, offset+1, str.size()-1);
reverseString(str, 0, str.size()-1);
}
// reverse str[start, end]
void reverseString(string &str, int start, int end){
while(start < end){
swap(str[start++], str[end--]);
}
}
};给定一个字符串，逐个翻转字符串中的每个单词。
- 单词的构成：无空格字母构成一个单词
- 输入字符串是否包括前导或者尾随空格？可以包括，但是反转后的字符不能包括
- 如何处理两个单词间的多个空格？在反转字符串中间空格减少到只含一个
循环处理。
class Solution {
public:
/*
* @param s: A string
* @return: A string
*/
string reverseWords(string &s) {
// write your code here
vector<string> v;
int i = 0, j = 0;
while(i < s.size()){
for(j = i; j < s.size() && s[j] == ' '; j++) {}
for(i = j; j < s.size() && s[j] != ' '; j++) {}
if(i >= s.size()) break;
v.push_back(s.substr(i, j-i));
i = j + 1;
}
// while(i < s.size() && s[i++] == ' ') {}
// if(i < s.size()) v.push_back(s.substr(i));
ostringstream oss;
for(int i = v.size() - 1; i >= 0; i--){
oss << v[i];
if(i != 0) oss << ' ';
}
return oss.str();
}
};给定一个字符串， 包含大小写字母、空格' '，请返回其最后一个单词的长度。
如果不存在最后一个单词，请返回0 。
注意事项
一个单词的界定是，由字母组成，但不包含任何的空格。
给定 s = "Hello World"，返回 5。
和53. 翻转字符串思路一样
class Solution {
public:
/**
* @param s: A string
* @return: the length of last word
*/
int lengthOfLastWord(string &s) {
// write your code here
int len = 0, i = 0, j = 0;
while(i < s.size()){
while(i < s.size() && s[i] == ' ') i++;
if(i >= s.size()) break;
for(j = i; j < s.size() && s[j] != ' ' ; j++) {}
len = j - i;
i = j + 1;
}
return len;
}
};The words are same rotate words if rotate the word to the right by loop, and get another. Count how many different rotate word sets in dictionary.
E.g. picture and turepic are same rotate words.
注意事项
所有单词均为小写。
Given dict = ["picture", "turepic", "icturep", "word", "ordw", "lint"]
return 3.
"picture", "turepic", "icturep" are same ratote words.
"word", "ordw" are same too.
"lint" is the third word that different from the previous two words.
这里可以利用哈希表。
class Solution {
public:
/*
* @param words: A list of words
* @return: Return how many different rotate words
*/
int countRotateWords(vector<string> words) {
// Write your code here
set<string> s;
for(int i = 0; i < words.size(); i++){
bool contain = false;
for(int j = 0; j < words[i].size(); j++){
auto iter = s.find(words[i].substr(j+1)+words[i].substr(0, j+1));
if(iter != s.end()){
contain = true;
break;
}
}
if(!contain)
s.insert(words[i]);
}
return s.size();
}
};给定两个字符串，请设计一个方法来判定其中一个字符串是否为另一个字符串的置换。
置换的意思是，通过改变顺序可以使得两个字符串相等。
"abc" 为 "cba" 的置换。
"aabc" 不是 "abcc" 的置换。
因为均为英文字母，所以我们使用两个个char[128]数组，然后分别对字符串a、b进行遍历将对应字母的值加1，最后判断两个char数组是否相等。
class Solution {
public:
/**
* @param A: a string
* @param B: a string
* @return: a boolean
*/
bool Permutation(string &A, string &B) {
// write your code here
int a[256]{}, b[256]{};
for(int i = 0; i < A.size(); i++){
a[A[i]]++;
}
for(int i = 0; i < B.size(); i++){
b[B[i]]++;
}
for(int i = 0; i < 256; i++){
if(a[i] != b[i]) return false;
}
return true;
}
};给出两个字符串, 你需要修改第一个字符串，将所有与第二个字符串中相同的字符删除, 并且第二个字符串中不同的字符与第一个字符串的不同字符连接
给出 s1 = aacdb, s2 = gafd
返回 cbgf
给出 s1 = abcs, s2 = cxzca;
返回 bsxz
和211. 字符串置换思路一样，也是使用一个char[128]数组。
class Solution {
public:
/*
* @param : the 1st string
* @param : the 2nd string
* @return: uncommon characters of given strings
*/
string concatenetedString(string &s1, string &s2) {
// write your code here
int ch[256]{};
for(int i = 0; i < s2.size(); i++){
ch[s2[i]] = 1;
}
ostringstream oss;
for(int i = 0; i < s1.size(); i++){
if(!ch[s1[i]]){
oss << s1[i];
}
else{
ch[s1[i]] ++;
}
}
for(int i = 0; i < s2.size(); i++){
if(ch[s2[i]] < 2) oss << s2[i];
}
return oss.str();
}
};给一个词典，找出其中所有最长的单词。
在词典
{
"dog",
"google",
"facebook",
"internationalization",
"blabla"
}中, 最长的单词集合为 ["internationalization"]
在词典
{
"like",
"love",
"hate",
"yes"
}中，最长的单词集合为 ["like", "love", "hate"]
遍历两次的办法很容易想到，如果只遍历一次你有没有什么好办法？
遍历一遍即可，每次遇到更长的字符串就将此前存储的上个最长的字符串集合清空，重新添加。
class Solution {
public:
/*
* @param dictionary: an array of strings
* @return: an arraylist of strings
*/
vector<string> longestWords(vector<string> &dictionary) {
// write your code here
vector<string> v;
int max_length = 0;
for(int i = 0; i < dictionary.size(); i++){
if(dictionary[i].size() > max_length){
max_length = dictionary[i].size();
v.clear();
}
if(dictionary[i].size() == max_length)
v.push_back(dictionary[i]);
}
return v;
}
};设计一种方法，将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符，且你得到的是“真实的”字符长度。
你的程序还需要返回被替换后的字符串的长度。
在词典
对于字符串"Mr John Smith", 长度为 13
替换空格之后，参数中的字符串需要变为"Mr%20John%20Smith"，并且把新长度 17 作为结果返回。
在原字符串(字符数组)中完成替换，不适用额外空间
每次遇到空格，就将空格后的字母向后偏移2个位置，然后继续遍历。
class Solution {
public:
/*
* @param string: An array of Char
* @param length: The true length of the string
* @return: The true length of new string
*/
int replaceBlank(char string[], int length) {
// write your code here
for(int i = 0; i < length; i++){
if(string[i] == ' '){
length = offset(string, length, i+1, 2);
string[ i] = '%';
string[i+1] = '2';
string[i+2] = '0';
}
}
return length;
}
private:
int offset(char string[], int length, int start, int off){
for(int i = length - 1; i >= start; i--){
string[i + off] = string[i];
}
return length + off;
}
};判断一个正整数是不是回文数。
回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。
注意事项
给的数一定保证是32位正整数，但是反转之后的数就未必了。11, 121, 1, 12321 这些是回文数。
23, 32, 1232 这些不是回文数。
class Solution {
public:
/**
* @param num: a positive number
* @return: true if it's a palindrome or false
*/
bool isPalindrome(int num) {
// write your code here
string str = to_string(num);
int start = 0, end = str.size() -1;
while(start < end){
if(str[start++] != str[end--]) return false;
}
return true;
}
};给定两个二进制字符串，返回他们的和（用二进制表示）。
a = 11
b = 1
返回 100
和167.链表求和思路一样。
class Solution {
public:
/**
* @param a: a number
* @param b: a number
* @return: the result
*/
string addBinary(string &a, string &b) {
// write your code here
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
bool add_flag = false;
int i = 0;
ostringstream oss;
for(; i < a.size() && i < b.size(); i++){
int add = a[i] - '0' + b[i] - '0' + (add_flag ? 1 :0);
add_flag = add >= 2;
add = add % 2;
oss << add;
}
while(i < a.size()){
int add = a[i++] - '0' + (add_flag ? 1 :0);
add_flag = add >= 2;
add = add % 2;
oss << add;
}
while(i < b.size()){
int add = b[i++] - '0' + (add_flag ? 1 :0);
add_flag = add >= 2;
add = add % 2;
oss << add;
}
if(add_flag) oss << 1;
string str = oss.str();
reverse(str.begin(), str.end());
return str;
}
};给定一个字符串，判断其是否为一个回文串。只包含字母和数字，忽略大小写。
注意事项
你是否考虑过，字符串有可能是空字符串？这是面试过程中，面试官常常会问的问题。
在这个题目中，我们将空字符串判定为有效回文。"A man, a plan, a canal: Panama" 是一个回文。
"race a car" 不是一个回文。
O(n) 时间复杂度，且不占用额外空间。
前后两个指针遍历。
class Solution {
public:
/**
* @param s: A string
* @return: Whether the string is a valid palindrome
*/
bool isPalindrome(string &s) {
// write your code here
int begin = 0, end = s.size();
while(begin < end){
while(begin < s.size() && !isalnum(s[begin])){
begin++;
}
while(end >= 0 && !isalnum(s[end])){
end--;
}
if(tolower(s[begin++]) != tolower(s[end--])) return false;
}
return true;
}
};给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果
给一个字符串"123"
返回[["1","2","3"],["12","3"],["1","23"]]
回溯法。
class Solution {
public:
/*
* @param : a string to be split
* @return: all possible split string array
*/
vector<vector<string>> splitString(string& s) {
// write your code here
vector<string> v;
vector<vector<string>> r;
splitString(s, v, r, 0);
return r;
}
void splitString(string &s, vector<string> &v, vector<vector<string>> &r, int start){
if(start == s.size()) {
r.push_back(v);
return;
}
if(start < s.size()){
v.push_back(s.substr(start,1));
splitString(s,v,r, start+1);
v.pop_back();
}
if(start < s.size() - 1){
v.push_back(s.substr(start, 2));
splitString(s, v, r, start+2);
v.pop_back();
}
}
};给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。
给出字符串 "25525511135"，所有可能的IP地址为：
[
"255.255.11.135",
"255.255.111.35"
]回溯法。
class Solution {
public:
/**
* @param s: the IP string
* @return: All possible valid IP addresses
*/
vector<string> restoreIpAddresses(string &s) {
// write your code here
vector<string> v;
vector<string> r;
IpAddress(s, v, r, 0);
return r;
}
void IpAddress(string &s, vector<string> &v, vector<string> &r, int start){
if(start >= s.size()){
ostringstream oss;
if(v.size() == 4){
for(int j = 0; j < 4; j++){
if(j == 0) oss << v[j];
else oss << '.' << v[j];
}
r.push_back(oss.str());
}
return;
}
for(int i = start; i < start +3 && i < s.size(); i++){
string ip = s.substr(start, i - start + 1);
int num = stoi(ip);
if(num <= MAXIP){
v.push_back(ip);
IpAddress(s, v, r, i + 1);
v.pop_back();
}
if(num == 0) break;
}
}
private:
const int MAXIP = 255;
};给一个由 1 - n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。
注意事项
n <= 30给出 n = 20, str = 19201234567891011121314151618
丢失的数是 17 ，返回这个数。
因为n<30,所以我们只需要考虑1位数或者2位数即可。
class Solution {
public:
/*
* @param n: An integer
* @param str: a string with number from 1-n in random order and miss one number
* @return: An integer
*/
int findMissing2(int n, string &str) {
// write your code here
vector<bool> visited(n+1, false); //第一位不用
return findMissing2(n, str, 0, visited);
}
// n <= 30
int findMissing2(int n, string &str, int start, vector<bool> &visited){
if(start >= str.size()){
for(int i = 1; i <= n; i++){
if(!visited[i]) return i;
}
return -1;
}
if(str[start] == '0') return -1; // 数字划分失败
// 可能是一位数或者两位数
for(int i = start; i < start + 3 && i < str.size(); i++){
string s = str.substr(start, i-start+1);
int num = stoi(s);
if(num > 0 && num <= n && !visited[num]){ //[1,n]
visited[num] = true;
int miss = findMissing2(n, str, i+1, visited);
if(miss != -1) return miss;
visited[num] = false;
}
}
return -1; // must
}
};Given a digit string excluded 01, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
注意事项
以上的答案是按照词典编撰顺序进行输出的，不过，在做本题时，你也可以任意选择你喜欢的输出顺序。给定 "23"
返回 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
回溯法。
class Solution {
public:
/**
* @param digits: A digital string
* @return: all posible letter combinations
*/
vector<string> letterCombinations(string &digits) {
// write your code here
vector<string> v;
string tmp;
letter(digits, 0, tmp, v);
return v;
}
private:
void letter(string &digits, int start, string &str, vector<string> &v){
if(start == digits.size()){
if(str.size() != 0 && str.size() == digits.size())
v.push_back(str);
return;
}
for(int i = start; i < digits.size(); i++){
int index = digits[i] - '0';
if(index == 0 || index == 1) continue;
for(int j = 0; j < 4 && digit[index][j] ; j++){
string oldstr = str;
str += digit[index][j];
letter(digits, i+1, str, v);
str = oldstr;
}
}
}
const char digit[10][5] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
};给出一个单词表和一条去掉所有空格的句子，根据给出的单词表添加空格, 返回可以构成的句子的数量, 保证构成的句子中所有的单词都可以在单词表中找到.
注意事项
忽略大小写给一个字符串 CatMat, 给出字典 ["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"], 返回 3
我们可以构成一下 3 条语句: CatMat = Cat Mat CatMat = Ca tM at CatMat = C at Mat
我们首先将set集合中的全部转为小写，将待拆分的单词也转为小写。
class Solution {
public:
/*
* @param : A string
* @param : A set of word
* @return: the number of possible sentences.
*/
int wordBreak3(string& s, unordered_set<string>& dict) {
// Write your code here
unordered_set<string> _dict;
for(auto iter = dict.begin(); iter != dict.end(); iter++){
_dict.insert(tolower(*iter));
}
s = tolower(s);
vector<vector<string>> v;
vector<string> r;
wordBreak3(s, _dict, v, r, 0);
return v.size();
}
void wordBreak3(string &s, unordered_set<string> &dict,
vector<vector<string>> &v, vector<string> &r, int start){
if(start == s.size()){
v.push_back(r);
}
for(int i = start; i < s.size(); i++){
string word = s.substr(start, i - start + 1);
if(dict.find(word) != dict.end()){
r.push_back(word);
wordBreak3(s, dict, v, r, i+1);
r.pop_back();
}
}
}
string tolower(const string &str){
string lower = str;
transform(lower.begin(), lower.end(), lower.begin(), ::tolower);
return lower;
}
};给出一个候选数字的set(C)和目标数字(T),找到C中所有的组合，使找出的数字和为T。C中的数字可以无限制重复被选取。
例如,给出候选数组[2,3,6,7]和目标数字7，所求的解为：
[7]，
[2,2,3]
注意事项
1. 所有的数字(包括目标数字)均为正整数。
2. 元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
3. 解集不能包含重复的组合。 给出候选set[2,3,6,7]和目标数字7
返回 [[7],[2,2,3]]
回溯法
class Solution {
public:
/*
* @param candidates: A list of integers
* @param target: An integer
* @return: A list of lists of integers
*/
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
// write your code here
vector<vector<int>> res;
vector<int> r;
sort(candidates.begin(), candidates.end());
combinationSum(candidates, target, 0, r, res);
return res;
}
void combinationSum(const vector<int> &candidates, int target, int start,
vector<int> &r, vector<vector<int>> &res){
if(target == 0){
res.push_back(r);
return;
}
for(int i = start; i < candidates.size(); i++){
if(candidates[i] > target) break;
r.push_back(candidates[i]);
combinationSum(candidates, target - candidates[i], i, r, res);
r.pop_back();
}
}
};给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。
注意事项
1. 所有的数字(包括目标数字)均为正整数。
2. 元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
3. 解集不能包含重复的组合。 给出一个例子，候选数字集合为[10,1,6,7,2,1,5] 和目标数字 8 ,
解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]
- 回溯法
- 基本思路和代码都是和135.数字组合一样的，不同的地方在于要去重。
class Solution {
public:
/*
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
vector<vector<int>> combinationSum2(vector<int> &num, int target) {
// write your code here
vector<int> r;
vector<vector<int>> res;
sort(num.begin(), num.end());
combinationSum2(num, target, 0, r, res);
return res;
}
void combinationSum2(const vector<int> &num, int target, int start,
vector<int> &r, vector<vector<int>> &res){
if(target == 0){
res.push_back(r);
return;
}
for(int i = start; i < num.size(); i++){
//num中可能会有重复元素
if(i > start && num[i] == num[i-1]) continue;
if(num[i] > target) break;
r.push_back(num[i]);
combinationSum2(num, target-num[i], i+1, r, res);
r.pop_back(); //回溯
}
}
};组给出两个整数n和k，返回从1......n中选出的k个数的组合。
例如 n = 4 且 k = 2
返回的解为：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
- 和135.数字组合都是简单回溯法的应用
class Solution {
public:
/*
* @param n: Given the range of numbers
* @param k: Given the numbers of combinations
* @return: All the combinations of k numbers out of 1..n
*/
vector<vector<int>> combine(int n, int k) {
// write your code here
vector<vector<int>> res;
vector<int> r;
combine(n, k, 1, r, res);
return res;
}
void combine(int n, int k, int start,
vector<int> &r, vector<vector<int>> &res){
if(k == 0){
res.push_back(r);
return;
}
for(int i = start; i <= n; i++){
r.push_back(i);
combine(n, k-1, i+1, r, res);
r.pop_back();
}
}
};给出一个二维的字母板和一个单词，寻找字母板网格中是否存在这个单词。
单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。
给出
board =
[
"ABCE",
"SFCS",
"ADEE"
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.class Solution {
public:
/*
* @param board: A list of lists of character
* @param word: A string
* @return: A boolean
*/
bool exist(vector<vector<char>> &board, string &word) {
// write your code here
vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
if(board[i][j] == word[0]){
if(exist(board, word, visited, i, j, 0))
return true;
}
}
}
return false;
}
bool exist(vector<vector<char>> &board, string &word, vector<vector<bool>> &visited,
int x, int y, int start){
if(start >= word.size()){
return true;
}
if(x >= board.size() || x < 0
|| y < 0 || y >= board[0].size()
|| board[x][y] != word[start]
|| visited[x][y]){
return false;
}
// visited[x][y] = true;
// bool hor1 = false, hor2 = false, ver1 = false, ver2 = false;
// if (exist(board, word, visited, x, y-1, start+1)
// || exist(board, word, visited, x, y+1, start+1)
// || exist(board, word, visited, x-1, y, start+1)
// || exist(board, word, visited, x+1, y, start+1))
// return true;
// visited[x][y] = false; // 回溯
// return false;
// 上面这段代码会TLE
visited[x][y] = true;
bool hor1 = false, hor2 = false, ver1 = false, ver2 = false;
if (exist(board, word, visited, x, y-1, start+1)
|| exist(board, word, visited, x, y+1, start+1)
|| exist(board, word, visited, x-1, y, start+1)
|| exist(board, word, visited, x+1, y, start+1))
return true;
visited[x][y] = false; // 回溯
return false;
}
};给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
返回s所有可能的回文串分割方案。
给出 s = "aab"，返回
[
["aa", "b"],
["a", "a", "b"]
]class Solution {
public:
/*
* @param s: A string
* @return: A list of lists of string
*/
vector<vector<string>> partition(string &s) {
// write your code here
vector<string> v;
vector<vector<string>> r;
partition(s, v, r, 0);
return r;
}
private:
void partition(string &s, vector<string> &v, vector<vector<string>> &r,
int start){
if(start == s.size()){
r.push_back(v);
return;
}
for(int i = start; i < s.size(); i++){
string str = s.substr(start, i-start+1);
if(isPalindrome(str)){
v.push_back(str);
partition(s, v, r, i+1);
v.pop_back();
}
}
}
bool isPalindrome(const string &s){
for(int start = 0, end = s.size()-1; start < end; start++, end--){
if(s[start] != s[end])
return false;
}
return true;
}
};给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。
给定 n = 3, 可生成的组合如下:
"((()))", "(()())", "(())()", "()(())", "()()()"
回溯法
class Solution {
public:
/**
* @param n: n pairs
* @return: All combinations of well-formed parentheses
*/
vector<string> generateParenthesis(int n) {
// write your code here
if(n <= 0) return vector<string>();
vector<string> r;
string tmp;
helper(n, 0, 0, r, tmp);
return r;
}
void helper(int n, int left, int right, vector<string> &v, string &tmp){
if(left == n && right == n){
v.push_back(tmp);
return;
}
if(left < n){
string old_tmp = tmp;
tmp += '(';
helper(n, left+1, right, v, tmp);
tmp = old_tmp;
}
if(left > right && right < n){
string old_tmp = tmp;
tmp += ')';
helper(n, left, right+1, v, tmp);
tmp = old_tmp;
}
}
};给定一个含不同整数的集合，返回其所有的子集
注意事项
子集中的元素排列必须是非降序的，解集必须不包含重复的子集如果 S = [1,2,3]，有如下的解：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]请用非递归方法尝试解答这道题。
递归就不说了。对于非递归，可以用队列来做。
class Solution {
public:
/*
* @param nums: A set of numbers
* @return: A list of lists
*/
vector<vector<int>> subsets(vector<int> &nums) {
// write your code here
// 递归版
// vector<vector<int>> v;
// vector<int> r;
// subsets(nums, r, v, 0);
// return v;
// 非递归
sort(nums.begin(), nums.end());
queue<vector<int>> q;
vector<vector<int>> r;
q.push(vector<int>());
while(!q.empty()){
auto v = q.front();
q.pop();
r.push_back(v);
for(int i = v.size(); i < nums.size(); i++){
if(v.size() == 0 || v[v.size() - 1] < nums[i]){
v.push_back(nums[i]);
q.push(v);
v.pop_back();
}
}
}
return r;
}
void subsets(vector<int> &nums, vector<int> &r, vector<vector<int>> &v,
int start){
v.push_back(r);
for(int i = start; i < nums.size(); i++){
r.push_back(nums[i]);
subsets(nums, r, v, i+1);
r.pop_back();
}
}
};给定一个列表，该列表中的每个要素要么是个列表，要么是整数。将其变成一个只包含整数的简单列表。
注意事项
如果给定的列表中的要素本身也是一个列表，那么它也可以包含列表。给定 [1,2,[1,2]]，返回 [1,2,1,2]。
给定 [4,[3,[2,[1]]]]，返回 [4,3,2,1]。
请用非递归方法尝试解答这道题。
递归就不说了。对于非递归，可以用队列来做。
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Return true if this NestedInteger holds a single integer,
* // rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds,
* // if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Return the nested list that this NestedInteger holds,
* // if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
// @param nestedList a list of NestedInteger
// @return a list of integer
vector<int> flatten(vector<NestedInteger> &nestedList) {
// Write your code here
vector<int> r;
flatten(nestedList, r);
return r;
}
void flatten(const vector<NestedInteger> &list, vector<int> &r){
for(int i = 0; i < list.size(); i++){
if(!list[i].isInteger()){
flatten(list[i].getList(), r);
}
else{
r.push_back(list[i].getInteger());
}
}
}
};给定一个数字列表，返回其所有可能的排列。
注意事项
你可以假设没有重复数字。给出一个列表[1,2,3]，其全排列为：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]请用非递归方法尝试解答这道题。
递归就不说了。对于非递归，可以用队列来做。
class Solution {
public:
/*
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int>> permute(vector<int> &nums) {
// write your code here
// 递归版
// vector<vector<int>> r;
// vector<int> v;
// permute(nums, r, v);
// return r;
// 非递归版
vector<int> v;
vector<vector<int>> r;
queue<vector<int>> q;
q.push(v);
while(!q.empty()){
auto tmp = q.front();
q.pop();
if(tmp.size() == nums.size()){
r.push_back(tmp);
continue;
}
for(int i = 0; i < nums.size(); i++){
if(find(tmp.begin(), tmp.end(), nums[i]) == tmp.end()){
tmp.push_back(nums[i]);
q.push(tmp);
tmp.pop_back();
}
}
}
return r;
}
void permute(vector<int> &nums, vector<vector<int>> &r, vector<int> &v){
if(v.size() == nums.size()){
r.push_back(v);
return;
}
for(int i = 0; i < nums.size(); i++){
if(find(v.begin(), v.end(), nums[i]) != v.end())
continue;
v.push_back(nums[i]);
permute(nums, r, v);
v.pop_back();
}
}
};给出一个具有重复数字的列表，找出列表所有不同的排列。
给出一个列表[1,2,2]，其全排列为：
[
[1,2,2],
[2,1,2],
[2,2,1]
]请用非递归方法尝试解答这道题。
class Solution {
public:
/*
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int>> permute(vector<int> &nums) {
// write your code here
// 递归版
// vector<vector<int>> r;
// vector<int> v;
// permute(nums, r, v);
// return r;
// 非递归版
vector<int> v;
vector<vector<int>> r;
queue<vector<int>> q;
q.push(v);
while(!q.empty()){
auto tmp = q.front();
q.pop();
if(tmp.size() == nums.size()){
r.push_back(tmp);
continue;
}
for(int i = 0; i < nums.size(); i++){
if(find(tmp.begin(), tmp.end(), nums[i]) == tmp.end()){
tmp.push_back(nums[i]);
q.push(tmp);
tmp.pop_back();
}
}
}
return r;
}
void permute(vector<int> &nums, vector<vector<int>> &r, vector<int> &v){
if(v.size() == nums.size()){
r.push_back(v);
return;
}
for(int i = 0; i < nums.size(); i++){
if(find(v.begin(), v.end(), nums[i]) != v.end())
continue;
v.push_back(nums[i]);
permute(nums, r, v);
v.pop_back();
}
}
};- 坐标型动态规划
- 序列型动态规划
- 双序型动态规划
- 划分型动态规划
- 背包型动态规划
- 区间型动态规划
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
注意事项
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。比如，给出下列数字三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
坐标型动态规划
这道题放在第一个，是因为他是动态规划最好的入门题，首先我们可以考虑不使用动态规划，仅仅进行DFS遍历，但是我们会发现这样会超时，为什么，就是因为对三角形内部的节点我们重复遍历了，所以我们引入哈希表，我们将算过的节点保存在哈希表中，此时代码已经可以AC了，实际上到这时就已经是一种动态规划了，是一种带记忆搜索的动态规划。
然后我们在考虑使用常见的for循环的动态规划的写法。实际上这种方法又分为两种：自顶向下和自底向上。对于这两种在空间复杂度和时间复杂度是没有区别的。我们知道三角形内部的每个节点都取决于他上面的的两个节点（自顶向下）的值，所以根据这个我们可以写出代码。
在这里我把这几种代码都放出来，供大家参考。
class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int>> &triangle) {
// write your code here
dfs TLE
int best = INT_MAX;
dfs(triangle, 0, 0, 0, best);
return best;
}
void dfs(vector<vector<int>> &triangle, int x, int y, int sum, int &best){
if(x == triangle.size()){
best = min(best, sum);
return;
}
dfs(triangle, x+1, y, sum+triangle[x][y], best);
dfs(triangle, x+1, y+1,sum+triangle[x][y], best);
}
};
class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int>> &triangle) {
// write your code here
// divide TLE
return divide(triangle, 0, 0);
}
int divide(vector<vector<int>> &triangle, int x, int y){
if(x == triangle.size()){
return 0;
}
return triangle[x][y] + min(divide(triangle,x+1,y),
divide(triangle,x+1,y+1));
}
};class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int>> &triangle) {
// write your code here
// divide + hash
// 实际上这也是一中动态规划，带记忆搜索的
vector<vector<int>> hash = triangle;
for(int i = 0; i < hash.size(); i++){
for(int j = 0; j < hash[i].size(); j++){
hash[i][j] = INT_MAX;
}
}
return divide_hash(triangle, 0, 0, hash);
}
int divide_hash(vector<vector<int>> &triangle, int x, int y, vector<vector<int>> &hash){
if(x == triangle.size()) return 0;
if(hash[x][y] != INT_MAX)
return hash[x][y];
hash[x][y] = triangle[x][y] + min(divide_hash(triangle, x+1, y, hash),
divide_hash(triangle, x+1, y+1, hash));
return hash[x][y];
}
};class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int>> &triangle) {
// write your code here
// 动态规划 自底向上
int n = triangle.size();
vector<vector<int>> f = triangle; // 用triangle的size初始化f
for(int i = 0; i < f[n-1].size(); i++){
f[n-1][i] = triangle[n-1][i];
}
for(int i = n-2; i >= 0; i--){
for(int j = 0; j < triangle[i].size(); j++){
// 当前节点的值 只取决于跟他直接相连的两个节点
f[i][j] = triangle[i][j] + min(f[i+1][j], f[i+1][j+1]);
}
}
return f[0][0];
};class Solution {
public:
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
int minimumTotal(vector<vector<int>> &triangle) {
// write your code here
// 动态规划 自顶向下
int n = triangle.size();
vector<vector<int>> f = triangle; // 此时对于f来说，每行两端的元素已经与triangle的相同
for(int i = 1; i < n; i++){
// 初始化每行两端元素
f[i][0] += f[i-1][0];
f[i][f[i].size()-1] += f[i-1][f[i-1].size()-1];
}
for(int i = 1; i < n; i++){
for(int j = 1; j < f[i].size() -1; j++){
f[i][j] = triangle[i][j] + min(f[i-1][j-1], f[i-1][j]);
}
}
int minsum = INT_MAX;
for(int i = 0; i < f[n-1].size(); i++){
minsum = min(minsum, f[n-1][i]);
}
return minsum;
}
};给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。
注意事项
你在同一时间只能向下或者向右移动一步坐标型动态规划
状态方程：
dp[x][y]=min(dp[x-1][y],dp[x][y-1])+grid[x][y]
思考如果上下左右可以走，还可以使用动态规划么？
class Solution {
public:
/**
* @param grid: a list of lists of integers.
* @return: An integer, minimizes the sum of all numbers along its path
*/
int minPathSum(vector<vector<int> > &grid) {
// write your code here
// 也可以初始化一个新的dp[][]，然后初始化第一行第一列
int r = grid.size();
int c = grid[0].size();
for(int i = 0;i < r;i++){
for (int j = 0;j < c;j++){
if(i == 0 && j == 0) continue;
int left = i-1 < 0 ? INT_MAX : grid[i-1][j];
int up = j-1 < 0 ? INT_MAX : grid[i][j-1];
grid[i][j] += min(left,up);
}
}
return grid[r-1][c-1];
}
};有一个机器人的位于一个 m × n 个网格左上角。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
问有多少条不同的路径？
注意事项
n和m均不超过100给出 m = 3 和 n = 3, 返回 6.
给出 m = 4 和 n = 5, 返回 35.
坐标型动态规划
状态方程：
dp[x][y]=dp[x-1][y]+dp[x][y-1]
思考如果上下左右可以走，还可以使用动态规划么？
class Solution {
public:
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/
int uniquePaths(int m, int n) {
// wirte your code here
int dp[100][100];
for(int i = 0; i < 100; i++){
for(int j = 0; j < 100; j++){
dp[i][j] = 0;
}
}
dp[0][0]=1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i > 0){
dp[i][j] += dp[i-1][j];
}
if(j > 0){
dp[i][j] += dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};"不同的路径" 的跟进问题：
现在考虑网格中有障碍物，那样将会有多少条不同的路径？
网格中的障碍和空位置分别用 1 和 0 来表示。
注意事项
n和m均不超过100如下所示在3x3的网格中有一个障碍物：
[
[0,0,0],
[0,1,0],
[0,0,0]
]一共有2条不同的路径从左上角到右下角。
坐标型动态规划
思考如果上下左右可以走，还可以使用动态规划么？
class Solution {
public:
/**
* @param obstacleGrid: A list of lists of integers
* @return: An integer
*/
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
// write your code here
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
int dp[100][100];
for(int i = 0; i < 100; i++){
for(int j = 0; j < 100; j++)
dp[i][j] = 0;
}
dp[0][0] = 1;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if (obstacleGrid[i][j] == 1)
dp[i][j] = 0;
else{
if(i > 0)
dp[i][j] += dp[i-1][j];
if (j > 0)
dp[i][j] += dp[i][j-1];
}
}
}
return dp[row-1][col-1];
}
};假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法
返回 3
坐标型动态规划
斐波那契数列
class Solution {
public:
/**
* @param n: An integer
* @return: An integer
*/
int climbStairs(int n) {
// write your code here
int a = 1,b = 1;
int j = 0;
while(j++ < n){
a = a + b;
b = a - b;
}
return b;
}
};给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置
注意事项
这个问题有两个方法，一个是贪心和 动态规划。
贪心方法时间复杂度为O（N）。
动态规划方法的时间复杂度为为O（n^2）。
我们手动设置小型数据集，使大家可以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。A = [2,3,1,1,4]，返回 true.
A = [3,2,1,0,4]，返回 false.
坐标型动态规划
目前用的动态规划，能否跳到最后一个位置也就是dp[n]是否为true，取决于dp[n-1],dp[n-2],...,dp[1]他们是否能跳到，如果能跳到他们的位置，那他们能否跳到最后一个位置，所以我们需要一个dp[n]来保存这些状态
class Solution {
public:
/*
* @param A: A list of integers
* @return: A boolean
*/
bool canJump(vector<int> &A) {
// write your code here
int size = A.size();
bool dp[A.size()];
dp[0] = true;
for(int i = 1; i < size; i++){
dp[i] = false;
for(int j = 0; j < i; j++){
if(dp[j] && A[j] >= i-j){
dp[i] = true;
break;
}
}
}
return dp[size-1];
}
};给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
给出数组A = [2,3,1,1,4]，最少到达数组最后一个位置的跳跃次数是2(从数组下标0跳一步到数组下标1，然后跳3步到数组的最后一个位置，一共跳跃2次)
坐标型动态规划
和116.跳跃游戏一样的思路，就是需要两个状态，一个保存是否可以跳到，一个保存最少步数，这里利用INT_MAX将这两种状态合并为一个。
class Solution {
public:
/*
* @param A: A list of integers
* @return: A boolean
*/
bool canJump(vector<int> &A) {
// write your code here
int size = A.size();
bool dp[A.size()];
dp[0] = true;
for(int i = 1; i < size; i++){
dp[i] = false;
for(int j = 0; j < i; j++){
if(dp[j] && A[j] >= i-j){
dp[i] = true;
break;
}
}
}
return dp[size-1];
}
};给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。
最长上升子序列的定义：最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。WIKI百科
给出 [5,4,1,2,3]，LIS 是 [1,2,3]，返回 3
给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4
- 动态规划。
- 二分法，实际上就是在循环的过程中我们用到了二分法。这种方法有点类似于贪心，就是我们每次选一个数，让这个数刚刚数组的前一个数，这样可以为后面的数留出更多选择余地，如何选择这个数？就是60.搜索插入位置的思路，我们搜索插入位置，然后将这个位置的数替换掉。
class Solution {
public:
/*
* @param nums: An integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> &nums) {
// write your code here
// binarySearch
// if(nums.size() == 0) return 0;
// int len = 1;
// vector<int> lis(nums.size());
// lis[0] = nums[0];
// for(int i = 1; i < nums.size(); i++){
// if(nums[i] > lis[len - 1]){
// lis[len++] = nums[i];
// }
// else{
// // 这里要保证当前这个位置的数尽可能小
// // 这样后面才能有更多的选择“余地”
// int pos = binarySearch(lis, 0, len, nums[i]);
// lis[pos] = nums[i];
// }
// }
// return len;
//dp
if(nums.size() == 0) return 0;
int dp[nums.size()];
for(int i = 0; i < nums.size(); i++)
dp[i] = 1;
int lci = 1;
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
lci = max(lci, dp[i]);
}
return lci;
}
private:
// for binarySearch
// nums[start, end)
int binarySearch(const vector<int> &nums, int start, int end, int target){
while(start < end){
int mid = start + (end - start) / 2;
if(target <= nums[mid])
end = mid;
else
start = mid + 1;
}
return start;
}
};给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
给出
s = "lintcode"
dict = ["lint","code"]
返回 true 因为"lintcode"可以被空格切分成"lint code"
- 假设在第i个字母，此时判断是否能从这个字母前面切断，那我们就要从0-i依次寻找可以切断并且j-i这个子字符串也在字典中，这样就可以切断，否则就不可以。
class Solution {
public:
/*
* @param s: A string
* @param dict: A dictionary of words dict
* @return: A boolean
*/
bool wordBreak(string &s, unordered_set<string> &dict) {
// write your code here
// 优化前
// 这样时间复杂度是O(n3),会LTE
// 考虑到字典中最大单词长度，从后向前寻找。
// 当切分的单词长度大于最大长度时，中断循环
int length = s.size(), maxlength = 0;
for(auto iter = dict.begin(); iter != dict.end(); iter++){
maxlength = max<int>(maxlength, (*iter).size());
}
//dp[i] 表示前i个字符是否可以分割
bool dp[length+1];
dp[0] = true; //空字符串必然可以切分
for(int i = 1; i <= s.size(); i++){
dp[i] = false;
for(int j = i; j >= 1; j--){
int subsize = i - j + 1;
if(subsize > maxlength) break;
string substr = s.substr(j-1, subsize);
if(dp[j-1] && dict.find(substr) != dict.end()){
dp[i] = true;
break;
}
}
}
return dp[length];
}
};给定一个字符串s，将s分割成一些子串，使每个子串都是回文。
返回s符合要求的的最少分割次数。
比如，给出字符串s = "aab"，
返回 1， 因为进行一次分割可以将字符串s分割成["aa","b"]这样两个回文子串
和107. 单词拆分 I一样的思路，这里只是将字典换为了是否为回文串，另外要求的是最小的切分数，所以这里的dp[i]的含义就是前i个字符串最少切分数，之所以让dp[0]=-1是因为如果整个字符串刚好是个回文串，那么dp[i]+1刚好是0
class Solution {
public:
/**
* @param s: A string
* @return: An integer
*/
int minCut(string &s) {
// write your code here
int length = s.size();
int dp[length+1]{};
dp[0] = -1;
for(int i = 1; i <= s.size(); i++){
int __min = i-1;
for(int j = 1; j <= i; j++){
bool can = ispalinrome(s, j-1, i-1);
if(can)
__min = min(__min, dp[j-1]+1);
}
dp[i] = __min;
}
return dp[length];
}
private:
bool ispalinrome(string &s, int start, int end){
while(start < end){
if(s[start++] != s[end--]) return false;
}
return true;
}
};