ButterFlyEffect

题解

/ 注册

全部文章 / 题解（共6篇）

深度遍历

深度遍历，由于是图。所以我们需要用一个map维持clone过的节点，以及对应的新节点。遇到的时候直接赋值，避免再次陷入clone流程中。递归最简单。 /** * Definition for undirected graph. * struct UndirectedGraphNode { * ...

深度遍历简单题

2020-11-08

0 656

时间复杂度O(n)的非典型题解

本题第一时间想到的解法就是排序，但是这样不符合O(n)的时间复杂度要求。另外一种思路就是用一个set记录每个元素的位置，然后遍历数组的元素，对每个元素做向上向下的遍历，统计连续的长度。几个点：1 普通的set查找是O(logN)的，改成hash set就可以认为是O(1)的了。2 在之前序列统计过的...

贪心子集问题连续子区间问题

2020-11-08

0 708

O(n)的解法

看了一些题解都是hash或者排序、划分的解法，时间和空间复杂度都不满足要求。这里给一个时间复杂度O(n),空间复杂度O(1)的解法。其实这个题目不太严谨，本质上是一个简单的数学问题。应该再加上一个条件：加上这个缺失的最小整数后，它是一个连续数组（不包括0）。不知道是不是以为这个原因，很多朋友没有这么...

趣味问题简单题

2020-10-29

21 2428

动态规划

又是一个求连续区间数组的问题，典型的动态规划问题。和求最大区间和不同的是，如果我们依然尝试用dp[i]表示以a[i]结尾的子区间的最大成绩。会发现由于负数的存在，会导致乘法结果反转。dp[i-1]a[i]反倒变成了最小值，无法得到状态转移方程。沿着乘法的特性看，如果a[i]为负数，那么dpa[i]时...

动态规划连续子区间问题

2020-10-27

17 1021

回溯+递归

递归+回溯直接搞定题目要求需要升序排列，所以提前将S sort一下就可以了。从0开始，每个位置都从之后的所有位置开始新一轮的选择。 class Solution { public: vector<vector<int> > vres; vector<ve...

递归子集问题回溯深度遍历递归回溯

2020-10-26

11 1344

非典型性题解

暴力求解法开始时想到了暴力求解法，最差情况下是O(nn)的时间复杂度，很不幸，超时了。但至少在面试的时候，可以在有限的时间内给出一个基本解法，思路是这样的：1 在数组arr(left, right)中找出最大和第二大的数的位置pos1和pos2；这样就将arr划分成了3段： left,..., ...

双指针二分法

2020-10-20

16 1290