soulmachine / leetcode Goto Github PK

第一章编程技巧里“阀值”应该为“阈值”，这个在知乎上看到过两者区别。
http://www.zhihu.com/question/20642950

The test set also includes the non-alphabet characters, thus the ASCII_MAX should be defined as 256, and s[i] - 'a' is not necessary.
The current code can not pass the OJ. I made minor changes as below with accepted:

class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int ASCII_MAX= 256;
int last_pos[ASCII_MAX];
fill(last_pos, last_pos+ASCII_MAX, -1);
int max_len = 0, len = 0;
for(int i=0; i<s.size(); i++,len++){
if(last_pos[s[i]] >= 0){//find a duplicated char
max_len = max(len, max_len);
i = last_pos[s[i]] + 1;//start from the next possible solution
len = 0;
fill(last_pos, last_pos+ASCII_MAX, -1);
}
last_pos[s[i]] = i;
}
max_len = max(len, max_len);
return max_len;
}
};

I do not think the time complexity of your code is O (n) but I am not sure what it should be.

字体的百度网盘链接已经失效了，能不能重新补一个？

Time limit exceeded.

linear solution:
https://oj.leetcode.com/discuss/20176/concise-in-place-solution-with-linear-time

Binary search:
https://oj.leetcode.com/discuss/19000/c-my-binary-search-solution

In a case the code is not right: if gap == num[i] then you will get result[0]=result[1]

++inc may be better, although inc++ could AC.

解决了超时的问题。应该使用multi-pass来两两merge

您好，Java目录下没有内容，是还没有来得做么？
我最近正在使用您总结的教材来刷题，我是用Java的，可以正好补充Java的版本。

请问懒人镜像版的root密码是什么啊？

it says O(N^2), but I think it should be O(1) since the size is fixed.

https://github.com/soulmachine/leetcode/blob/master/C%2B%2B/chapString.tex#L402
the iteration direction for inner loop is not correct and should be
for (int j = i - 1; j >= 0 ; j--) {

The recursive version can be accepted on leetcode, but it's not a O(N) solution.
Please consider cases from wildcard matching:

abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb
.*aa.*ba.*a.*bb.*aa.*ab.*a.*aaaaaa.*a.*aaaa.*bba

This case never return on my machine.

问题word break2 里
// path[i][j] 为 true,表示 s[j, i) 是一个合法单词,可以从 j 处切开
// 第一行未用
vector<vector > prev(s.length() + 1, vector(s.length()));

这里的path[i][j]为true....应该改为prev[i][j]...

Suppose p is a pointer. The running time for if(p==nullptr) and if(!p) are different in Leetcode. Is this a bug in Leetcode.

P44页讲到了Remove Duplicates from Sorted List的迭代解法，其中的一段代码片段：

for (ListNode *prev = head, *cur = head->next; cur; cur = cur->next) {
    if (prev->val == cur->val) {
        prev->next = cur->next;
        delete cur;
    } else {
        prev = cur;
    }
}

既然delete cur语句已经将cur删除，为什么还可以在for的条件语句里执行cur = cur->next?

PS.感谢作者辛勤的劳动为我们带来了如此有价值的作品，再次感谢:）

2ms with the following sol.
Optimized the combination part.

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(!m || !n) return 0;

        long long a = 1,b = 1;

        // find the max
        int min = m < n ? m : n;
        int max = m > n ? m : n;

        // find (m+n-2)!/max{(m-1)!,(n-1)!}
        for(int i=max;i<=m+n-2;++i)  a *= i;
        // min{(m-1)!,(n-1)!}
        for(int i=1;i<=min-1;++i)    b *= i;

        return a/b;
    }
};

这个题目要求in-place，但目前的解好像都不是空间O(1)的。我有个O(1)空间的解想放上来但看到其他帖子里说这个repo是private了。现在可以pull request了么？

Consider the case: Only root node, whose value is INT_MAX. The code will output false instead of true.

Solution: Use LLONG_MAX to replace INT_MAX.

class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, LLONG_MIN, LLONG_MAX);
}
bool isValidBST(TreeNode* root, long long lower, long long upper) {
if (!root) return true;
return root->val > lower && root->val < upper
&& isValidBST(root->left, lower, root->val)
&& isValidBST(root->right, root->val, upper);
}
};

http://q.weibo.com/1312378

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
yeah?

提供的代码似乎是题目Plus One的答案，和题目Sqrt(x)没有关系

The input string could contain characters other than a-z. So we need to change the size of last array from 26 to 256.

leetcode在陆续增加新题。持续更新：https://github.com/ghostrong/leetcode, C++源码, .cpp 文件

OJ没法通过, 如果linked list: 1->NULL or 1->1-> NULL

In the end of

leetcode/C++/chapDFS.tex line263
一个$m$行，$n$列的矩阵，机器人从左上走到右下总共需要的步数是$m+n-2$，其中向下走的步数是$m-1$，因此问题变成了在$m+n-2$个操作中，选择$m–1$个时间点向下走，选择方式有多少种。即 $C_{m+n-2}^{m-1}$ 。

$C_{m+n-2}^{m-1} would present like

m - 1
C m + n - 2

But it should be

m + n - 2
C m - 1

Right? Or your country have different usage of C(m, n)?

If it is a typo, please change it to

一个$m$行，$n$列的矩阵，机器人从左上走到右下总共需要的步数是$m+n-2$，其中向下走的步数是$m-1$，因此问题变成了在$m+n-2$个操作中，选择$m–1$个时间点向下走，选择方式有多少种。即 $C_{m-1}^{m+n-2}$

Hi, I gotta to run your solution on github.
However, I got a TLE when submit to online judge.
The corresponding testcase is something like
[[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18] ... [19999,20000]], [0,20001]]
It cause multiple erase which make your algorithm in worst case O(n^2).
A O(n) time, O(n) space solution that use extra memory to save the result can basically pass the oj.

for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)

应该改成
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)

至少我目前测试的结果是这样。

RT

Leetcode has added the new case for this problem, when overflow occurs, need to return INT_MAX, the current code can NOT be accepted. I adjust the return code as this and accepted.

    long long ret =    ((dividend^divisor) >> 31)?(-multi): multi;

    if (ret > INT_MAX)
        return INT_MAX;
    else
        return ret;

第一章第一段：“应判断两者之差的绝对值f(a,b)是否小于某个阀值“。其中“阀值”是一个错误的用词，正确的用法是“阈值”。“阈“音”玉“，其内部是”或“不是”伐“。

_解题思路: 递归
这道题没什么特别的地方，现在这里简单的分析一下解题思路，从根节点往下，我们要判断三个条件.

1. 左右两个节点的大小是否相同.
2. 左节点的左孩子是否和右节点的右孩子相同.
3. 左节点的右孩子是否和右节点的左孩子相同.
   ，如果以上三个条件对于每一层都满足，我们就可以认为这棵树是镜像树._

但这并不是树是对称树的所有条件，比如
1
/
2 2
/ \ /
1 2 2 1
/ \ / \ / \ /
1 3 3 1 1 2 2 1

所有的层都符合这三个条件，但显然不是对称树
下一层满足了条件，并不等于上层也满足。

觉得很可惜，这个题解很受用，希望可以继续更下去

I have a doubt about the complexity of the recursive method. This should not be n^6. The worst case should be 6^n instead of n^6.

in 2.1.18, gray code, the link to the wikipedia page is wrong.

the link points to http://en.wikipedia.org/wiki/Gray_coded which should be http://en.wikipedia.org/wiki/Gray_code

Code 2: There isn't any occur variable in this solution. I am confused by what you are talking about.

N 个节点的 BST 的形态为 Catalan 数的第 N 项，即 C(2n, n) / (n + 1) => (2n)! / n! / (n + 1)，最后可以写成这样：

class Solution {
 public:
  int numTrees(int n) {
    long ans = 1;
    for (int i = 1; i <= n; ++i) ans += ans * n / i;
    return ans / (n + 1);
  }
};

Hi, Your solution don't take care this case: '+-1'.
I am working on python solutions. I will submit a pr for this after I finish my work(weeks later).
This is a reminder. Or you can take care of it yourself.

Line 16: return total>=0 ? j+1 : -1
Should be (j+1)%gas.size(), so that we will return 0 instead of N in some cases.

The problems description is the same as Same Tree
=.=

In LRU Cache, after moving a node in the list to the front, it updated cacheMap[key] to cacheList.begin().

But I don't think the iterator to the node will be changed after splicing.

Using function mergeTwoLists will lead to Time limit exceeding. Please use min heap.

原题描述是
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:
1
/
2 2
/ \ /
3 4 4 3

But the following is not:
1
/
2 2
\
3 3