给定数组,找出数组中4个数之和为目标数的所有不重复情况。
o(n^3*logn)险过。应该有更快的方法。
int cmp(int a,int b) {
return a < b;
}
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
sort(nu……
Best Time to Buy and Sell Stock系列第三题。之前两题分别说可以买卖任意多次和只能买卖一次。
此题是买卖两次。
买卖两次,找个节点分割问题,就把问题变成两个买卖一次的问题。但是超时。时间复杂度要到o(n^2)
另外一个思路。
按照买卖一次的方法处理正序,逆序
然后存储到达每个点时的max值。线性解法。
class Solut……
交换二叉搜索树的两个节点,要求复原。
不确定我的做法对不对,我只是在value的程度上把他们复原了。但是原文说不要破坏他们的结构?
想法很简单中序遍历+线性数组纠正
class Solution {
public:
void recoverTree(TreeNode *root) {
if(root == NULL)return ;
treeArray.clear();
inOrder(……
判断句子是否为回文:不区分大小写,不考虑非数字和字母的字符。
class Solution {
public:
bool isPalindrome(string s) {
for(int i = 0;i < s.length();i++) {
if(s[i] >= 'A' && s[i] <= 'Z') {
s[i] = 'a' + s[i] - 'A';
}
}
……
开始只能用map做。不过显然没有达到常数的空间的要求。
参考:
http://blog.unieagle.net/2012/09/20/leetcode题目:first-missing-positive/
自己diy的hash厉害。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
for(int i = 0;i < n;i++) {
if(A[i] <= 0)
……
sqrt模拟。注意两个int乘法可能越界。
class Solution {
public:
int sqrt(int x) {
//x >= 0 0 ~ x/2
if(x <= 0)return 0;
int left = 1;
int right = x / 2;
bsearch(left,right,x);
return ans;
}
private:
int ans;
void bsearch(int left,i……
K路归并排序。注意各种边界:比如指针为NULL或者vector空。
class Solution {
public:
ListNode <em>mergeKLists(vector&lt;ListNode *&gt; &amp;lists) {
if(lists.size() &lt;= 0)
return NULL;
while(lists.size() &gt; 1) {
……
不停的扩展当前能到达的最远的地方。
class Solution {
public:
int jump(int A[], int n) {
if(n <= 1)return 0;
int min = -1;
int max = 0;
int maxstep = 0;
int count = 0;
while(true) {
count++;
for(int i = min+1;i <= max……
给定多个字符串,找出那些Anagrams的字符串组。
Anagrams:eat ate eta
这个题 排序,再排序。
int cmp(int a,int b) {
return a < b;
}
struct Item {
int index;
string val;
};
int cmpitem(Item a,Item b) {
return a.val < b.val;
}
class Solution {
public:
vector anagrams(vector &……
在数组中找寻一系列的数,之和为target。
搜索+剪枝。注意去重复和升序。
int cmp(int a,int b) {
return a < b;
}
class Solution {
public:
vector<vector<int>>ans;
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
ans.clear();
……