haoel / leetcode Goto Github PK

我刚看了这个问题Palindrome Number ,看到这个条件(Do this without extra space.)时,我直接停止思考了,但我看您的解答后,更加不解,这个条件应该怎么理解.这里的意思是不是说空间复杂度是1呀

在3Sum.cpp第33行
Simlar like "Two Number" problem, we can have the simlar solution.
Simlar少了个i

Hi,

I want to work on my own like your project. And I also want to place the problem on top of my own answer. But I don't know how to use the scraper you wrote.( Although it is only one line..) Do you mind write a comment or a demonstration about to how to use this script called "problem.sh"?

Cheers!

findMinimumInRotatedSortedArray.II.cpp line52,53
In this clause, num[low] always less than num[mid], but if num[low] is equal to num[mid], how then?

I have tried to reinstall xidel by query_problem.sh, but they are all failed, I think we can update it and find some substitute

class MinStack {
public:
    void push(int x) {
        stack_.push_front(x);
        if (minStack_.empty() || x < *minStack_.front()) {
            minStack_.push_front(&stack_.front());
        }
    }
    void pop() {
        if (&stack_.front() == minStack_.front()) {
            minStack_.pop_front();
        }
        stack_.pop_front();
    }
    int top() {
        return stack_.front();
    }
    int getMin() {
        return *minStack_.front();
    }
private:
    deque<int> stack_;
    deque<int*> minStack_;
};

This puzzle really sucks for C++ programers. :-( However the OJ just provide the Java solution.

Thank you for your solutions

https://github.com/haoel/leetcode/blob/master/src/findMinimumInRotatedSortedArray/findMinimumInRotatedSortedArray.cpp
Not worked for this test case
{ 2, 3, 1, 4, 5, 6, 7 }

https://github.com/haoel/leetcode/blob/master/src/sortList/sortList.cpp

return mergeTwoLists(sortList(head), sortList(p2));

It will be really helpful for people that want to contribute if you could include the contribution guide.
It will be really helpful if you could include these topic:

1. language wish to implement
2. code format
3. file format

Hello Haoel! At very beginning, I really like what comments.sh does, thanks. I got some problems with the scripts. Following is the messages and info. Do you have any advice for it?

[root@localhost leetcode]# ./comments.sh https://oj.leetcode.com/problems/largest-number/ largestNumber.cpp
./comments.sh: line 80: /usr/bin/xidel: cannot execute binary file
LargestNumber.cpp updated !

line 80: xidel ${leetcode_url} -q -e "css('div.question-content')" |
xidel ${leetcode_url} -q -e "css('div.question-content')" |
grep -v ' ' |sed '/^$/N;/^\n$/D' |
sed 's/^/ * /' | sed "1i/$(printf '%.0s' {0..80}) \n * " |
sed "$a \ $(printf '%.0s_' {0..80})_/\n" > /tmp/tmp.txt

[root@localhost leetcode]# ls -t
LargestNumber.cpp xidel comments.sh
[root@localhost leetcode]# ls xidel/
changelog install.sh readme.txt xidel xidel-0.8.4.linux64.tar.gz

Following is what the scripts gen:
// Source : https://oj.leetcode.com/problems/largest-number/
// Author : Edward Wang
// Date : 2015-02-04

See https://leetcode.com/problems/nth-digit/

vector<vector > threeSum(vector &num) {

vector< vector<int> > result;

//sort the array, this is the key
sort(num.begin(), num.end());

int n = num.size();

for (int i=0; i<n-2; i++) {
    //skip the duplication
    if (i>0 && num[i-1]==num[i]) continue;
    int a = num[i];
    int low = i+1;
    int high = n-1;
    while ( low < high ) {
        int b = num[low];
        int c = num[high];
        if (a+b+c == 0) {
            //got the soultion
            vector<int> v;
            v.push_back(a);
            v.push_back(b);
            v.push_back(c);
            result.push_back(v);
            // Continue search for all triplet combinations summing to zero.
            //skip the duplication
            while(low<n && num[low]==num[low+1]) low++; 
            while(high>0 && num[high]==num[high-1]) high--; 
            low++;
            high--;
        } else if (a+b+c > 0) {
            //skip the duplication
            while(high>0 && num[high]==num[high-1]) high--;
            high--;
        } else{
            //skip the duplication
            while(low<n && num[low]==num[low+1]) low++;
            low++;
        } 
    }
}
return result;

}

The below line code may have problem,
"while(low<n && num[low]==num[low+1]) low++; "
Why not "while(low<n -1 && num[low]==num[low+1]) low++; "

Given the length n, you only need to loop about n~2n times if k is much more bigger than n.

The code used recursion, the space may be O(n). I searched for the O(1) solutions, and found that they all use morris traversal to satisfy O(1) space complexity. So, the only different thing is how to traverse the tree. But, any better idea?

leetcode solution.

in row 62,63
should remove the +1

There is no swap method included, while you use swap(headA, headB).

For strStr1 in "https://github.com/haoel/leetcode/blob/master/src/strStr/strStr.cpp", below case will get a complexity of O(m*n)
strStr1("aaaaaaaaaaaaaaaaaa","aaaaaab");

If we have [1 10 50 90] and we trying to find 100.
Wouldn't map find return the 50 which have just inserted already?

Thanks,
Werror

Hello,
In the explanation of 'House Robber,' you mentioned
/*

• Dynamic Programming
  *
• We can easy find the recurive fomular:
  *

• dp[n] = max( 
  

•                dp[n-1],   // the previous house has been robbed. 
  

•                dp[n-2] + money[n]  // the previous house has NOT been robbed.
  

•            )
  

• The initalization is obvious:

• dp[1] = money[1]
  

• dp[2] = max(money[1], money[2])
  

  */

I think its a bit misleading . Actually dp[n-1] does not mean "the previous house has been robbed". For example : given 'money' as [2,1,3,5], 'dp' would be [2,2,5,7] . As you can see dp[1]=2, therefore when you calculate dp[2], dp[1] does NOT mean the second house(index 1) has been robbed.

The correct explanation should be : dp[n] stands for 'the maximum amount of money in total you can rob so far". dp[n-1] means "if you do NOT rob the current house [n] , what you can get so far",

But still, your ideas have impressed and helped me a lot. Thanks !

Code is right, but here is a type error in line 39

2) find the first number from n-1 to i which >= num[i-1]

should be

2) find the first number from n-1 to i which > num[i-1]

.

https://github.com/zhjb7/leetcode/blob/master/algorithms/cpp/longestCommonPrefix/longestCommonPrefix.cpp

longestCommonPrefix : 13 seconds.
longestCommonPrefix_zhjb7: 5 seconds.
longestCommonPrefix_zhjb7_another: 5 seconds.

Is any errors in my code ?

I’d thought that memset initialize bytes but not integers?

Dear,
I'm new in programming and need of help for resolve the problem.

The sales data of a company's sales is stored in a file Txt that obeys the following format: branch(Filial), year_month, sales_count, total_dend.

Make a program that loads the data from the file into data structures and allows

Answer expressions such as:

1. total sales of subsidiaries with codes between 10 and 20

2. total sales of subsidiaries with codes between 10 and 20 in the months of Jan / 17 to Jun / 17

3. total sales of all branches(Filial) in the months of Aug / 17 to Oct / 17

Someone can help? Please.

It's confusing that char* ph does not move with the same offset as char* haystack does.

This is my modified solution:

class Solution {
public:
    char* strStr(char* haystack, char* needle) {
        if (!*needle) return haystack;  // ["a", ""]
        char* ph = haystack;
        char* pn = needle;
        while (*ph && *pn) { ph++; pn++; }
        if (!*ph && *pn) return NULL;  // ["", "a"]
        ph = ph - 1;
        while (*ph) {
            char* px = haystack;  // start of the rest part
            char* py = needle;
            int step = 0;
            while (*py && *px && *px == *py) {
                px++; py++;
                if (step == 0 && *px == *needle) step = px - haystack;
            }
            if (!*py) return haystack;
            step = step > 0 ? step : 1;
            haystack += step;
            ph += step;
        }
        return NULL;
    }
};

i just paste ur code to leetcode. the result is "Line 42: expected ‘}’ at end of input"。
it confused me！becaue the total line is 34。

1.Two Sum's difficulty is easy

作者你好，我看 pull requests 里边还有好多尚未 merge commit 的代码，请问一下，您是最近工作比较忙吗？如果有网友提交了代码，您大概几天后可以 review 并 merge？

我的思路是:
如果有N列, 就循环N次, 每次把第i列打印出来.

read -a array <<< $(head -n1 file.txt)
for index in "${!array[@]}"
do
    awk '{if (NR==1) space=""; else space=" "} {printf "%s%s",space,$'$((1+index))'} END {printf "\n"}' file.txt
done

但是报错Memory Limit Exceeded.

看你的代码是要把整个文件都写入s这个数组. 感觉内存使用上不会更少?

为什么我的回答报了"Memory Limit Exceeded", 这个报错到底代表什么?
这个题目的讨论区也有不少人有这个疑惑, 但还没有回答.
我只是直觉上觉得awk应该是读一行然后处理再读下一行. 为什么反而我的代码出错了呢? 耗哥能否帮忙解疑?

During to notes:

You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.

And you use back() for class Stack's top() function. I think it's not perfect.

 // Get the top element.
        int top() {
            return nums.back();
        }

BTW, thanks for your sharing.

maybe we can add gtest for ut
e.g. https://github.com/BryanYangZL/LeetCode

请问一下如果这个节点正好是尾节点的时候该怎么处理啊？

In code

for (int i=0; i<rowIndex; i++){
        for(int j=i+1; j>0; j--){
           v[j] += v[j-1];
        } 
    }

when i equals rowIndex-1 and j equals rowIndex, the v doesn't have the element at v[j].

If n is greater than the count of listnode, it will run coredump.
The line 43 must swap with line 44.

in reverse() (line 62), u forgot to judge whether y is over/underflow ,so can not ac

In this algorithms where the solution file is divideTwoInt.cpp,when the input is "-2147483648 -1",the array named bit_num out of bounds because the indicator i can increase to 32;

We can modify the size of the array to 33 or other ways avoid this error occurring.

Have a look at: https://github.com/haoel/leetcode/blob/master/src/searchInsertPosition/searchInsertPosition.cpp#L28

int mid = low +(high-low)/2;

would occur overflow. try to change to this:

int mid = (high-low)/2;

This algorithm failed when there are successive characters in T, e.g. S="rabbbit" and T="rabbit".

I think there is no easy way to fix it.

Hi @haoel

Thanks for sharing the code @
https://github.com/haoel/leetcode/blob/master/algorithms/binaryTreeRightSideView/binaryTreeRightSideView.cpp

Just FYI, the solution of mine is a little bit shorter (https://github.com/zhuangh/OJ/blob/master/leetcode/cpp/binaryTreeRightSideView.cpp)
than yours. The number of lines is 1/3 of the solution you shared.

The idea is to use DFS to do pre-order traversal of the mirror tree. At the same time, use an array to mark current level, so that we can keep from putting wrong element into the result vector.

Thank you

Your github repo is very good. Would you consider adding any license? Especially for people that want to git clone this repository.

#include
class Solution {
public:
int reverse(int x) {
int n;
long ret = 0; // in case overflow
while(x != 0){
n = x % 10;
ret = ret * 10 + n;
if(ret > INT_MAX || ret < INT_MIN){
return 0;
}
x = x / 10;
}
return ret;
}
};

Ever since leetcode org changed their website, the regx in the comment.sh is kinda broken. Any idea to fix it?

Your DP solution is not really efficient.

I can provide two test cases:

unordered_set<string> dict = {"a","aa","ab"};
string s = "babaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

unordered_set<string> dict = {"a","aa","ba"};
string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabab";

Will help people, like me, to see the locked questions, if possible.

It seems that your map<int, int> cache violates the constraint.

Thanks