lld2006

leetcode对题目做了一些改动， 现在已经不要求ascending order了

其实这个题目可以把time complexity 降到 O（logn）具体的做法是利用矩阵乘法， [[1,1][1,0]] 不过在这里没什么大的意思罢了。

解法1可以再check一下m n的大小， 来改善space complexity。

解法2 比较有意思。 补充两句。 start时间和end时间sort后， start[i] end[i]说明前面i对间隔 和后面的不再有交集， 可以输出interval了， 因为每个end[i]对应的时间都会小于结束时间， 现在既然已经找到i个start时间， 他们不可能和start[i+1]有交叠。 start[i+1] < end[i]说明end[i+1]

感觉还是利用bit操作最方便， code也简单。 class Solution { public: int totalNQueens(int n) { return dfs(0, 0, 0, 0, n); } int dfs(int row, int col_flag, int diag_flag, int off_diag_flag, int nrow){ if(row ==nrow)...

可以稍微改进一下拿数字的方法，可以一直push candidate 直到sum 要大于target了。 速度上稍微快一点，stack也可以少用一点。 ``` class Solution { public: vector combinationSum(vector& vn, int target) { vector vSeq; helper(0, 0, vn, vSeq, target); return results_; } void helper(int start, int...

推荐一下论坛高票code, stack 只记录所有invalid的parenthesis的位置， 每两个invalid位置之间都是valid的。index = size 和index=-1 也都当成invalid。 具体code如下 class Solution { public: int longestValidParentheses(string s) { stack st; for(int i = 0; i < s.size(); ++i){ if(st.empty() || s[i]...

可以做些优化。 1， 逐行检查， 各用一个n bit的flag来检查diagonal, offdiag以及column被占用的情况。如果某列满足均未占用， 在flag上该列做标记。 下一行做检查前， 将主对角线flag右移一位， 付对角线flag左移一位即可 2，逐行检查时， 第一行的col只用检查一半， 另外一半可以通过对称性得到（没有写在code中） 3, github 对贴code不友好啊， 括号什么的我就不改了。 看source可以看到正确的。 class Solution { public: vector solveNQueens(int n) { vector columns(n, -1);//which column...

1, 加上#号后，最左边和最右边都是#号， 总长度是2*radius - 1， 其中 #个数是 radius， 字符的长度是radius-1； 2， 中心是 center，左边 右边各有radius-1 个字符， 所以最左边的字符（不包含#号）的index是center-（radius-1）+1 但是字符的index 是2 4 6 8 ..., 所以最长回文字符串最左边的字符在不包含#号的index就是 (center-radius+2-2)/2; 这样就不需要归纳了，

我是这样理解的， 如果把所有堆排上号，1，2，3，..., 2k, 第一个取石头的人可以选择取1，3，5，7， 2k-1, 或者2，4，6，8， ..., 2k，而这两堆数目是不等的， 所以选择石头总数多的那堆即可。 之所以可以一直取奇数号或者偶数号也很好理解，因为堆数是偶数所以第一个人取的时候是可以选择奇偶的， 而第二个人是不能选择的。 如果最开始取1， 那么第二个人一定得取2或者2k取完之后一端是奇数号， 一端是偶数号。 所以第一个人总可以选择奇数或者偶数号的堆。