0%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.empty())
return 0;
vector<int> f(nums.size()), g(nums.size());
int ret = f[0]=g[0]=nums[0];
for(int i=1;i<nums.size();++i)
{
f[i]=max(nums[i], max(g[i-1]*nums[i], f[i-1]*nums[i]));
g[i]=min(nums[i], min(g[i-1]*nums[i], f[i-1]*nums[i]));
ret = max(f[i], ret);
}
return ret;
}
};

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
foo(root);
return ret;
}
private:
bool ret = true;
TreeNode* pre=NULL;
void foo(TreeNode* root)
{
if(root==NULL || !ret)
return;
foo(root->left);
if(pre==NULL)
pre=root;
else{
if(pre->val>=root->val)
{
ret=false;
return;
}
pre=root;
}
foo(root->right);
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
string multiply(string num1, string num2) {
int len = num1.size() + num2.size();
vector<int> nums(len, 0);
for(int i=num1.size()-1;i>=0;--i)
for(int j=num2.size()-1;j>=0;--j)
nums[i+j+1]+=(num1[i]-'0')*(num2[j]-'0');
for(int i=len-1;i>0;--i)
{
nums[i-1]+=nums[i]/10;
nums[i]=nums[i]%10;
}

string ret;
int idx=0;
while(nums[idx]==0 && idx!=len-1)
++idx;
while(idx<len)
ret+=(nums[idx++]+'0');
return ret;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
stack = []
items = path.split('/')
for item in items:
if item=='.' or not item:
continue
elif item=='..':
stack = stack[:-1];
else:
stack.append(item)
return '/'+'/'.join(stack)

利用stack保存下标,这些下标对应的高度是单调递增的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
heights.append(0)
ret = 0
stack =[]
for i, h in enumerate(heights):
while stack and heights[stack[-1]]>h:
idx = stack.pop()
height = heights[idx]
w = i if not stack else i-stack[-1]-1
ret = max(ret, height*w)
stack.append(i)
return ret

先排序,然后按照最长子序列的方法找结果。

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
class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
if(envelopes.size()<2)
return envelopes.size();
sort(envelopes.begin(), envelopes.end(), [](pair<int,int> &lhs,pair<int,int> &rhs){
if(lhs.first!=rhs.first)
return lhs.first<rhs.first;
else return lhs.second<rhs.second;
});
vector<int> dp(envelopes.size(), 1);
int ret=1;
for(int i=0;i<envelopes.size();++i)
{
for(int j=i-1;j>=0;--j)
{
if(envelopes[j].first<envelopes[i].first &&
envelopes[j].second<envelopes[i].second)
{
dp[i]=max(dp[j]+1,dp[i]);
}
ret=max(dp[i],ret);
}
}
return ret;
}
};

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
class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [](pair<int, int> lhs, pair<int, int> rhs){ return lhs.first+lhs.second < rhs.first+rhs.second;};
priority_queue<pair<int, int> , vector<pair<int, int>>, decltype(cmp)> q(cmp);

for(int i=0;i<nums1.size() && i<k; ++i)
for(int j=0;j<nums2.size()&& j<k; ++j)
{
if(q.size()<k)
{
q.push(make_pair(nums1[i], nums2[j]));
}
else if(q.top().first+q.top().second > nums1[i]+nums2[j])
{
q.pop();
q.push(make_pair(nums1[i], nums2[j]));
}
}
vector<pair<int,int>> ret;
while(!q.empty())
{
ret.push_back(q.top());
q.pop();
}

return ret;
}
};

直接二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool isPerfectSquare(int num) {
long long beg=1, end=num;
while(beg<=end)
{
long long mid = (end-beg)/2+beg;
auto t = mid*mid;
if(t==num)
return true;
else if(t<num)
{
beg=mid+1;
}
else
{
end=mid-1;
}
}
return false;
}
};

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
auto end = findEnd(head);
if(end==NULL)
return NULL;
auto lhs=head, rhs=end->next;
int llen=length(lhs, end), rlen=length(rhs, end);
if(llen<rlen)
{
swap(llen, rlen);
swap(lhs, rhs);
}
while(llen>rlen)
{
lhs=lhs->next;
--llen;
}

while(lhs!=rhs)
{
lhs=lhs->next;
rhs=rhs->next;
}
return lhs;
}

private:
ListNode *findEnd(ListNode *head)
{
if(head==NULL || head->next==NULL)
return NULL;
auto slow=head, fast=head->next;
while(slow && fast)
{
if(slow==fast)
return slow;
slow=slow->next;
if(fast->next)
fast=fast->next->next;
else
return NULL;
}
return NULL;
}

int length(ListNode *head, ListNode *tail)
{
if(head==NULL)
return 0;
if(head==tail)
return 1;
else return 1+length(head->next, tail);
}
};

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
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
unordered_map<string, vector<string>> map;
return foo(s, wordDict, map);
}

vector<string> foo(string s, unordered_set<string> &wordDict, unordered_map<string, vector<string>> &map)
{
if(map.find(s)!=map.end())
{
return map[s];
}

vector<string> res;
if(s.length()==0)
{
res.push_back("");
return res;
}

for(string word: wordDict)
{
if(startsWith(s, word))
{
auto subList=foo(s.substr(word.length()), wordDict, map);
for(auto sub: subList)
res.push_back(word+(sub.size()==0?"":" ")+sub);
}
}
map[s]=res;
return res;
}

bool startsWith(string lhs, string rhs)
{
if(lhs.length()<rhs.length())
return false;
for(int i=0;i<rhs.length(); ++i)
if(lhs[i]!=rhs[i])
return false;
return true;
}
};