3. Max Points on a Line 共线点个数3种解法
思路一：思考如何确定一条直线，两点法，确定斜率后带入一点。有三种情况，1. 两点重合，2. 斜率不存在，3. 正常算，依次以每个点为过直线的点，map映射斜率个数。
思路二：后两种情况合并，用(dy/d, dx/d)表示，其中d=gcd(dx, dy)，这样避免了除法的精度损失
思路三：暴力O(n^3)的解法，枚举任意一条直线，判断三点共线三角形面积法（1/2*ABxAC==0）叉积为零(行列式为0)
4. O(nlogn)链表排序
思路一：归并排序(注意要做截断处理前一半的末尾赋值为NULL，奇数偶数都考虑可以避免找中间结点的错误，if(two&&two->next))
思路二：快速排序
class Solution {
public:
ListNode* sortList(ListNode* head) {
quicksort(head,NULL);
return head;
}
void quicksort(ListNode* head, ListNode* end)
{
if(head!=end)
{
ListNode* partion = partition(head,end);
quicksort(head, partion);
quicksort(partion->next,end);
}
}
ListNode* partition(ListNode* head, ListNode* end)
{
ListNode* slow = head;
ListNode* fast = head->next;
while(fast!=end)
{
if(fast->val<head->val)
{
slow = slow->next;
swap(fast->val,slow->val);
}
fast = fast->next;
}
swap(slow->val,head->val);
return slow;
}
};
6 后序遍历非递归
思路一：标记变量法，判断是否为遍历完右子树返回。
要点：标记变量mark，初始化为NULL。后序从右子树返回则mark = root，从左子树返回的，还要重新入栈，注意两个循环的条件都是栈不为空。
思路二： 判断法
入栈顺序根节点，右儿子，左儿子。这样出栈顺序就是后序的顺序，判断条件一定要注意pre!=NULL一定不能忘记写，如果忘记了，pre==NULL时有一个子树为空也满足条件就错了。
if((cur->left==NULL&&cur->right==NULL)||(pre!=NULL&&(cur->left==pre||cur->right==pre)))
一种情况如果左右子树为空，那么直接记录答案并更新pre；另一种情况，如果当前pre不为空并且表示从任意一个子树返回，那么也是正确的后序返回顺序。为什么从左子树返回也是正确的，因为按照左右中的顺序出栈，那么到当前点，pre==cur->left，表明右子树为空。
思路三：左右子树入栈顺序改变的先序遍历+reverse
栈来操作，先：中左右->后：左右中，先反转：右左中，将左右子树入栈顺序调换即可
8. reorder-list.
L: L0→L1→…→Ln-1→Ln, 变成这样：L0→Ln →L1→Ln-1→L2→Ln-2→… 思路，快慢指针找中点，找到后尾串反转(双指针法，或头插[第二个放前面，第三个放前面..])，两个链表合并。
11. word-break-ii:
枚举所有情况的题，多半是dfs，但如果不用记忆数组做减少重复计算的优化，那么递归方法跟brute force没有区别，所以要避免重复计算。或用dp搞。
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_map<string, vector<string>> m;
return helper(s,wordDict,m);
}
vector<string> helper(string s, vector<string> & dict, unordered_map<string, vector<string>>& m)
{
if(m.count(s))return m[s]; //记忆化搜索
if(s.empty())return {""}; //递归出口
vector<string> res;
for(string word:dict)
{
if(s.substr(,word.size())!=word)continue;
vector<string> remember = helper(s.substr(word.size()),dict,m);
for(string str:remember)
{
res.push_back(word + (str.empty()?"":" ")+str);
}
}
return m[s]=res;
}
single-number-ii
思路：转自菜鸟葫芦娃
Single Number的本质，就是用一个数记录每个bit出现的次数，如果一个bit出现两次就归0，这种运算采用二进制底下的位操作^是很自然的。Single Number II中，如果能定义三进制底下的某种位操作，也可以达到相同的效果，Single Number II中想要记录每个bit出现的次数，一个数搞不定就加两个数，用ones来记录只出现过一次的bits，用twos来记录只出现过两次的bits，ones&twos实际上就记录了出现过三次的bits，这时候我们来模拟进行出现3次就抵消为0的操作，抹去ones和twos中都为1的bits
int singleNumber(int A[], int n) {
int ones = ; // 记录只出现一次的bits
int twos = ; // 记录只出现二次的bits
int threes;
for(int i=;i<n;i++)
{
int t=A[i];
twos |= ones&t; // 要在更新ones之前更新twos
ones ^=t;
threes = ones&twos;// ones和twos中都为1即出现3次
ones &= ~threes;//抹去出现3次的bits
twos &= ~threes;
}
return ones;
}
Integer break
思路一：O(n^2)的dp，注意拆分的时候，可以不拆分包含自己
1 dp[]=;
dp[]=;
for(int i=;i<=n;i++)
{
for(int j=;j<i;j++)
{
dp[i] = max(max(dp[j],j)*max(dp[i-j],i-j),dp[i]);// 注意这里
}
}
return dp[n];
思路二：O(n)的dp，和台阶题类似，在n >3的情况下，处理一个数要么拆分成2，要么拆分成3，（4的话相当于2个2 ， 拆成1的话乘积太小了）
dp[] =
dp[] =
for(int i=;i<=n;i++)
dp[i] = max(dp[i - ] * , dp[i - ] * )
return dp[n]
思路三：
拆成3的比拆成2的乘积大。 比如6的时候 2*2*2 < 3*3
希望能尽可能的拆成3，然后才是2.
所以，如果
- n % 3 == 0: 那么全部拆成3
- n % 3 == 1: 2个2剩下的为3 4*3^(x-1) > 1*3^x
- n % 3 == 2: 1个2剩下的为3
16 candy
要求每个小朋友至少分一个，rating高的比邻居分的多
思路：分两步，从左到右，从右到左。从右到左时注意，如果此时dp[i]>dp[i+1]则continue，没必要加了，别无脑加1！
18 clone-graph
类比任意指针的链表深拷贝
思路：dfs或bfs遍历复制，用map记录以及visited处理
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
unordered_map<int, UndirectedGraphNode *> umap;
return clone(node,umap);
}
UndirectedGraphNode * clone(UndirectedGraphNode* node,unordered_map<int, UndirectedGraphNode *> & umap)
{
if(!node)return node;
if(umap.count(node->label))return umap[node->label];
UndirectedGraphNode* newNode = new UndirectedGraphNode(node->label);
umap[node->label]=newNode;
for(int i=;i<node->neighbors.size();i++)
{
newNode->neighbors.push_back(clone(node->neighbors[i],umap));
}
return newNode;
}
};
25 word ladder
一次只能变一个字母，且中间状态必须在dict中存在，可能有很多中间状态，求最小转换次数，最小的搜索方式就是bfs
思路：从第一个字母开始改，26个字母分别试，用一个map记录是否访问过以及到这个状态所需的次数。
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
unordered_map<string,int> pathCnt{{{start,}}};
queue<string> q{{start}};
while(q.size())
{
string word = q.front();q.pop();
for(int i=;i<word.size();i++)
{
string newWord = word;
for(char ch = 'a';ch<='z';ch++)
{
newWord[i] = ch;
if(newWord==end)return pathCnt[word]+;
if(dict.count(newWord)&&!pathCnt.count(newWord))
{
q.push(newWord);
pathCnt[newWord]=pathCnt[word]+;
}
}
}
}
return ;
}
};
*27 binary-tree-maximum-path-sum
这题之前做过，现在又不会了orz。类似一维数组最大和问题，换到了二叉树上，起点终点在任意结点，可能有负数。
考察递归和树的dfs很好的一道题。
/ \ / \
试一个例子自己找一下递归的解法
对于每个结点来说，我们要知道经过其左子结点的path之和大还是经过右子节点的path之和大。那么递归函数返回值就可以定义为以当前结点为根结点，到叶节点的最大路径之和，然后全局路径最大值放在参数中，用引用res来表示。
1. 用res记录答案
2. 递归函数始终返回以当前结点为终点的最大路径和
每次递归中，左子结点为终点的最大path和加上以右子结点为终点的最大path和，再加上当前结点值就组成了一条完整的路径。
class Solution {
public:
int maxPathSum(TreeNode *root) {
int res = INT_MIN;
helper(root, res);
return res;
}
int helper(TreeNode *root, int & res)
{
if(root==NULL)return ;
int left = max(,helper(root->left,res));
int right = max(,helper(root->right,res));
res = max(res,left+right+root->val);
return max(left,right)+root->val;
}
};
Maximum Subarray 最大子数组
思路一：dp O(n) dp[i] = max(dp[i-1], 0)+a[i]
思路二: 分治，每次把数组一分为二，分别找出左边和右边的最大子数组之和，然后还要从中间开始向左右分别扫描，求出的最大值分别和左右两边得出的最大值比较取最大的
class Solution {
public:
int maxSubArray(int A[], int n) {
if (n==) return ;
return helper(A, , n - );
}
int helper(int num[],int l,int r)
{
if(l>=r)return num[l];
int mid = (l+r)/;
int left = helper(num,l,mid-);
int right = helper(num,mid+,r);
int mmax = num[mid], t = mmax;
for (int i = mid - ; i >= l; --i) {
t += num[i];
mmax = max(mmax, t);
}
t = mmax;
for (int i = mid + ; i <= r; ++i) {
t += num[i];
mmax = max(mmax, t);
}
return max(max(left,right),mmax);
}
};
sqrtx
开根号，返回int
二分法：
注意判出条件有两个。
int sqrt(int x) {
if(x < )
return -;
long l = , r = x;
while(l<=r)
{
long mid = l+(r-l)/;
if(mid*mid==x || (mid * mid < x && (mid + ) * (mid + ) > x))return mid;
if(mid*mid<x)l=mid+;
else r = mid-;
}
return ;
}
牛顿法：
转自Matrix67
随便设一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了。
仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根，这个函数的导数是2x。也就是说，函数上任一点(x,f(x))处的切线斜率是2x。那么，x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2。
int sqrt(int x) {
if(x < )
return -;
long res = x;
while(res * res > x)
res = ((res + x / res) >> );
return res;
}
Permutation Sequence
求第k个全排列，直接dfs求超时
有个O(n)的好方法，从左到右一个一个求出来。因为只要求1个，所以可以按照全排列的规则，一个个数的求出每个位置的数字，而不需要将所有的全排列字符串列出来。
对于n个字符组成的字符串{1,2,3,...,n}，取第k个排列时，首先可以求出第k个排列字符串中的第一个数，即(k-1)/(n-1个数的排列个数)
下面是递归和非递归的两种写法
class Solution {
public:
string res="";
string nums = "";
string getPermutation(int n, int k) {
string s;
for(int i=;i<n;i++)
s += nums[i];
solve(s,k);
return res;
}
void solve(string& s, int k)
{
if(s==""||k==)return;
int len = s.size();
int cnt=; // 计算 (n-1)个数的排列个数cnt
for(int i=;i<len;i++)
{
cnt*=len-i;
}
int pos = (k-)/cnt;
res+=s[pos];
k-=cnt*pos;
s=s.erase(pos,);
solve(s,k);
}
};
string getPermutation(int n, int k) {
string s;
string res="";
string nums = "";
for(int i=;i<n;i++)s += nums[i];
for(int i=;i<n;i++)
{
int cnt=;
int len=s.size()-;
while(len>)
{
cnt*=len;
len--;
}
int pos = (k-)/cnt;
k-=cnt*pos;
res+=s[pos];
s.erase(pos,);
}
return res;
}
pascals-triangle-ii
只用O(k)空间返回第k个杨辉三角数组
类比01背包，容量倒循环写法省空间
class Solution {//合理规划dp转移方向降低一个维度
public:
vector<int> getRow(int rowIndex) {
vector<int> dp(rowIndex+,);
dp[]=;
for(int i=;i<=rowIndex;i++)
for(int j=i;j>;j--)
{
dp[j]=dp[j]+dp[j-];
}
return dp;
}
};
populating-next-right-pointers-in-each-node
将完全二叉树改写成next指针指向右边结点的形式，这题之前做过，不用多余空间又忘了怎么搞了orz。应该考虑连续两层的信息。只考虑当前层肯定就断了，不要一直卡在这里。
void connect(TreeLinkNode *root) {
if(!root)return;
while(root->left)
{
TreeLinkNode* p=root;
while(p)
{
p->left->next = p->right;
if(p->next)
p->right->next = p->next->left;
else
p->right->next = NULL;
p=p->next;
}
root = root->left;
}
}
populating-next-right-pointers-in-each-node II
凉凉，上一题变一下形又凉了，这题树变为任意二叉树，要灵活运用dummy结点处理，这样从起始到结束都是统一的形式，方便循环处理。当找第一个结点的情况与找后序存在的结点情况相似时，考虑dummy伪结点的使用
void connect(TreeLinkNode *root) {
if(!root)return;
while(root)
{
TreeLinkNode* dummy = new TreeLinkNode(-); // 每一层的头结点
TreeLinkNode* cur = dummy;
while(root)
{
if(root->left)
{
cur->next = root->left;
cur = cur->next;
}
if(root->right)
{
cur->next = root->right;
cur = cur->next;
}
root=root->next;
}
root = dummy->next;
}
}
distinct-subsequences
dp ：当前位置选或不选
array[i][j] 表示T[0, j] 在S[0, i] 中的匹配个数
如果不使用S[i] , 那么f(i , j) = f(i-1 , j)
如果使用了S[i] , 那么一定有 S[i] == T[j] , f( i , j ) = f(i -1 , j -1 )
所以当S[i]==T[j]时，有array( i , j ) = array( i -1 , j ) + array(i - 1 , j - 1);
当S[i]!=T[j]时，有 array( i , j ) = array( i -1 , j );
在使用中不难发现该dp二维数组可以降维，注意改变数组元素值时由后往前，这样不会覆盖[i-1]的值，dummy处理很巧
int numDistinct(string S, string T) {
if(S.size()==||T.size()==)return ;
vector<int> dp(T.size()+,);
dp[]=;//dummy
int len = T.size();
for(int i=;i<=S.size();i++)
{
for(int j=min(i,len);j>;j--)
if(S[i-]==T[j-])
dp[j]=dp[j-]+dp[j];
}
return dp[len];
}
binary-tree-level-order-traversal-ii
倒序的层序遍历
1 bfs层序遍历后reverse，虽然能做但这个方法太low不符合命题者出题意图
2 查出max depth后，dfs从第一层max_depth到最后一层1，用一个数组存储
3 递归版bfs，很巧，不直接存到result中，先进行下一层递归，存最后一层然后一层一层递归上来，再把当前层的结果保存到result中 。
binary-tree-zigzag-level-order-traversal
1. 这题用bfs+size+tag-reverse可以搞，但比较low
2. 可以双栈搞。注意第二个栈的入栈顺序，先右再左
rotate-image
先关于主对角线对称，然后关于中间行对称。
* merge-k-sorted-lists
1. merge sort 分治做
2. 优先队列最小堆做
分布式常考，解法见blog
分治写法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.size() == ) return NULL;
return merge(lists,,lists.size()-);
}
ListNode* merge(vector<ListNode *> &lists, int l,int r)
{
if(l<r) {
int mid = (l+r) / ;
ListNode* left = merge(lists, l,mid);
ListNode* right = merge(lists, mid+,r);
return mergeTwoLists(left,right);
}
else return lists[l];
}
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = new ListNode(-);
ListNode *cur = head;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
if (l2) cur->next = l2;
return head->next;
}
};
最小堆写法：
首先把k个链表的首元素都加入最小堆中，它们会自动排好序。然后我们每次取出最小的那个元素加入我们最终结果的链表中，然后把取出元素的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时k个链表也合并为了一个链表，返回首节点
struct cmp {
bool operator () (ListNode *a, ListNode *b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> q;//最小堆
for (int i = ; i < lists.size(); ++i) {
if (lists[i]) q.push(lists[i]);
}
ListNode *head = NULL, *pre = NULL, *tmp = NULL;
while (!q.empty()) {
tmp = q.top();
q.pop();
if (!pre) head = tmp;
else pre->next = tmp;
pre = tmp;
if (tmp->next) q.push(tmp->next);
}
return head;
}
};
remove-duplicates-from-sorted-array-ii
给一个排好序的数组，最多允许2个重复元素。注意要和筛选后的数组比较，不是和原数组比较
int removeDuplicates(int A[], int n) {
if(n<)return n;
int index=;
for(int i=;i<n;i++)
{
if(A[i]!=A[index-])
A[index++]=A[i];
}
return index;
}
subsets
递增的全排列，要考虑初始数组不是顺序的情况，dp来做看代码，追加法写的很好，最后按元素数排序输出
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> result;
vector<vector<int>> res;
vector<int> v;
result.push_back(v);
res.push_back(v);
for(int i=;i<S.size();i++){
int n = result.size();
for(int j=;j<n;j++){
result.push_back(result[j]);
result[j].push_back(S[i]);
sort(result[j].begin(), result[j].end());// 原数组不是有序数组
}
}
sort(result.begin(), result.end());
for(int j=;j<=S.size();j++)
for(int k=;k<result.size();k++)
if(result[k].size() == j)
res.push_back(result[k]);
return res;
}
combinations
sb了这题，看清样例是啥再做行吗，又tm上来就无脑dfs，人家是有序无重复的结果
vector<vector<int> > combine(int n, int k)
{
vector<vector<int>> res;
vector<int> tmp;
dfs(n,k,,res,tmp);
return res;
}
void dfs(int n,int k,int start,vector<vector<int>> &res,vector<int> tmp)
{
if(tmp.size() == k)
{
res.push_back(tmp);
return;
}
for(int i=start;i<=n;i++)
{
tmp.push_back(i);
dfs(n,k,i+,res,tmp);
tmp.pop_back();
}
}
set-matrix-zeroes
使用常数空间，如果矩阵某个元素为0，则其所在行和列都为0
方法1. 主要防止覆盖问题，可以先用-1处理所在行和列元素，最后还原为0。
方法2. 用第一行和第一列作为统计标识，首先要判断第一行和第一列是否需要清零，然后遍历内部矩阵并记录，再根据记录清零，最后看是否需要清零第一行第一列。
Simplify Path
字符串好题
思路一：针对每一个需求分别处理
string simplifyPath(string path) {
int pos;
while((pos = path.find("//"))!=-) //去掉//
{
path.erase(pos,);
}
while((pos = path.find("/./"))!=-) //去掉/./
{
path.erase(pos,);
}
while((pos = path.find("/../"))!=-)//去掉/../
{
path.erase(pos,);
if(pos==)continue;
int p = path.rfind("/",pos-);
path.erase(p,pos-p);
}
if(path.size()>&&path.substr(path.size()-,)=="/.."){//去掉/..
path.erase(path.size()-,);
if(int(path.size())->=){
int p = path.rfind("/",path.size()-);
path.erase(p,path.size()--p);
}
}
if(path.size()>&&path.substr(path.size()-,)=="/.")path.erase(path.size()-,); //去掉/.
if(path.size()>&&path[path.size()-]=='/')path.erase(path.size()-,);//处理结尾
return path;
}
思路二：遍历一遍，遍历过程中综合考虑各种因素
class Solution {
public:
string simplifyPath(string path) {
vector<string> v;
int i = ;
while (i < path.size()) {
while (path[i] == '/' && i < path.size()) ++i;
if (i == path.size()) break;
int start = i;
while (path[i] != '/' && i < path.size()) ++i;
int end = i - ;
string s = path.substr(start, end - start + );
if (s == "..") {
if (!v.empty()) v.pop_back();
} else if (s != ".") {
v.push_back(s);
}
}
if (v.empty()) return "/";
string res;
for (int i = ; i < v.size(); ++i) {
res += '/' + v[i];
}
return res;
}
};
%是带有符号的，这点要注意
spiral-matrix-ii
螺旋数组正确写法(JAVA)
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
if (n < 1)
return res;
int index = 1, rowStart = 0, rowEnd = n - 1, colStart = 0, colEnd = n - 1;
while (index <= n * n) {
for (int i = colStart; i <= colEnd; i++) {
res[rowStart][i] = index++;
}
for (int i = rowStart + 1; i <= rowEnd; i++) {
res[i][colEnd] = index++;
}
for (int i = colEnd - 1; i >= colStart; i--) {
res[rowEnd][i] = index++;
}
for (int i = rowEnd - 1; i > rowStart; i--) {
res[i][colStart] = index++;
}
rowStart += 1;
rowEnd -= 1;
colStart += 1;
colEnd -= 1;
}
return res;
}
spiral-matrix
while(l<=r&&up<=down)
{
for(int i=l;i<=r;i++)
ans.push_back(matrix[up][i]);
for(int i=up+;i<=down;i++)
ans.push_back(matrix[i][r]);
for(int i=r-;up!=down&&i>=l;i--) //由于矩阵是任意的，注意往返不能重复
ans.push_back(matrix[down][i]);
for(int i=down-;l!=r&&i>up;i--)//注意往返不能重复
ans.push_back(matrix[i][l]);
l++,r--,up++,down--;
}
search-for-a-range
两次二分夹逼法，注意等号的选择
int l1=,r1=n-,l2=,r2=n-;
while(l1 <= r1)
{
int mid = l1+((r1-l1)>>);
if(A[mid] < target)
l1 = mid + ;
else
r1 = mid - ;
}
while(l2 <= r2)
{
int mid = l2+((r2-l2)>>);
if(A[mid] > target)
r2 = mid - ;
else
l2 = mid + ;
}
vector<int> result(,-);
if(l1 <= r2)
{
result[] = l1;
result[] = r2;
}
return result;
}
first-missing-positive
思路：将数值和位置形成映射，使得A[i]=i+1
int firstMissingPositive(int A[], int n) {
for(int i=;i<n;)
{
if((A[i]<=||A[i]>n)&&i<n)
{
i++;
}
else if(A[A[i]-]!=A[i])// 注意不能直接写A[i]!=i+1 因为[1,1]可能死循环
{
swap(A[i],A[A[i]-]);
}
else i++;
}
int i;
for(i=;i<n;i++)
if(A[i]!=i+)break;
return i+;
}
search-in-rotated-sorted-array
旋转排序数组找target
思路：二分后，一定按顺序的找，注意等号
int search(int A[], int n, int target) {
int l=,r=n-;
while(l<=r)
{
int mid = (l+r)/;
if(A[mid]==target)return mid;
if(A[l]<=A[mid])//等号必须在这里，eg:[3,1] 1
{
if(A[l]<=target&&target<A[mid])
r=mid-;
else l=mid+;
}
else
{
if(A[mid]<target&&target<=A[r])
l=mid+;
else r=mid-;
}
}
return -;
}
unique-binary-search-trees
分阶段，先看根节点，可以1到n，当根节点确定时找状态转移，因为是bst，所以左子树为i-1个结点，右子树为n-i个结点，两者乘积
int dp[]={};
int numTrees(int n) {
dp[]=;
dp[]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=i;j++)
dp[i]+=dp[j-]*dp[i-j];
}
return dp[n];
}
unique-binary-search-trees II
vector<TreeNode *> generateTrees(int n) {
return dfs(,n);
}
vector<TreeNode *> dfs(int l,int r){
vector<TreeNode*> ans;
if(l>r) {ans.push_back(NULL);return ans;}
for(int i=l;i<=r;i++){
vector<TreeNode*> vecl=dfs(l,i-),vecr=dfs(i+,r);
for(auto p:vecl)
for(auto q:vecr){
TreeNode *root=new TreeNode(i);
root->left=p;
root->right=q;
ans.push_back(root);
}
}
return ans;
}
minimum-window-substring
尺取法O(n), 在S串中遍历一次，找到包含T串中所有元素的最小子串
思路：因为无序所以hash，map记录元素及对应个数，保留T串整体信息
l=0，r从头向后遍历，直到子串中元素满足map的记录，用count==T.size()判断，记录子串，l右移直到越过第一个T中的元素使子串不满足map条件，此时确定l边界，r右移确定右边界
class Solution {
public:
string minWindow(string S, string T) {
string res;
map<char,int> t,s;
for(auto c:T)
t[c]++;
int count=,l=;
for(int r=;r<S.length();r++)
{
if(t[S[r]]!=)
{
s[S[r]]++;
if(s[S[r]]<=t[S[r]])
count++;
while(count==T.size())
{
if(res.empty()||res.length()>r-l+)
res=S.substr(l,r-l+);
if(t[S[l]])
{
s[S[l]]--;
if(s[S[l]]<t[S[l]])
count--;
}
l++;
}
}
}
return res;
}
};
longest-common-prefix：对所有string排序后比较首尾即可
roman-to-integer：当前一个罗马数字小于后一个时是特例，要减去2倍的前一个数字值
regular-expression-matching
方法一：递归求解
先来判断p是否为空，若为空则根据s的为空的情况返回结果。当p的第二个字符为*号时，由于*号前面的字符的个数可以任意，可以为0，那么先用递归来调用为0的情况，就是直接把这两个字符去掉再比较，或者当s不为空，且第一个字符和p的第一个字符相同时，我们再对去掉首字符的s和p调用递归，注意p不能去掉首字符，因为*号前面的字符可以有无限个；如果第二个字符不为*号，那么就的比较第一个字符，然后对后面的字符串递归
class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty()) return s.empty();
if (p.size() > && p[] == '*') {
return isMatch(s, p.substr()) || (!s.empty() && (s[] == p[] || p[] == '.') && isMatch(s.substr(), p)); //注意这里
} else {
return !s.empty() && (s[] == p[] || p[] == '.') && isMatch(s.substr(), p.substr());
}
}
};
方法二：dp
我们也可以用DP来解，定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况：
1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + , vector<bool>(n + , false));
dp[][] = true;
for (int i = ; i <= m; ++i) {
for (int j = ; j <= n; ++j) {
if (j > && p[j - ] == '*') {
dp[i][j] = dp[i][j - ] || (i > && (s[i - ] == p[j - ] || p[j - ] == '.') && dp[i - ][j]);
} else {
dp[i][j] = i > && dp[i - ][j - ] && (s[i - ] == p[j - ] || p[j - ] == '.');
}
}
}
return dp[m][n];
}
};
divide-two-integers：倍增法用的好，减少循环次数
题意：不能用乘法，除法，取余操作，实现整数除法
int divide(int dividend, int divisor) {
if(divisor == )
return INT_MAX;
long long result=,flag=;
if((dividend<)^(divisor<))
flag=;
long long a = abs(dividend), b = abs(divisor);
while(a >= b)
{
long long k = , t = b;
while(a >= t)
{
a -= t;
result += k;
k <<= ;
t += t;
}
}
return flag?-result:result;
}
longest-substring-without-repeating-characters
双指针维护区间，尺取法枚举可能解，这里的词典只记录字母是否出现，并不记录位置。
int lengthOfLongestSubstring(string s) {
int len = s.size();
int dic[]={};
int ans=,p=;
for(int q=;q<len;q++)
{
while(dic[s[q]])
{
dic[s[p]]--;
p++;
}
ans=max(ans,q-p+);
dic[s[q]]++;
}
return ans;
}
longest-palindromic-substring
二维dp 0:不回文，1:回文。注意奇数偶数的初始情况。
string longestPalindrome(string s) {
int len = s.length(),ans;
int dp[len+][len+];
memset(dp,,sizeof(dp));
int rec[len+];
for(int i = ;i < len;i++) dp[i][i] = ,ans = ,rec[] = ;
for(int i = ;i < len-;i++) if(s[i] == s[i+]) ans = ,rec[] = i,dp[i][i+] = ;
for(int i = ;i <= len;i++){
for(int j = ;j <= len-i;j++){
if(s[j] == s[j+i-]) {
dp[j][i+j-] = dp[j+][i+j-];
if(dp[j][i+j-] == ) {ans = max(ans,i),rec[i] = j;}
}
}
}
return s.substr(rec[ans],ans);
}
median-of-two-sorted-arrays
分治，注意递归的出口，一个是k=1，另一个是边界
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if((m+n)%==)
return (help(A,,m,B,,n,(m+n)/)+help(A,,m,B,,n,(m+n)/+))/;
else
return help(A,,m,B,,n,(m+n)/+);
}
double help(int A[], int aStart, int m, int B[], int bStart, int n, int k)
{
if(aStart >= m)
return B[bStart+k-];
if(bStart >= n)
return A[aStart+k-];
if(k==)
return min(A[aStart],B[bStart]);
int aMin = 0x7fffffff, bMin = 0x7fffffff;
if(aStart + k / - < m)
aMin = A[aStart + k/ -];
if(bStart + k / - < n)
bMin = B[bStart + k / - ];
if(aMin<bMin)
return help(A,aStart+k/,m,B,bStart,n,k-k/);
else
return help(A,aStart,m,B,bStart+k/,n,k-k/);
}
3sum
选出数组中相加为0的3个数，要求非递减，不重复
思路：fix一个数转换为2sum+set会超时
先排序，固定一个数，确定后两个数的和。在后面的数组中两头向中间找，注意剪枝与去重的操作
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > ans;
sort(num.begin(),num.end());
if(num.empty()||num.front()>||num.back()<)return {};
for(int i=;i<num.size()-;i++)
{
if(num[i]>)break;
if(i>&&num[i]==num[i-])continue;
int target = - num[i];
int j=i+,k=num.size()-;
while(j<k)
{
if(num[j]+num[k]==target)
{
ans.push_back({num[i],num[j],num[k]});
while(j<k&&num[j]==num[j+])j++;
while(j<k&&num[k]==num[k-])k--;
j++,k--;
}
else if(num[j]+num[k]<target)
j++;
else
k--;
}
}
return ans;
}
reverse-nodes-in-k-group
这题考察链表反转，头插的双指针写法
ListNode *reverseKGroup(ListNode *head, int k) {
if(head == NULL || head->next == NULL || k < ) return head;
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* pre = dummy, *cur = head, *temp;
int len = ;
while (head != NULL) {
len++ ;
head = head->next;
}
for (int i = ; i < len / k; i ++ ) {
for (int j = ; j < k; j ++ ) {
temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
pre = cur;
cur = cur->next;
}
return dummy->next;
}
generate-parentheses
产生括号的全排列
思路：全排列，容易想到dfs，由于括号包含左括号和右括号两部分，所以一方面不用考虑左括号，让他不断生成就好，对于右括号，设置两种情况，分别是生成和不生成右括号。
vector<string> generateParenthesis(int n) {
vector<string> s;
dfs(,,"",s,n);
return s;
}
void dfs(int left, int right, string tmp, vector<string> & s, int n)
{
if(left==n&&right==n)
{
s.push_back(tmp);
return;
}
if(left<n)
dfs(left+,right,tmp+'(',s,n);
if(left>right&&right<n)
dfs(left,right+,tmp+')',s,n);
}
substring-with-concatenation-of-all-words
这道题空间换时间的思路特别，不同word concate的组合非常多，枚举非常不明智，那么就hash好了。接下来就是暴力匹配，内部循环words.size()次，用另一个hash map记录匹配到的word个数。
O(n)方法，尺取法，每次尺取一个word长度，还是两个hashmap
vector<int> findSubstring(string S, vector<string>& L) {
if (S.empty() || L.empty())return {};
vector<int> res;
int n = S.size(), cnt = L.size(), len = L[].size();
unordered_map<string, int> m1;
for (string w : L) ++m1[w];
for (int i = ; i < len; i++)
{
int left = i, count = ;
unordered_map<string, int> m2;
for (int j = i; j <= n - len; j += len)
{
string t = S.substr(j,len);
if (m1.count(t))
{
++m2[t];
if (m2[t] <= m1[t])
++count;
else
{
while (m2[t] > m1[t])
{
string tmp = S.substr(left, len);
m2[tmp]--;
if (m2[tmp] < m1[tmp])count--;
left += len;
}
}
if (count == cnt)
{
res.push_back(left);
m2[S.substr(left, len)]--;
--count;
left += len;
}
}
else
{
m2.clear();
count = ;
left = j + len;
}
}
}
sort(res.begin(),res.end());
return res;
}
longest-valid-parentheses
找出最长的合法括号子串，输出长度
常规做法，栈中存左括号，栈空时记录起始节点位置
int longestValidParentheses(string s) {
stack<int> st;
int ans=,t=-;
if(s.size()==)return ;
for(int i=;i<s.size();i++)
{
if(s[i]=='(')st.push(i);
else
{
if(st.empty())t=i;
else
{
st.pop();
if(st.empty())
ans = max(ans,i-t);
else
ans = max(ans,i-st.top());
}
}
}
return ans;
}
Largest Rectangle in Histogram
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = ;
stack<int> st;
heights.push_back();
for (int i = ; i < heights.size(); ++i) {
while (!st.empty() && heights[st.top()] >= heights[i]) {
int cur = st.top(); st.pop();
res = max(res, heights[cur] * (st.empty() ? i : (i - 1 - st.top())));// 注意这里是st.top()而不是cur，两者之间有可行的宽度，前一次出栈了
}
st.push(i);
}
return res;
}
};
Longest Consecutive Sequence 求最长连续序列
O(n)时间复杂度
方法(1) hash set求解，将序列存入set，对每个数，从左右两个方向展开搜索hash匹配，然后删除这个数，避免重复搜索
方法(2) hash map求解，map初始为空，如果map[x]有值则表示已访问，continue(这里强调用count判断，如果用默认map映射判断，会自动生成一个为0的映射)，只需判断map[x-1], map[x+1]即可，更新ma[x-left], map[x+right]的值。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res = ;
unordered_map<int, int> m;
for (int num : nums) {
if (m.count(num)) continue;
int left = m.count(num - ) ? m[num - ] : ;
int right = m.count(num + ) ? m[num + ] : ;
int sum = left + right + ;
m[num] = sum;
res = max(res, sum);
m[num - left] = sum;
m[num + right] = sum;
}
return res;
}
};
Course schedule（拓扑排序）
方法一：bfs+入度
方法二：dfs+访问标记(标记循环) 0表示还未访问过，1表示已经访问了(为了剪枝)，-1 表示有冲突(一次dfs中判断是否有环)
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>());
vector<int> visit(numCourses);
for (auto a : prerequisites) {
graph[a[]].push_back(a[]);
}
for (int i = ; i < numCourses; ++i) {
if (!canFinishDFS(graph, visit, i)) return false;
}
return true;
}
bool canFinishDFS(vector<vector<int>>& graph, vector<int>& visit, int i) {
if (visit[i] == -) return false;
if (visit[i] == ) return true;
visit[i] = -;
for (auto a : graph[i]) {
if (!canFinishDFS(graph, visit, a)) return false;
}
visit[i] = ;
return true;
}
};
Sliding Window Maximum
1 最大堆 pair<value, position> 2 双端队列，维护按序单调递减
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
for (int i = ; i < nums.size(); ++i) {
if (!q.empty() && q.front() == i - k) q.pop_front(); // 删除左边元素
while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();// 保持队列单调递减
q.push_back(i);
if (i >= k - ) res.push_back(nums[q.front()]);
}
return res;
}
};
Meeting Rooms II
计算线段最大重叠个数，对于线段，可以特殊处理，起始点+1，终止点-1，这样遍历的过程可以模拟实线段
class Solution {
public:
int minMeetingRooms(vector<Interval>& intervals) {
map<int, int> m;
for (auto a : intervals) {
++m[a.start];
--m[a.end];
}
int rooms = , res = ;
for (auto it : m) {
res = max(res, rooms += it.second);
}
return res;
}
};
LRU cache
链表 和 map 实现 LRU 内存换页
get 和 put, get 函数是通过输入 key 来获得 value，如果成功获得后， (key, value) 升至缓存器中最常用的位置（顶部），如果 key 不存在，则返回 -1。put 函数是插入一对新的 (key, value)，如果原缓存器中有该 key，则需要先删除掉原有的，将新的插入到缓存器的顶部。如果不存在，则直接插入到顶部。若加入新的值后缓存器超过了容量，则需要删掉一个最不常用底部的值。
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
auto it = m.find(key);
if(it==m.end())return -;
l.splice(l.begin(), l, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = m.find(key);
if(it!=m.end())l.erase(it->second);
l.push_front(make_pair(key, value));
m[key]=l.begin();
if(l.size()>cap){
int k = l.rbegin()->first;
l.pop_back();
m.erase(k);
}
}
private:
int cap;
list<pair<int,int>> l;
unordered_map<int, list<pair<int,int>>::iterator> m;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
python
class Node:
def __init__(self, k, v):
self.key = k
self.val = v
self.prev = None
self.next = None class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.dic = dict()
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head def get(self, key):
if key in self.dic:
n = self.dic[key]
self._remove(n)
self._add(n)
return n.val
return -1 def set(self, key, value):
if key in self.dic:
self._remove(self.dic[key])
n = Node(key, value)
self._add(n)
self.dic[key] = n
if len(self.dic) > self.capacity:
n = self.head.next
self._remove(n)
del self.dic[n.key] def _remove(self, node):
p = node.prev
n = node.next
p.next = n
n.prev = p def _add(self, node):
p = self.tail.prev
p.next = node
self.tail.prev = node
node.prev = p
node.next = self.tail
Coin Change
DP有两种写法，一种为自底向上(dp迭代)，另一种为自顶向下(dfs+记忆数组)，两者等价
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> memo(amount+,INT_MAX);
memo[]=;
return dfs(coins,amount,memo);
}
int dfs(vector<int>& coins, int target, vector<int>& memo){
if(target<)return -;
if(memo[target]!=INT_MAX)return memo[target];
for(auto coin : coins){
int tmp = dfs(coins, target - coin, memo);
if(tmp>=) memo[target] = min(memo[target], tmp+);
}
return memo[target] = (memo[target] == INT_MAX) ? - : memo[target];
}
};