leetcode/230KthSmallestElementInaBST

Posted on 2020-01-09

Kth Smallest Element In a BST

找到二叉树中, 第 n 个最小的节点

my solution

可以一步一步找它的最小节点, 追踪的问题, 可以交给 stack

func kthSmallest(root *TreeNode, k int) int {
    // if root == nil {
    //     return 0
    // }
    stack := []*TreeNode{root}

    for root.Left != nil {
        stack = append(stack, root.Left)
        root = root.Left
    }

    pos := len(stack) - 1

    for foot := 1; foot != k; foot++ {
        // if cur.Right != nil then next is cur.Right.Left(bottom)
        if stack[pos].Right != nil {
            // i really need stack...
            if len(stack) > pos + 1 {
                stack[pos + 1] = stack[pos].Right
            } else {
                stack = append(stack, stack[pos].Right)
            }
            pos++

            for stack[pos].Left != nil {
                if len(stack) > pos + 1 {
                    stack[pos + 1] = stack[pos].Left
                } else {
                    stack = append(stack, stack[pos].Left)
                }
                pos++
            }
        } else {
            // if cur.Right == nil then next is last biger value
            old := stack[pos].Val

            // hope BST don't have repetitive value... 
            for stack[pos].Val <= old {
                pos--
            }
        }
    }

    return stack[pos].Val
}

查找下一节点 (next) 可以这么描述:

如果当前节点 (cur) 有右子节点, 则 next 为右子节点的左根节点

否则, next 为上一个大于当前节点值的节点

这是用递归来实现的, 为了追踪, 使用了 stack

(我好希望 go 能提供一个标准的 stack, 这样代码可以更加简洁. 或许是提供了, 但我不知道?)

一次成功, 真好

the best solution

func kthSmallest(root *TreeNode, k int) int {
    res = 0
    helper(root,k,1)
    return res
}
var res int

func helper(root *TreeNode, k int, i int) int {
    cur := 0 
    if root.Left != nil {
        prev := helper(root.Left, k, i)
        cur = prev + 1
    } else {
        cur = i
    }

    if cur == k {
        res = root.Val
    }

    if root.Right != nil && cur < k {
        return helper(root.Right, k, cur+1)
    }
    return cur
}

emm, 他使用了递归, 用递归来追踪, 可以不用显式追踪数据了, 挺好

leetcode/25ZReverse_Nodes_in_k-Group

Posted on 2020-01-09

25. Reverse Nodes in k-Group

给定一个链表, 每次反转链表数量为k的节点, 然后返回更改后的链表

k是一个正整数, 小于等于链表的长度, 如果链表的长度不是k的整数倍, 最后遗漏的节点保持原样

my code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head) return NULL;

        ListNode* ret = head;
        while (head && head->next) {
            int kt = k;
            ListNode* headt = head;
            vector<int> vec;

            vec.push_back(headt->val);
            while (--kt && head->next) {
                head = head->next;
                vec.push_back(head->val);
            }
            head = head->next;

            if (kt) break;
            reverse(headt, vec);
        }

        return ret;
    }

private:
    void reverse(ListNode* head, vector<int>& vec) {
        for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); ++it) {
            head->val = *it;
            head = head->next;
        }
    }
};

这道题的思路很清晰, 感觉不应该是hard难度的题

简单地将链表每一部分分开, 然后调用反序函数就可以了

可以优化的点是 while 那里, 以及我可以不用在 while 中判断, reverse 应该能够正常处理元素数量不同的情况

那么我在最后做一次判断, 将最后一次不用修改的还原就可以了, 这样可以省去 while 中的判断逻辑

速度上来说还算不错, 但是资源使用率上就很堪忧了

dalao’s code

class Solution {
public:
    ListNode* reverse(ListNode* first, ListNode* last)
    {
        ListNode* prev = last;

        while ( first != last )
        {
            auto tmp = first->next;
            first->next = prev;
            prev = first;
            first = tmp;
        }

        return prev;
    }

    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        auto node=head;
        for (int i=0; i < k; ++i)
        {
            if ( ! node  )
                return head; // nothing to do list too sort
            node = node->next;
        }

        auto new_head = reverse( head, node);
        head->next = reverseKGroup( node, k);
        return new_head;
    }
};

这个做法和我的想法基本相同, 但是在细节上的处理很好

首先, 他采用的递归, 这样代码更加简洁易懂

其次循环中是更改链表的指向, 而不是赋值, 这样功能性更强

leetcode/300LongestIncreasingSubsequence

Posted on 2020-01-09

300 Longest Increasing Subsequence

找出数组中最大的增长数量

my solution (8ms, 66.89%)

emm… 考虑将每一个下降的 slice 视为一个数组, 因为这些数组只可能产生一个值

而再将这些 slice 循环, 每次从当前节点选择最小的数字, 每次前进时选择一个最小的比上一个节点大的数字

然后计数, 一次遍历下来就得到了最大增长序列的长度

复杂度是一次 O(n) 的遍历 + 切片之后数组长度的遍历, 接近 O(n2)

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    stairs := [][]int{}
    temp := []int{}
    prev := 0x7fffffff

    for _, v := range nums {
        if v < prev {
            temp = append(temp, v)
        } else {
            sort.Ints(temp)
            stairs = append(stairs, temp)
            temp = []int{v}
        }

        prev = v
    }
    sort.Ints(temp)
    stairs = append(stairs, temp)

    size := len(stairs)
    count, ret := 1, 0
    for i := 0; i < size; i++ {
        prev = stairs[i][0]

        for i2 := i + 1; i2 < size; i2++ {
            ind, size2 := 0, len(stairs[i2])
            for ind < size2 && stairs[i2][ind] <= prev {
                ind++
            }

            if ind >= size2 || stairs[i2][ind] <= prev {
                continue
            }
            count++
            prev = stairs[i2][ind]
        }
        ret = max(ret, count)

        if ret >= size - i {
            break
        }
        count = 1
    }

    return ret
}

emm… 代码有点长

8ms 那个是我做的, 0 不是

best solution

func binsearch(stack []int, x int) (r int) {
    l, r := 0, len(stack)
    for l < r {
        m := l + (r - l) / 2
        if stack[m] >= x {
            r = m
        } else {
            l = m + 1
        }
    }
    return
}

func lengthOfLIS(nums []int) (r int) {
    stack := make([]int, 0)

    for _, num := range nums {
        r := binsearch(stack, num)
        if r < 0 {
            stack[0] = num
        } else if r == len(stack) {
            stack = append(stack, num)
        } else {
            stack[r] = num
        }
    }

    return len(stack)
}

简单来说就是通过不断将数组按照升序添加到 slice 里面 (我将其称作 slice, 因为它的行为不太像 stack)

slice 的元素只有两种情况会变更:

要么有更小的元素覆盖, 要么比 slice 中所有元素都大, 然后 append

因为题目要求的只要长度, 所以即使 slice 里面元素可能是错误的, 也没关系, 长度是对的

这样的复杂度是 O(n), 其实原理还是挺容易理解的, 为什么我就没想到呢 = =

leetcode/31ZNextPermutation

Posted on 2020-01-09

31 Next Permutation

简单来说就是找下一个比当前数字更大的数, 如果没有, 就重新排序

my code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        size_t size = nums.size();

        for (int i = size - 1; i > 0; --i) {
            if (nums[i] > nums[i - 1]) {
                int i2 = nums[i - 1];
                vector<int>::iterator it = nums.end();
                while ( ++i2 < size ) {
                    if ( ( it = find(nums.begin() + i + 1, nums.end(), i2) ) != nums.end() )
                        break;
                }

                if ( it != nums.end() ) {
                    *it ^= nums[i - 1];
                    nums[i - 1] ^= *it;
                    *it ^= nums[i - 1];
                } else {
                    nums[i] ^= nums[i - 1];
                    nums[i - 1] ^= nums[i];
                    nums[i] ^= nums[i - 1];
                }

                sort(nums.begin() + i, nums.end());
                return;
            }
        }

        return sort(nums.begin(), nums.end());
    }
};

思路很简单, 从右到左找到第一个”不和谐”的点B (该点数字比前面的数字A大)

然后拿A, 从这个不和谐的点B往右找下一个比A大的数, 交换

之后重排序B右边的数字(包括B)

emmmm… 结果不太好呢…

dalao’s code

static const int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();
// 很 6 啊, 这里实际是一个值, 全局的 static 变量, 他的执行会在 main 之前 
// 会求值 lambda 表达式中的内容, 而值并不是主要的目的, 甚至不是目的  
// 他是想调用其中的加速流操作的函数, 所以lambda最后有个()运算符, 果然我是条咸鱼...

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end()); // emm. 这是标准库函数...
    }
};

里面有一些我看不懂的东西, 涉及到 c++ 的流

ios::sync_with_stdio(false);    // 是否兼容printf
cin.tie(nullptr);        // 在每一次输入之前, 不要让他调用 cout 的 flushing

网上查了一下, 加速流的输入输出…

http://www.hankcs.com/program/cpp/cin-tie-with-sync_with_stdio-acceleration-input-and-output.html

https://www.geeksforgeeks.org/fast-io-for-competitive-programming/

dalao 就是 dalao…

我是怎么在不知道这一对函数的情况下活到今天的

leetcode/334IncreasingTripletSubsequence

Posted on 2020-01-09

334 Increasing Triplet Subsequence

找出数组中是否存在n个连续增长数列

my solution (0ms, 100%)

这道题的解法来自于在做完另一道题后, 观察最佳算法时获得的技巧

简单来说, 这可以用一个可覆写的数组来实现

func increasingTriplet(nums []int) bool {
    vec := []int{1 << 63 - 1}

    for _, v := range nums {
        if v > vec[len(vec) - 1] {
            vec = append(vec, v)

            if len(vec) > 2 {
                return true
            }

            continue
        }

        for i, v2 := range vec {
            if v <= v2 {
                vec[i] = v
                break
            }
        }
    }

    return false
}

因为答案仅仅需要一个 bool 值, 所以可以这么做

不过, 有时候, vec 的值会是错误的, 同时这个解可以用于 n 个数字, 也可用于递减数组

(同时, 如果我在讨论中, 没有看到相应语言完全比我好的解法, 我会开始分享自己的解法)

(https://leetcode.com/problems/increasing-triplet-subsequence/discuss/298228/go-simple-solution-O(n)-100)

开始没想到, 尝试了几次之后想到的

best solution

func increasingTriplet(nums []int) bool {
    min1,min2:= 2<<32-1,2<<32-1
    for _,v:=range nums{
        if v<=min1{
            min1=v
        }else if v<=min2{
            min2=v
        }else {
            return true
        }
    }
    return false
}

EHM… 我好像又把问题复杂化了…

不过没关系, 我的解可以用于 n 个序列 (我如此安慰自己)

leetcode/338CountingBits

Posted on 2020-01-09

338 Counting Bits

不想解释

my solution (没脸说…)

这样的东西必定有规律, 找出来就好了

func countBits(num int) []int {
    ret := []int{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}
    last := []int{1, 2, 2, 3, 2, 3, 3, 4}

    for i, size := 3, 16; size <= num; i++ {
        beg := size - size / 4

        for beg + 4 <= size {
            last = append(last[:], ret[beg:]...)
            beg = beg + (size - beg) / 2
        }

        last = append(last[:], []int{i, i + 1, i + 1, i + 2}...)
        ret = append(ret[:], last[:]...)
        size *= 2
    }

    ret = ret[:num + 1]
    return ret
}

规律如下, 每次的增加都是上次的一半的递归 (我不知道怎么解释这种规律, 感觉语言很苍白…)

0,1,1,2,
1,2,2,3,
1,2,2,3, 2,3,3,4,
1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5,
1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5, 2,3,3,4, 3,4,4,5, 3,4,4,5, 2,3,3,4, 3,4,4,5, 4,5,5,6

仔细观察一下就发现了

我本来以为我的解法很不错, 计算次数很少, 几乎没有, 大部分的运算都是 append, 应该会很快, 然而…

那个几十毫秒的不是我的, 800/900 的才是 = =

best solution

func countBits(num int) []int {
    result := make([]int, num+1)
    for i := 1; i <= num; i++ {
        result[i] = result[i & (i-1)] + 1
    }
    return result
}

他是通过计算出来的, 比我好在于, 他不会计算多余的, 然后需要裁剪

(BTW 这个算法与我原算法的速度相差无几, 但是等价的 C++ 代码却只需要几十毫秒)

(加上 tie 和 sync_with_stdio, 可能速度能更快, 我不禁陷入了沉思…)

leetcode/377CombinationSumIV

Posted on 2020-01-09

Combination Sum IV

找出满足条件组合的次数

my solution

没脸写出来

best solution

func combinationSum4(nums []int, target int) int {
    if target <= 0 {
        return 0
    }
    dp := make([]int, target+1)
    dp[0] = 1

    for i := 0; i <= target; i++ {
        for _, num := range nums {
            if i-num >= 0 {
                dp[i] += dp[i-num]
            }
        }
    }
    return dp[target]
}

0 1 = 1
1 1 = 1
2 1 1 = 2
3 2 1 1 = 4
4 4 2 1 = 7

不太好描述这个规律, 有点类似于 “万丈高楼平地起”, 简单来说就是一个迭代/包含的过程

比较关键的地方在于循环中的 if (感觉是废话 = = )

我想过, 是否会出现一种情况, 这种情况通过了判断, 但是实际上不正确

比如当 i = 3 的时候, num = 2, 通过了判断, 但是此时没有 1 那么就无法组成 4

这种情况成立么? 答案是否定的, 因为 2 中的次数就包含了有 1, 如果没有 1, 2 也将会是 0

假设 P(x) 为 x 所包含的次数, 上述解法就是 P(x) = P(x - 1) + … + P(1) (等式右侧每项参数都位于nums中)

(感觉越描越黑了 - - )

leetcode/32ZLongestValidParentheses

Posted on 2020-01-09

Longest Valid Parentheses

一个只包含字符 ‘(‘ 和字符 ‘)’ 的字符串, 找到最长的有效括号层数

my solution

这个问题的核心是如何知道, 哪个 ‘)’ 和哪个 ‘(‘ 匹配

这种情况, 如果用栈来解决的话会简单很多

static int _ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int longestValidParentheses(string s) {
        int size = s.size();

        vector<int> vecc;
        for (int i = 0; i < size; ++i) {
            if (s[i] == '(') {
                vecc.push_back(i);
            } else {    // asume is )
                if (vecc.size() && s[vecc.back()] == '(') {
                    s[i] = '0';
                    s[vecc.back()] = '0';
                    vecc.pop_back();
                }
                else {  // asume if (vecc.back() != '(') 
                    vecc.clear();
                }
            }
        }

        int ret = 0, now = 0;
        for (int i = 0; i < size; ++i) {
            if (s[i] == '0')
                ++now;
            else {
                ret = max(now, ret);
                now = 0;
            }
        }

        return max(now, ret);
    }
};

我并没有想到一次循环并找到最大长度的办法

采用的是一次循环将所有能够合并的括号全部替换, 再用一次循环来找到其中最长的序列

效果比想象中的要好, 可能是归功于快速IO

the best solution (4ms)

const static int _= []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();	// 在 hard 难度的题里面, 这个东西频繁出现

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLength = 0;
        vector<int> dp(s.size());
        for (int i = 1; i < s.size(); i++)
        {
            // 只处理当前值是 ')' 的情况
            if (s[i] == ')')
            {
                // 如果上一个值是 '('
                if (s[i - 1] == '(')
                {
                    // 如果当前下标超出了 2, 意味着可以加上之前的宽度
                    if (i > 2)
                        dp[i] = dp[i - 2] + 2;
                    else
                        // 否则宽度直接为 2 
                        dp[i] = 2;
                }
                // 如果上一个值是 ')'
                else // s[i-1] == ')'
                {
                    // 暂时保存上一个下标所记录的步数
                    int prev = dp[i - 1];
                    // 先判断下标是否有效, s[i - prev - 1] 的含义是
                    // 当前下标 减去 上一个下标记录的宽度, 那么就来到了这个宽度的起始位置
                    // 再减去 1, 就得到了这个宽度的上一个字符, 如果是 '(' 则代表宽度可以继续增加2
                    if (i - prev - 1 >= 0 && s[i - prev - 1] == '(')
                    {
                        // 宽度增加了 2
                        dp[i] = dp[i - 1] + 2;
                        // 再判断上一个区间的索引值是否合法
                        if (i - prev - 2 >= 0)
                            // 合法的话就再加上上一个区间的宽度
                            dp[i] += dp[i - prev - 2];
                    }
                }

            }
        }

        for (int n : dp)
            maxLength = max(maxLength, n);
        return maxLength;
    }
};

算法给人的第一感觉是”脚印”, 如果上一个”脚印”有效, 就加上他, 这样慢慢增加

他也是由两次循环组成, 第一个循环计算每次的步数, 第二次循环找到最大值

规律总结在代码注释, 假设字符串是 “()))()))()”, 那么他的 dp 可能是 0 2 0 0 0 2 0 0 0 2

“())(())()()()))” dp 可能是 0 2 0 0 0 2 4 0 6 0 8 0 [10] 0 0

(眼睛有点花… 不过应该没错)

大抵来说:

跳过了 ‘(‘ 的判断, 这会使需要处理的情况少 1/2
赋值少了 1/2, 他不对 ‘(‘ 的索引进行计算

emmm… 学到了很多

感觉”脚印”这个概念在很多算法里面都看到过, 一个个累加将复杂的计算分为了很多的小计算

leetcode/45ZJumpGameII

Posted on 2020-01-09

45. Jump Game II

给定一个非负整数的数字, 你开始在数组的第一个索引处

每一个在数组中的元素代表你能够跳跃的最大距离

你的目标是找到到达最后一个索引的最小跳跃数

my code

要达到最小跳跃数的话, 那么只要保证每次跳跃的距离是最大的就可以了

每个节点的跳跃距离是节点距离起始节点的距离 + 节点自身值

感觉比上一个 jump 简单

class Solution {
public:
    int jump(vector<int>& nums) {
        size_t size = nums.size();
        if (size <= 1) return 0;

        int route = 0;
        for (int i = 0; i < size; ) {
            if (i + nums[i] >= size - 1)
                return ++route;

            int maxn = nums[i] + nums[i + nums[i]];
            int step = nums[i];
            for (int i2 = i + 1; i2 <= (i + nums[i]); ++i2) {
                if (i2 - i + nums[i2] > maxn) {
                    maxn = i2 - i + nums[i2];
                    step = i2 - i;
                }
            }

            i += step;
            ++route;
        }

        return -1;
    }
};

结果还行, 看一下最好的算法

the best solution

auto fast_io = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();	// 我已经不会见到这个会觉得奇怪了!

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, n);
        ans[0] = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i]+i >= n-1) ans[n-1] = min(ans[n-1], ans[i]+1);
            else {
                int temp = nums[i];
                while (temp > 0 && ans[i+temp] > ans[i]+1) ans[i+(temp--)] = ans[i]+1;
            }
        }
        return ans[n-1];
    }
};

大致想法上好像差不多

看不太懂, 但是我感觉好像差不多

它多了一个长度为 n 的数组, 并且循环是线性 n

(我没有使用数组, 并且循环是以 step 为距离, 唯一会在速度上决胜负的应该是我for 中的 for 和他for中的while对比, 他的while可以提前退出的, 综合来说, 我觉得这次我的算法不输他! (有点膨胀 :) … ) )

我将前面的 fast_io 添加进我的代码后, 也达到了最好的速度

emmm, 那就不花时间研究他的算法了~

leetcode/46ZPermutations

Posted on 2020-01-09

46ZPermutations

给定一个整数数组集合, 返回所有的数组排列可能

my solution (16ms)

如果单纯想要做出来, 很简单, 递归就完事了

static const int _ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    return 0;
}();

class Solution {
public:
    vector<vector<int>> permute(vector<int>& v) {
        size_t size = v.size(); 
        if (size == 1) return {v};
        else if (size == 0) return {};

        // asume size >= 2;
        for (int i = 0; i < size; ++i) {
            vector<int> temp = v;
            temp.erase(temp.begin() + i);

            permute_do({v[i]}, temp);
        }

        return ret;
    }

private:
    void permute_do(vector<int> curv, vector<int> v) {
        size_t size = v.size();

        if (size == 1) {
            ret.push_back(curv);
            ret.back().push_back(v.front());

            return;
        }

        for (int i = 0; i < size; ++i) {
            vector<int> tempV = v;
            tempV.erase(tempV.begin() + i);
            vector<int> tempCurv = curv;
            tempCurv.push_back(v[i]);

            permute_do(tempCurv, tempV);
        }
    }

private:
    vector<vector<int>> ret;
};

内存使用率应该很高, 因为每一次递归都会重新创建临时对象

但是想不到什么好的方式在不影响速度的情况下解决这个问题…

emmm, 内存使用果然很高…

(这个问题是几个月之前尝试过的, 试了 3 次没有成功, 今天一次就成功了,

而且解题的时间也挺短的, 看来进步还不错)

the best solution (14ms)

看一下最好的算法是怎么解决这个问题的

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > result;

        permuteRecursive(num, 0, result);
        return result;
    }

    // permute num[begin..end]
    // invariant: num[0..begin-1] have been fixed/permuted
    void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
        if (begin >= num.size()) {
            // one permutation instance
            result.push_back(num);
            return;
        }

        for (int i = begin; i < num.size(); i++) {
            swap(num[begin], num[i]);
            permuteRecursive(num, begin + 1, result);
            // reset
            swap(num[begin], num[i]);
        }
    }
};

他将 permute 中的循环合并到了 permuteRecursive 里面

核心在于 swap, 通过交换, 这样 result 就始终只有一个, 取而代之的是多了一个 int 参数传递