leetcode部分解题思路

此文件用于保持一些算法题,都是以前做过但没有掌握的,主要来源于leetcode,但不限于此。

leetcode-3

description

Given a string, find the length of the longest substring withou repeating characters.

idea

对于子字符串的问题都有一个统一的模型,用一个256长度的数组保存出现的字符的个数,用两个指针指示子串的头和尾,移动后指针并记录出现的字符,当map 中对应的值大于1时,出现重复,比较当前长度和最大长度,这时移动前指针,重复以上过程。

code

int lengthOfLongestSubstring(string s) {
    int size=s.size();
    if(size==0) return 0;
    vector<int> map(256,0);
    int front=0,back=0;
    int maxLen=0;
    int curLen=0;
    while(back<size) {
        if(map[s[back]]==0) {
            map[s[back]]+=1;
            curLen+=1;
            back++;
        }
        else {
            maxLen=curLen>maxLen?curLen:maxLen;
            while(s[front]!=s[back]) {
                map[s[front]]-=1;
                front++;
            }
            map[s[front]]-=1;
            front++;
            curLen=back-front;
        }
    }
    return max(maxLen,size-front);
}

leetcode-4

描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

想法

题目要求时间复杂度是lgN,那么只能考虑二分法。对于两个数组,比较k/2位置上的值,如果数组1中的key1大于数组2中的key2,所求的值不可能在key2之前的数中,故接下来可以在数组1和数组2key2之后的数中查找第(k - key2)大的数(因为已经去掉了key2个小的数)。同理,另外一边也一样。递归,直到k = 1或数组长度为0。要注意很多边界条件。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1=nums1.size();
int len2=nums2.size();
if((len1+len2) & 0x01) {
return findKth(nums1, 0, nums2, 0, (len1+len2)/2+1);
}
else return (findKth(nums1, 0, nums2, 0, (len1+len2)/2) + findKth(nums1, 0, nums2, 0, (len1+len2)/2+1))/2.0;
}

int findKth(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k) {
int len1=nums1.size()-start1;
int len2=nums2.size()-start2;
if(len1>len2) return findKth(nums2, start2, nums1, start1, k);

if(len1==0) return nums2[k-1];
if(k==1) return min(nums1[start1], nums2[start2]);

int k1=min(len1, k/2);
int k2=k-k1;
if(nums1[start1+k1-1] > nums2[start2+k2-1]) return findKth(nums1, start1, nums2, start2+k2, k-k2);
else if(nums1[start1+k1-1] < nums2[start2+k2-1]) return findKth(nums1, start1+k1, nums2, start2, k-k1);
else return nums1[k1-1];
}

联想 - top K

有大量整数,求出其中的前K个最大的数(最小的也是一样的原理)。

最大用最小堆,最小用最大堆。

leetcode - 5 longest Palindromic substring

description

Given a string s, find the longest palindromic substring in s.

idea

  1. 最直观的想法:遍历字符串,往两边对称扩展,注意分奇数和偶数的情况。
  2. 动态规划:dp[i][j]保持区间[i,j]之间的字符是否为回文。dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
  3. 马拉车算法。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
string longestPalindrome(string s) {
string sub="";
for(int i=0;i<s.size();++i)
{
string tmp;
size_t head=i-1,tail=i+1;
while(head>=0&&tail<=s.size()-1&&s[head]==s[tail])
{

head--,tail++;
}
tmp=s.substr(head+1,tail-head-1);
if(tmp.size()>sub.size()) sub=tmp;

if(i+1<s.size()&&s[i]==s[i+1])
{
tmp=s.substr(i,2);
head=i,tail=i+1;
}
while(head>=0&&tail<=s.size()-1&&s[head]==s[tail])
{

head--,tail++;
}
tmp=s.substr(head+1,tail-head-1);
if(tmp.size()>sub.size()) sub=tmp;
}
return sub;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void longestPalindrome (String str) {
int n = str.length(),left = 0,len=0;
int dp[][] = new int[n][n];
for(int i = 0;i < n; i++) {
dp[i][i] = 1;
}
//第一遍搜索下标:00 11 22 33
//第二遍搜索下标:01 12 23 34
//第三遍搜索下标:02 13 24 35
for(int j = 0;j < n; j++) {//j代表下标相隔的距离大小
for(int i = 0 ;i + j < n; i++){ //j索引从i开始,因为要对len进行赋值
if( str.charAt(i) == str.charAt(i+j) ){
if(j<2 || dp[i + 1][i + j - 1] == 1 ) {
dp[i][i+j] = 1;
}
}
if(dp[i][i+j] ==1 && len < j+1) {
len = j+1;
left = i;
}
}
}
System.out.println(str.substring(left, left + len));
}

leetcode - 8 string to int

description

实现atoi

idea

没什么难度,就是很烦,一个个判断,注意int能表示的范围

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int myAtoi(string str) {
if(str=="") return 0;
int p=-1;
int res=0;
bool sign=true;
while(str[++p]==' ');
if(str[p]=='+') {
sign=true;
p++;
}
else if(str[p]=='-') {
sign=false;
p++;
}
while(p<str.size()) {
if(str[p]>='0' && str[p]<='9') {
int tmp=str[p]-'0';
if(res > (0x7FFFFFFF-tmp)/10) {
if(sign) {
res=0x7FFFFFFF;
break;
}
else {
res=0x80000000;
break;
}
} else {
res=res*10+tmp;
}
} else {
break;
}
p++;
}
if(res==0) return 0;
return sign ? res : -res;
}

leetcode - 10 regular expression matching

描述

正则匹配,’.’代表任意字符,’*‘表示任意个前面的字符

idea

这个题有毒,头都炸了

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isMatch(string s, string p) {
if (p.empty()) return s.empty();
if (p.size() == 1) {
return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
}
if (p[1] != '*') {
if (s.empty()) return false;
return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}
while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
if (isMatch(s, p.substr(2))) return true;
s = s.substr(1);
}
return isMatch(s, p.substr(2));
}

leetcode - 15 3Sum

description

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

idea

直接看代码吧,写得还是很清晰的。主要跳过相同的元素。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int> > ret;
int size = nums.size();
sort(nums.begin(), nums.end());
for(int i = 0; i < size; i ++)
{
//skip same i
while(i > 0 && i < size && nums[i] == nums[i-1])
i ++;
int j = i + 1;
int k = size - 1;
while(j < k)
{
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0)
{
vector<int> cur(3);
cur[0] = nums[i];
cur[1] = nums[j];
cur[2] = nums[k];
ret.push_back(cur);
j ++;
k --;
//skip same j
while(j < k && nums[j] == nums[j-1])
j ++;
//skip same k
while(k > j && nums[k] == nums[k+1])
k --;
}
else if(sum < 0)
{
j ++;
//skip same j
while(j < k && nums[j] == nums[j-1])
j ++;
}
else
{
k --;
//skip same k
while(k > j && nums[k] == nums[k+1])
k --;
}
}
}
return ret;
}

leetcode - 22 Generate Parentnes

description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

idea

The idea is intuitive. Use two integers to count the remaining left parenthesis (n) and the right parenthesis (m) to be added. At each function call add a left parenthesis if n >0 and add a right parenthesis if m>0. Append the result and terminate recursive calls when both m and n are zero.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<string> generateParenthesis(int n) {
vector<string> res;
addingpar(res, "", n, 0);
return res;
}
void addingpar(vector<string> &v, string str, int n, int m){
if(n==0 && m==0) {
v.push_back(str);
return;
}
if(m > 0){ addingpar(v, str+")", n, m-1); }
if(n > 0){ addingpar(v, str+"(", n-1, m+1); }
}

leetcode - 29 Divide Two Integers

description

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.

idea

可以用移位和加减法。A除以B,就相当于是算A里面有多少个B。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int divide(int dividend, int divisor) {
if(divisor == 0 || ((dividend == 0x80000000) && (divisor==-1))) return 0x7FFFFFFF;
bool sign = (dividend >=0) == (divisor>0);
long long dd = labs(dividend);
long long d = labs(divisor);
int res=0;
while(dd >= d) {
long long tmp=d;
int count=1;
while(dd>=tmp) {
dd-=tmp;
res+=count;
tmp<<=1;
count<<=1;
}
}
return sign ? res : -res;
}

leetcode - 30 Substring with Concatenation of All Words

description

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).

idea

用一张hash表保存各个word出现的次数,然后遍历字符串去匹配。
算法简单直观,但是时间复杂度高,在leetcode 统计上看到还有一个复杂度更好的方法,但是没看到代码和实现。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> counts;
for (string word : words)
counts[word]++;
int n = s.length(), num = words.size(), len = words[0].length();
vector<int> indexes;
for (int i = 0; i < n - num * len + 1; i++) {
unordered_map<string, int> seen;
int j = 0;
for (; j < num; j++) {
string word = s.substr(i + j * len, len);
if (counts.find(word) != counts.end()) {
seen[word]++;
if (seen[word] > counts[word])
break;
}
else break;
}
if (j == num) indexes.push_back(i);
}
return indexes;
}

leetcode - 31 Next Permutation

Description

构造全排列

Idea

字典序全排列,这个不会没什么好说的了

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void nextPermutation(vector<int>& nums) {
int s=nums.size();
int tag1=-1,tag2=-1;
for(int i=s-2;i>=0;i--)
{
if(nums[i]<nums[i+1])
{
tag1=i;
break;
}

}
if(tag1==-1)
{
sort(nums.begin(),nums.end());
return;
}
for(int i=s-1;i>0;i--)
{
if(nums[i]>nums[tag1])
{
tag2=i;
break;
}
}
int tmp=nums[tag1];
nums[tag1]=nums[tag2];
nums[tag2]=tmp;
sort(nums.begin()+tag1+1,nums.end());
}

leetcode - 32 Longest Valid Parentheses

description

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

idea

遍历一遍字符串,用一个栈保存索引,若当前字符和栈顶匹配,则出栈,这样最后栈里的元素都是不能匹配的,计算两两之间的距离,就能得到结果。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int longestValidParentheses(string s) {
int n = s.length(), longest = 0;
stack<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') st.push(i);
else {
if (!st.empty()) {
if (s[st.top()] == '(') st.pop();
else st.push(i);
}
else st.push(i);
}
}
if (st.empty()) longest = n;
else {
int a = n, b = 0;
while (!st.empty()) {
b = st.top(); st.pop();
longest = max(longest, a-b-1);
a = b;
}
longest = max(longest, a);
}
return longest;
}

leetcode - 37 Sudoku Solver

description

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.

idea

典型的深搜的题,不会就别找工作了。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
bool isValid(vector<vector<char> > &board, int x, int y)  
{
int i, j;
for (i = 0; i < 9; i++)
if (i != x && board[i][y] == board[x][y])
return false;
for (j = 0; j < 9; j++)
if (j != y && board[x][j] == board[x][y])
return false;
for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
if (i != x && j != y && board[i][j] == board[x][y])
return false;
return true;
}
bool solveSudoku(vector<vector<char>>& board) {
int i=0,j=0;
int size=board.size();
for(int i=0;i<size;++i)
{
for(int j=0;j<size;++j)
{
if(board[i][j]=='.')
{
for(int k=1;k<=9;++k)
{
board[i][j]='0'+k;
if(isValid(board,i,j) && solveSudoku(board))
return true;
board[i][j]='.';
}
return false;
}
}
}
return true;
}

leetcode - 41 First Missing Positive

description

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

idea

一个长度为 N 的数组,存储从 1 开始的连续整数,最多就是 N 个,如果有 miss的,一定在中间某处。
注意:交换的时候,前一个变量已经改变了,所以不能继续用了。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 int firstMissingPositive(vector<int>& nums) {
int i=0;
while(i<nums.size()) {
if(nums[i]>0 && nums[i]<=nums.size() && nums[i]!=nums[nums[i]-1]) {
int tmp=nums[i];
nums[i]=nums[tmp-1];
nums[tmp-1]=tmp;
} else {
i++;
}
}
for(int i=0;i<nums.size();i++) {
if(nums[i]!=i+1) return i+1;
}
return nums.size()+1;
}

leetcode - 42 Trapping Rain Water

description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

idea

如果当前的高度比两边的最大高度中较小的一个低,那么就可以装水。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   int trap(vector<int>& height) {
int i=0,j=height.size()-1,maxL=0,maxR=0;
int res=0;
while(i<=j) {
if(height[i]>height[j]) {
maxR=maxR>height[j]?maxR:height[j];
res+=maxR-height[j];
j--;
} else {
maxL=maxL>height[i]?maxL:height[i];
res+=maxL-height[i];
i++;
}
}
return res;
}

leetcode - 44 Wildcard Matching

description

Implement wildcard pattern matching with support for ‘?’ and ‘‘.
‘?’ Matches any single character.
‘ Matches any sequence of characters (including the empty sequence).

idea

双指针:
遇到 × 的时候保留下当前p和s 的位置,先把 × 当0个匹配,遇到不匹配了再回来,把 × 当1个匹配,就这样一直遍历。

动归:
遇到 × ,要么匹配0个,要么匹配多个,由于动归的特性,只要往前移一个就可以了。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 双指针
bool isMatch(string s, string p) {
int star=-1,sp=0,pp=0,ss=-1;
while(sp<s.size()) {
if(s[sp]==p[pp] || p[pp]=='?') { sp++; pp++; }
else if(p[pp]=='*') { star=pp; ss=sp; pp++; }
else if(star!=-1) { pp=star+1; sp=++ss; }
else return false;
}
while(pp<p.size()) {
if(p[pp]!='*') break;
pp++;
}
return pp==p.size();
}

//动归
bool isMatch(string s, string p) {
int rows = s.size() + 1;
int cols = p.size() + 1;

vector<vector<bool>> dp(rows, vector<bool>(cols, false));

dp[0][0] = true;

for (int i = 1; i < rows; i++){
dp[i][0] = false;
}

for (int j = 1; j < cols; j++){
if (p[j-1] == '*')
dp[0][j] = dp[0][j-1];
}

for (int i = 1; i < rows; i++){
for (int j = 1; j < cols; j++){
if (p[j-1] == s[i-1] || p[j-1] == '?'){
dp[i][j] = dp[i-1][j-1];
}
else if (p[j-1] == '*'){
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
}

return dp[rows-1][cols-1];
}

leetcode - 50 Pow(x, n)

description

Implement pow(x, n).

idea

尽量用移位来解决问题

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  double myPow(double x, int n) {
double ans = 1;
unsigned long long p;
if (n < 0) {
p = -n;
x = 1 / x;
} else {
p = n;
}
// 二进制层面的个数
while (p) {
if (p & 1)
ans *= x;
x *= x;
p >>= 1;
}
return ans;
}

leetcode - 51 N-Quees

description

八皇后问题

idea

回溯,穷举

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
bool isValid(const vector<string>& solu,int r,int c) {
int n=solu.size();
// row col
for(int i=0;i<n;i++) {
if(i!=c && solu[r][i]=='Q') return false;
if(i!=r && solu[i][c]=='Q') return false;
}

for(int i=r+1,j=c-1;i<n && j>=0;i++,j--) {
if(solu[i][j]=='Q') return false;
}
for(int i=r-1,j=c+1;i>=0 && j<n;i--,j++) {
if(solu[i][j]=='Q') return false;
}

for(int i=r-1,j=c-1;i>=0 && j>=0;i--,j--) {
if(solu[i][j]=='Q') return false;
}
for(int i=r+1,j=c+1;i<n && j<n;i++,j++) {
if(solu[i][j]=='Q') return false;
}
return true;
}

void help(vector<vector<string>>& res,vector<string>& solu,int count) {
int n=solu.size();
if(count==n) {
res.push_back(solu);
return;
}

for(int j=0;j<n;++j) {
if(isValid(solu,count,j)) {
solu[count][j]='Q';
help(res,solu,count+1);
solu[count][j]='.';
}
}
}

vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> solu(n,string(n,'.'));
help(res,solu,0);
return res;

}

##leetcode - 56 Merge Intervals

description

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

idea

按start排序,然后看end是否和start有交叉。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<Interval> merge(vector<Interval>& intervals) {
if(intervals.size()<2) return intervals;
sort(intervals.begin(),intervals.end(),[](Interval a,Interval b)->bool{ return a.start<b.start; });
vector<Interval> res;
int start=intervals[0].start;
int end=intervals[0].end;
for(auto in : intervals) {
if(in.start<=end) {
end=max(end,in.end);
} else {
res.push_back(Interval(start,end));
start=in.start;
end=in.end;
}
}
res.push_back(Interval(start,end));
return res;
}

leetcode - 71 Simplify Path

description

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = “/home/“, => “/home”
path = “/a/./b/../../c/“, => “/c”

idea

this code can comment itself.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
string split(string& ori,char t) {
string ret("");
size_t pos=-1;
for(size_t i=0;i<ori.size();++i) {
if(ori[i]==t) {
pos=i;
break;
}
}
if(-1==pos) return ret;
ret=ori.substr(0,pos);
ori=ori.substr(pos+1);
return ret;
}
string simplifyPath(string path) {
vector<string> stk;
if(path[path.size()-1]!='/') path+="/";
while(!path.empty()) {
string str=split(path,'/');
if(str=="" || str==".") continue;
if(str=="..") {
if(!stk.empty()) stk.pop_back();
} else {
stk.push_back(str);
}
}
if(stk.empty()) return "/";
string ret("");
for(auto s : stk) {
ret=ret+"/"+s;
}
return ret;
}

leetcode - 72 Edit Distance

description

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

idea

动态规划,注意转移方程

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minDistance(string word1, string word2) {
int len1=word1.size();
int len2=word2.size();
int len=max(len2,len1);
int dp[len+1][len+1];
dp[0][0]=0;
for(int i=1;i<=len;i++) dp[i][0]=i;
for(int i=1;i<=len;i++) dp[0][i]=i;
for(int i=0;i<len1;i++) {
for(int j=0;j<len2;j++) {
if(word1[i] == word2[j]) dp[i+1][j+1]=min(min(dp[i+1][j] + 1, dp[i][j+1] + 1), dp[i][j]);
else dp[i+1][j+1]=min(min(dp[i+1][j] + 1, dp[i][j+1] + 1), dp[i][j] + 1); // insert, delete, repalce(equal)
}
}
return dp[len1][len2];
}

leetcode - 76 Minimun Window Substring

description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

idea

字符串的题,通常有两个常用伎俩:
前后指针,
用一个128的map来表示出现的字符的个数

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto c : t) map[c]++;
int counter=t.size(),begin=0,end=0,d=INT_MAX,head=0;
while(end<s.size()) {
if(map[s[end]] > 0) counter--;
map[s[end]]--;
end++;
while(counter==0) {
if(end-begin < d) {
d=end-begin;
head=begin;
}
if(map[s[begin]]==0) counter++;
map[s[begin]]++;
begin++;
}
}
return d==INT_MAX ? "" : s.substr(head,d);
}

description

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

idea

回溯,深搜

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
    bool dfs(vector<vector<char>>&board, string word, int count, int row, int col, vector<vector<int>>&visited)  
{
if (count == word.size() - 1)
return true;
visited[row][col] = 1;//已经访问
if (row + 1 < board.size() &&visited[row+1][col]==0&& board[row + 1][col] == word[count + 1] )
if (dfs(board, word, count + 1, row + 1, col, visited))
return true;
if (row - 1 >= 0 &&visited[row-1][col]==0&& board[row - 1][col] == word[count + 1] )
if (dfs(board, word, count + 1, row - 1, col, visited))
return true;
if (col + 1 < board[0].size() &&visited[row][col+1]==0&& board[row][col + 1] == word[count + 1] )
if (dfs(board, word, count + 1, row, col + 1, visited))
return true;
if (col - 1 >= 0 &&visited[row][col-1]==0&& board[row][col - 1] == word[count + 1] )
if (dfs(board, word, count + 1, row, col - 1, visited))
return true;
visited[row][col] = 0;
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
if (word.size() == 0)
return true;
int row = board.size();
int col = board[0].size();
vector<vector<int>>visited(row, vector<int>(col));
if (row == 0 || col == 0)
return false;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (board[i][j] == word[0])
{
if (dfs(board, word, 0, i, j, visited))
return true;
}
}
}
return false;
}

leetcode - 84 Largest Rectangle in Histogram

####description
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

idea

用一个栈来维护

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int largestRectangleArea(vector<int>& heights) {
int max_area = 0;
heights.push_back(0);
int sz = heights.size();
int stack[sz];
stack[0] = heights[0];
int stack_idx = 0;
int i = 1;
while (stack_idx >= 0 && i < sz) {
if (heights[i] >= stack[stack_idx]) {
stack[++stack_idx] = heights[i++];
continue;
}
while (stack_idx >= 0 && stack[stack_idx] > heights[i]) {
int area = stack[stack_idx] * (i - stack_idx);
if (area > max_area) { max_area = area; }
stack_idx--;
}
while (stack_idx < i) {
stack[++stack_idx] = heights[i];
}
i++;
}
return max_area;
}

leetcode - 85 Maximal Rectangle

description

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

idea

利用84题的思路来解题。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int blues(vector<int> hist) {
stack<int> index;
int res=0;
for(int i=0;i<hist.size();i++) {
if(index.empty() || hist[i]>hist[index.top()]) {
index.push(i);
} else {
while(!index.empty() && hist[index.top()]>hist[i]) {
int h=hist[index.top()];
index.pop();
int w=index.empty()?i:i-(index.top()+1);
int tmp=h*w;
res=max(res,tmp);
}
index.push(i);
}
}
return res;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int h=matrix.size();
if(h==0) return 0;
int w=matrix[0].size();
if(w==0) return 0;
int res=0;
vector<int> hist(w+1,0);
for(int i=0;i<h;i++) {
for(int j=0;j<w;j++) {
hist[j]=(hist[j]+1)*(matrix[i][j]-'0');
}
res=max(res,blues(hist));
}
return res;
}

leetcode - 94 Binary Tree Inorder Traversal

description

二叉树的中序遍历

idea

递归太简单了,用非递归,同时实现先序和后序。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 中序
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> nodes;
while(!nodes.empty() || root) {
while(root) {
nodes.push(root);
root=root->left;
}
TreeNode* x=nodes.top();
nodes.pop();
if(!x) continue;
res.push_back(x->val);
root=x->right;
}
return res;
}

// 先序
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> nodes;
while(!nodes.empty() || root) {
while(root) {
res.push_back(root->val);
nodes.push(root->right);
root=root->left;
}
TreeNode* x=nodes.top();
nodes.pop();
root=x;
}
}

// 后序
// 这段代码是抄的
// 后序遍历在决定是否可以输出当前节点的值的时候,
// 需要考虑其左右子树是否都完成了遍历。所以需要设置一个 lastVisit 游标。
// 若 lastVisit 等于当前考查节点的右子树,表示该节点的左右子树都遍历过了,
// 可以输出当前节点。并把 lastVisit 节点设置成当前节点,
// 将当前游标节点 node 设置为空,下一轮就可以访问栈顶元素。
// 否则,需要接着考虑右子树。
// 后续和中序很接近,只是在输出当前节点的时候要判断右子树是否已经完
// 成遍历。
public static void postorderTraversal(TreeNode root) {
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
TreeNode node = root;
TreeNode lastVisit = root;
while (node != null || !treeNodeStack.isEmpty()) {
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
//查看当前栈顶元素
node = treeNodeStack.peek();
//如果其右子树也为空,或者右子树已经访问
//则可以直接输出当前节点的值
if (node.right == null || node.right == lastVisit) {
System.out.print(node.val + " ");
treeNodeStack.pop();
lastVisit = node;
node = null;
} else {
//否则,继续遍历右子树
node = node.right;
}
}
}

leetcode - 95 Unique Binary Search Tree II

Description

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

idea

递归,树的题用递归都还挺简单的。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<TreeNode*> help(int start,int end) {
vector<TreeNode*> res;
if(start>end) {
res.push_back(nullptr);
return res;
}
for(int i=start;i<=end;i++) {
vector<TreeNode*> result_left=help(start,i-1);
vector<TreeNode*> result_right=help(i+1,end);
for(int j=0;j<result_left.size();j++) {
for(int k=0;k<result_right.size();k++) {
TreeNode* root=new TreeNode(i);
root->left=result_left[j];
root->right=result_right[k];
res.push_back(root);
}
}
}
return res;
}
vector<TreeNode*> generateTrees(int n) {
if(n<=0) return vector<TreeNode*>();
vector<TreeNode*> result=help(1,n);
return result;
}

leetcode - 96 Unique Binary Search Trees

Description

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.

Idea

和95类似的题,但是用相同的方法会超时。动归的方法比较好,因为在根节点左右两边的子树的数目只和节点有关,比如[1,2]和[3,4]的数目是一样的。对于任一个节点可以构建的树的数目就是左右子树数目相乘。

code

1
2
3
4
5
6
7
8
9
10
int numTrees(int n) {
vector<int> res(n+1);
res[0]=res[1]=1;
for(int i=2;i<=n;++i) {
for(int j=1;j<=i;++j) {
res[i]+=res[j-1]*res[i-j];
}
}
return res[n];
}

leetcode - 97 Interleaving String

description

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

idea

动态规划

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isInterleave(string s1, string s2, string s3) {
if(s1.size()+s2.size()!=s3.size()) return false;

bool dp[s1.size()+1][s2.size()+1]={false};
for(size_t i=0;i<s1.size()+1;i++) {
for(size_t j=0;j<s2.size()+1;j++) {
if(i==0 && j==0) dp[i][j]=true;
else if(i==0) dp[i][j] = (s2[j-1]==s3[i+j-1]) && (dp[0][j-1]);
else if(j==0) dp[i][j]=(s1[i-1]==s3[i+j-1]) && (dp[i-1][0]);
else dp[i][j]=(s1[i-1]==s3[i+j-1] && dp[i-1][j]) || (s2[j-1]==s3[i+j-1] && dp[i][j-1]);
}
}
return dp[s1.size()][s2.size()];
}

leetcode - 115 distinct subsequences

description

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Here is an example:
S = “rabbbit”, T = “rabbit”

Return 3.

ieda

动态规划。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numDistinct(string s, string t) {
int ss=s.size();
int ts=t.size();
int dp[ss+1][ts+1];
memset(dp,0,sizeof(dp));
for(int i=0;i<=ss;++i) dp[i][0]=1;
for(int i=1;i<=ss;++i) {
for(int j=1;j<=ts;++j) {
if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
else dp[i][j]=dp[i-1][j];
}
}
return dp[ss][ts];
}

leetcode - 123 best time to buy and sell stock III

description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

idea

动态规划。
保持到当前之前的四个状态,分别是:买了一个,卖了一个,买了两个,卖了两个。然后到当前元素,更新状态,有点像状态机。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices) {
int buy1,buy2,sell1,sell2;
sell2=0;
buy2=0x80000000;
sell1=0;
buy1=0x80000000;
for(auto p : prices) {
sell2=max(sell2,buy2+p);
buy2=max(buy2,sell1-p);
sell1=max(sell1,buy1+p);
buy1=max(buy1,-p);
}
return sell2;
}