查看完整版本 : LeetCode

darigold 2015-3-29 08:37 AM

LeetCode

做左十零題簡單既
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-maximum-depth-of-binary-tree.html]LeetCode OJ - Maximum Depth of Binary Tree[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-same-tree.html]LeetCode OJ - Same Tree[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-number-of-1-bits.html]LeetCode OJ - Number of 1 Bits[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-pascals-triangle.html]LeetCode OJ - Pascal's Triangle[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-balanced-binary-tree.html]LeetCode OJ - Balanced Binary Tree[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-minimum-depth-of-binary-tree.html]LeetCode OJ - Minimum Depth of Binary Tree[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-surrounded-regions.html]LeetCode OJ - Surrounded Regions[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-two-sum.html]LeetCode OJ - Two Sum[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-add-two-numbers.html]LeetCode OJ - Add Two Numbers[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-longest-substring-without.html]LeetCode OJ - Longest Substring Without Repeating Characters[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-single-number.html]LeetCode OJ - Single Number[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-plus-one.html]LeetCode OJ - Plus One[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-majority-element.html]LeetCode OJ - Majority Element[/url]

[[i] 本帖最後由 darigold 於 2015-7-18 04:52 AM 編輯 [/i]]

darigold 2015-4-2 10:22 PM

唔好俾佢停啊

[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-reverse-bits.html]LeetCode OJ - Reverse Bits[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-rotate-array.html]LeetCode OJ - Rotate Array[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-count-and-say.html]LeetCode OJ - Count and Say[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-path-sum.html]LeetCode OJ - Path Sum[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-factorial-trailing-zeroes.html]LeetCode OJ - Factorial Trailing Zeroes[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-house-robber.html]LeetCode OJ - House Robber[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-length-of-last-word.html]LeetCode OJ - Length of Last Word[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-excel-sheet-column-number.html]LeetCode OJ - Excel Sheet Column Number[/url]
[url=http://andrew-algorithm.blogspot.com/2015/03/leetcode-oj-excel-sheet-column-title.html]LeetCode OJ - Excel Sheet Column Title[/url]
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-merge-k-sorted-lists.html]LeetCode OJ - Merge k Sorted Lists[/url]
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-binary-tree-level-order.html]LeetCode OJ - Binary Tree Level Order Traversal[/url]
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-intersection-of-two-linked.html]LeetCode OJ - Intersection of Two Linked Lists[/url]

[[i] 本帖最後由 darigold 於 2015-7-18 05:00 AM 編輯 [/i]]

Susan﹏汪汪 2015-4-2 10:39 PM

好多binary tree嘅題目

汪汪呢幾日係蘋果forum到同另一個人(嘈)
基本上就係佢抱怨蘋果Swift為何只有Set和Dictionary但沒有OrderedSet同OrderedDictionary

然後佢就開始左研發自家OrderedSet之旅...不過就遇到更多問題, 例如明明寫緊Swift又死都要用Pointer去bypass個initializer
又或者明明係circular reference但又唔肯用weak reference, 到肯用weak reference時又死都要用unowned...
而明知unowned係必定在non-nil情況下才可以用...同時也有容許nil的weak implicitly unwrapped optional reference又肯唔用(根本就係同一樣)

言歸
汪汪就由一開始已經極速寫好一個[code]public func !=<T : Equatable>(lhs: OrderedSet<T>, rhs: OrderedSet<T>) -> Bool {
   
    if lhs.count != rhs.count {
        return true
    }
    for idx in 0..<lhs.count {
        if lhs[idx] != rhs[idx] {
            return true
        }
    }
    return false
}

public func ==<T : Equatable>(lhs: OrderedSet<T>, rhs: OrderedSet<T>) -> Bool {
   
    if lhs.count != rhs.count {
        return false
    }
    for idx in 0..<lhs.count {
        if lhs[idx] != rhs[idx] {
            return false
        }
    }
    return true
}

public struct OrderedSet<T : Comparable> : CollectionType {
   
    private var root: OrderedSetNode<T>?
   
    public init() {
        
    }
   
    public init<S : SequenceType where T == S.Generator.Element>(_ sequence: S) {
        
        for item in sequence {
            self.insert(item)
        }
    }
   
    public var startIndex: Int {
        return 0
    }
    public var endIndex: Int {
        return root?.weight ?? 0
    }
   
    public var count: Int {
        return root?.weight ?? 0
    }
   
    public func contains(member: T) -> Bool {
        return root?.contains(member) ?? false
    }
   
    public subscript (position: Int) -> T {
        return root![position]
    }
   
    public mutating func insert(member: T) {
        if isUniquelyReferencedNonObjC(&root) {
            root!.insert(member)
            root!.weightCheck()
            return
        } else if let _root = root {
            root = _root.clone
            root!.insert(member)
            root!.weightCheck()
            return
        }
        root = OrderedSetNode(member)
    }
   
    public func generate() -> GeneratorOf<T> {
        var _view = root?.view.0
        return GeneratorOf {
            if _view != nil {
                let value = _view!.value
                _view = _view!._next
                return value
            }
            return nil
        }
    }
   
    public var isEmpty: Bool {
        return root == nil
    }
}

extension OrderedSet : ArrayLiteralConvertible {
   
    public init(arrayLiteral elements: T ...) {
        for item in elements {
            self.insert(item)
        }
    }
}

extension OrderedSet : Printable, DebugPrintable {
   
    public var description: String {
        if self.count == 0 {
            return "0 members"
        }
        return "{" + ", ".join(map(self) { "\($0)" }) + "}"
    }
   
    public var debugDescription: String {
        if self.count == 0 {
            return "0 members"
        }
        return "{" + ", ".join(map(self) { "\($0)" }) + "}"
    }
}

private class OrderedSetNode<T : Comparable> {
   
    var value: T
    var node1, node2: OrderedSetNode<T>?
   
    // used for tree rotation
    var weight: Int
   
    init(_ value: T) {
        self.value = value
        self.weight = 1
    }
}

extension OrderedSetNode {
   
    var clone: OrderedSetNode<T> {
        let _clone = OrderedSetNode(value)
        _clone.node1 = self.node1
        _clone.node2 = self.node2
        _clone.weight = self.weight
        return _clone
    }
}

extension OrderedSetNode {
   
    func leftRotate() {
        
        let _tnode = node1
        node1 = OrderedSetNode(value)
        node1!.node1 = _tnode
        node1!.node2 = node2!.node1
        node1!.weightCheck()
        
        value = node2!.value
        node2 = node2!.node2
        
    }
   
    func rightRotate() {
        
        let _tnode = node2
        node2 = OrderedSetNode(value)
        node2!.node2 = _tnode
        node2!.node1 = node1!.node2
        node2!.weightCheck()
        
        value = node1!.value
        node1 = node1!.node1
        
    }
   
    func weightCheck() {
        
        if node1 == nil && node2 != nil && node2!.weight > 1 {
            leftRotate()
        } else if node2 == nil && node1 != nil && node1!.weight > 1 {
            rightRotate()
        } else if node1 != nil && node2 != nil {
            if node1!.weight > node2!.weight * 2 {
                rightRotate()
            } else if node1!.weight * 2 < node2!.weight {
                leftRotate()
            }
        }
        
        let _w1 = node1?.weight ?? 0
        let _w2 = node2?.weight ?? 0
        self.weight = _w1 + _w2 + 1
    }
   
    func contains(member: T) -> Bool {
        if member < value {
            return node1?.contains(member) ?? false
        }
        if value < member {
            return node2?.contains(member) ?? false
        }
        return true
    }
   
    subscript (position: Int) -> T! {
        let _w1 = node1?.weight ?? 0
        if position < _w1 {
            return node1?[position]
        }
        if position == _w1 {
            return value
        }
        return node2?[position - _w1 - 1]
    }
   
    func insert(newValue: T) {
        if newValue < value {
            if isUniquelyReferencedNonObjC(&node1) {
                node1!.insert(newValue)
            } else if let _node1 = node1 {
                node1 = _node1.clone
                node1!.insert(newValue)
            } else {
                node1 = OrderedSetNode(newValue)
            }
            node1!.weightCheck()
            return
        }
        if value < newValue {
            if isUniquelyReferencedNonObjC(&node2) {
                node2!.insert(newValue)
            } else if let _node2 = node2 {
                node2 = _node2.clone
                node2!.insert(newValue)
            } else {
                node2 = OrderedSetNode(newValue)
            }
            node2!.weightCheck()
            return
        }
        value = newValue
    }
}

extension OrderedSetNode {
   
    var view: (OrderedSetView<T>, last: OrderedSetView<T>) {
        let _v = OrderedSetView(value)
        let _v1 = node1?.view
        let _v2 = node2?.view
        if _v1 != nil && _v2 != nil {
            _v1!.last._next = _v
            _v._next = _v2!.0
            return (_v1!.0, _v2!.last)
        }
        if _v1 == nil && _v2 != nil {
            _v._next = _v2!.0
            return (_v, _v2!.last)
        }
        if _v1 != nil && _v2 == nil {
            _v1!.last._next = _v
            return (_v1!.0, _v)
        }
        return (_v, _v)
    }
}

private class OrderedSetView<T> {
   
    var value: T
    var _next: OrderedSetView<T>?
   
    init(_ value: T) {
        self.value = value
    }
}[/code]

darigold 2015-4-3 02:29 PM

Interesting Swift code.
睇住你既code突然諗起persistent data structure,一種functional language寫,可以access所有historical state既data structure。有興趣可以去研究一下。

Susan﹏汪汪 2015-4-3 04:19 PM

[quote]原帖由 [i]darigold[/i] 於 2015-4-3 02:29 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413342103&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
Interesting Swift code.
睇住你既code突然諗起persistent data structure,一種functional language寫,可以access所有historical state既data structure。有興趣可以去研究一下。 [/quote]汪汪都唔知呢個...只係寫寫下諗到呢個做法

因為要保持Swift嘅特色, 所有container外在行為必需要同value type一樣(也所以要用struct定義)
第二點係Swift屬lazy evaluation, 所以所有container都係copy-on-write

基於以上原因...汪汪自己寫嘅都保留呢個特性

darigold 2015-4-4 12:14 AM

persistent binary tree

[code]#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class persistent_tree
{
public:
    persistent_tree();
    ~persistent_tree();
    void insert(int x);
    void dump(unsigned int time_stamp);
private:
    class persistent_tree_node
    {
    public:
        persistent_tree_node(int data, persistent_tree_node* left, persistent_tree_node* right, int count);
        ~persistent_tree_node();
        
        void add_ref();
        void release();

        // Ideally these should be encapsulated - skipped for illustration
        persistent_tree_node* left;
        persistent_tree_node* right;
        unsigned int count;
        int data;
        int ref_count;
    };

    vector<persistent_tree_node*> roots;

    persistent_tree_node* recursive_insert(persistent_tree_node* current, int new_data);
    void recursive_dump(persistent_tree_node* current);
};

persistent_tree::persistent_tree()
{
}

persistent_tree::~persistent_tree()
{
    for (unsigned int i = 0; i < this->roots.size(); i++)
    {
        this->roots[i]->release();
    }
}

persistent_tree::persistent_tree_node::persistent_tree_node(int data, persistent_tree_node* left, persistent_tree_node* right, int count)
{
    this->left = left;
    this->right = right;
    this->data = data;
    this->count = 1;

    if (this->left != nullptr)
    {
        this->left->add_ref();
    }
    if (this->right != nullptr)
    {
        this->right->add_ref();
    }
}

void persistent_tree::persistent_tree_node::add_ref()
{
    this->ref_count++;
}

void persistent_tree::persistent_tree_node::release()
{
    if (--this->ref_count == 0)
    {
        delete this;
    }
}

persistent_tree::persistent_tree_node::~persistent_tree_node()
{
    if (this->left != nullptr)
    {
        this->left->release();
    }
    if (this->right != nullptr)
    {
        this->right->release();
    }
}

void persistent_tree::insert(int new_data)
{
    // Insert always work on the last time stamp
    persistent_tree_node* root = nullptr;
    if (this->roots.size() != 0)
    {
        root = this->roots[this->roots.size() - 1];
    }

    persistent_tree_node* new_root = this->recursive_insert(root, new_data);
    new_root->add_ref();
    this->roots.push_back(new_root);
}

persistent_tree::persistent_tree_node* persistent_tree::recursive_insert(persistent_tree::persistent_tree_node* current, int new_data)
{
    if (current == nullptr)
    {
        return new persistent_tree::persistent_tree_node(new_data, nullptr, nullptr, 1);
    }
    else if (current->data == new_data)
    {
        return new persistent_tree::persistent_tree_node(new_data, current->left, current->right, current->count + 1);
    }
    else if (current->data > new_data)
    {
        persistent_tree::persistent_tree_node* new_left_node = this->recursive_insert(current->left, new_data);
        return new persistent_tree::persistent_tree_node(current->data, new_left_node, current->right, current->count);
    }
    else if (current->data < new_data)
    {
        persistent_tree::persistent_tree_node* new_right_node = this->recursive_insert(current->right, new_data);
        return new persistent_tree::persistent_tree_node(current->data, current->left, new_right_node, current->count);
    }
    else
    {
        assert(false);
        return nullptr;
    }
}

void persistent_tree::dump(unsigned int time_stamp)
{
    if (time_stamp < this->roots.size())
    {
        persistent_tree::persistent_tree_node* root = this->roots[time_stamp];
        this->recursive_dump(root);
        cout << endl;
    }
    else
    {
        assert(false);
    }
}

void persistent_tree::recursive_dump(persistent_tree::persistent_tree_node* current)
{
    if (current == nullptr)
    {
        return;
    }
    else
    {
        this->recursive_dump(current->left);
        for (unsigned int i = 0; i < current->count; i++)
        {
            // Extra comma at the end, don't care
            cout << current->data << ", ";
        }
        this->recursive_dump(current->right);
    }
}

int main(int argc, char** argv)
{
    persistent_tree tree;
    tree.insert(3);
    tree.insert(0);
    tree.insert(6);
    tree.insert(2);
    tree.insert(4);
    tree.dump(0);
    tree.dump(1);
    tree.dump(2);
    tree.dump(3);
    tree.dump(4);
    return 0;
}[/code]

darigold 2015-4-4 12:21 AM

For simplicity - I implemented only the insert method for a binary tree, and didn't bother to balance it.

1.) This tree is based on immutable nodes, with more careful handling of ref_count (using interlocked increment) and root list (using a lock free queue maybe), we can run this data structure in parallel with no locks.

2) this tree can give caller back all its histories. This can be useful if we want them. For example, when a transaction need to be rollback, or maybe just because we wanted to debug. By releasing the root list selectively, we can choose what time-stamp we wish to get rid of. Of course, we could have achieve the same thing by cloning the whole tree all the time, but that's too expensive. The maintain log(n) time for the insertion (assuming the tree balancing will be there)

darigold 2015-4-4 01:09 AM

Code is pushed to [url]https://github.com/cshung/MiscLab/blob/master/PersistentTreeDemo/Main.cpp[/url]

stupidsing 2015-4-10 06:40 PM

while we are on the topic of persistent trees, I'd like to show you my immutable 2-3 tree (or B-tree) implementation.

[url]https://github.com/stupidsing/suite/blob/master/src/main/java/suite/immutable/I23Tree.java[/url]

This tree implementation is immutable, auto-balanced and supports removal.  Comments are welcome.

darigold 2015-4-11 01:12 AM

[quote]原帖由 [i]stupidsing[/i] 於 2015-4-10 06:40 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413962500&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
while we are on the topic of persistent trees, I'd like to show you my immutable 2-3 tree (or B-tree) implementation.
[/quote]
Nice suite of source code!
I am particularly interested in the c/asm folder. You seems to have some good stuff there - garbage collector, jit code demo, bootloader, ...

煙民母親生賤種 2015-4-11 01:26 AM

[quote]原帖由 [i]darigold[/i] 於 2015-4-4 01:09 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413385415&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
Code is pushed to [url=https://github.com/cshung/MiscLab/blob/master/PersistentTreeDemo/Main.cpp]https://github.com/cshung/MiscLab/blob/master/PersistentTreeDemo/Main.cpp[/url] [/quote]點解你地鐘意用傳統的格式? 而唔直接在個 class 內 detailed 埋 D code? 唔覺得亂及麻煩嗎?:fst_013:

                                    [table][tr][td]persistent_tree::~persistent_tree()[/td][/tr][tr][td]{[/td][/tr][tr][td]    for (unsigned int i = 0; i < this->roots.size(); i++)[/td][/tr][tr][td]    {[/td][/tr][tr][td]        this->roots[i]->release();[/i][/td][/tr][tr][td]    }[/td][/tr][tr][td]}[/td][/tr][/table]

class persistent_tree{
~persistent_tree()
{
    for (unsigned int i = 0; i < this->roots.size(); i++)
    {
        this->roots->release();
    }

}
};

Susan﹏汪汪 2015-4-11 01:59 AM

[quote]原帖由 [i]stupidsing[/i] 於 2015-4-10 06:40 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413962500&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
while we are on the topic of persistent trees, I'd like to show you my immutable 2-3 tree (or B-tree) implementation.

[url=https://github.com/stupidsing/suite/blob/master/src/main/java/suite/immutable/I]https://github.com/stupidsing/suite/blob/master/src/main/java/suite/immutable/I[/url] ... [/quote]之前只係簡單試過寫唔影響balance同保持最大COW的情況下嘅remove
不過有部份情況下出錯...

但之後搞緊新apps上架同更新舊app
而且除非寫database
現實多數情況下用Hash table都係最佳, 而且只有少數情況需要iterate ordinal data
針對呢D少數情況做sorting比較長期insert/remove都保持O(log n)嘅OrderedSet有過之而無不及
所以OrderedSet冇咩實質作用就一直冇理到

darigold 2015-4-11 03:50 AM

:) C# Dictionary 我用得最多。
老C++沒有default HashMap, 用Map就多。Map係Red Black Tree。
我段code既keypoint係persistence。唔係save落disk既persistent,係任何時候可以搵番次前n個time step既data。

HashMap據我理解做唔到。
之前學過HashTrie,可以做到,我得閒試試:p

darigold 2015-4-11 03:52 AM

唔好.......停!

Harder ones!
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-binary-tree-preorder.html]LeetCode OJ - Binary Tree Preorder Traversal[/url] (Trivial recursive walk)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-binary-tree-inorder.html]LeetCode OJ - Binary Tree Inorder Traversal[/url] (Trivial recursive walk)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-climbing-stairs.html]LeetCode OJ - Climbing Stairs[/url] (Trivial dynamic programming)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-populating-next-right.html]LeetCode OJ - Populating Next Right Pointers in Each Node[/url] (Non trivial traversal order - simple though)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-repeated-dna-sequences.html]LeetCode OJ - Repeated DNA Sequences[/url] (Compact packing)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-valid-parentheses.html]LeetCode OJ - Valid Parentheses[/url] (Pushdown Automata)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-unique-binary-search-trees.html]LeetCode OJ - Unique Binary Search Trees[/url] (Catalan numbers!)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-linked-list-cycle.html]LeetCode OJ - Linked List Cycle[/url] (Floyd Cycle detection)
[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-single-number-ii.html]LeetCode OJ - Single Number II[/url] (Finite field modulo 3)

[[i] 本帖最後由 darigold 於 2015-7-18 05:03 AM 編輯 [/i]]

darigold 2015-4-11 04:04 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2015-4-11 01:26 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413992308&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
點解你地鐘意用傳統的格式? 而唔直接在個 class 內 detailed 埋 D code? 唔覺得亂及麻煩嗎?:fst_013:[/quote]
第一,習慣,冇乜好解釋,同你習慣用右手(我猜)寫字一樣。
第二,抽象,讀我header files既人唔需要理解我的implementation。
第三,separate compilation,儘量做細header file會minimize chances to re-compile more than I need

其實咁細段code(小於1k line),2, 3都係多餘,main point係第一。

darigold 2015-4-11 05:00 AM

[quote]原帖由 [i]darigold[/i] 於 2015-4-11 04:04 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413997583&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

第一,習慣,冇乜好解釋,同你習慣用右手(我猜)寫字一樣。
第二,抽象,讀我header files既人唔需要理解我的implementation。
第三,separate compilation,儘量做細header file會minimize chances to re-compil ... [/quote]
講起習慣,真係唔明點解有人鐘意將粒星寫係variable前面。

char *x;
而唔係

char* x;

stupidsing 2015-4-11 08:45 AM

[quote]原帖由 [i]darigold[/i] 於 2015-4-11 01:12 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413991494&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Nice suite of source code!
I am particularly interested in the c/asm folder. You seems to have some good stuff there - garbage collector, jit code demo, bootloader, ... [/quote]
亂葬崗一個,擺放了很多半制成的實驗品。:smile_35:
gc和jit離目標還有萬丈遠吧。


講返persistent trees, 2-3 樹我就知點做,red-black始終理解得唔透。
好似兩種架構係equivalent 的,有 O(log n) 已經心足。

同埋持久樹的 gc 好難做,係有垃圾收集的環境就易,
但如果用持久樹整文件系統就唔知幾時可以回收不用的頁面。

stupidsing 2015-4-11 08:47 AM

[quote]原帖由 [i]darigold[/i] 於 2015-4-11 05:00 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413998619&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

講起習慣,真係唔明點解有人鐘意將粒星寫係variable前面。

char *x;
而唔係

char* x; [/quote]

因為(曾經)有呢種寫法。
char *x, y, *z;

當中唯有 y 不是指針。

darigold 2015-4-11 09:25 AM

[quote]原帖由 [i]stupidsing[/i] 於 2015-4-11 08:45 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=414007335&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

亂葬崗一個,擺放了很多半制成的實驗品。:smile_35:
gc和jit離目標還有萬丈遠吧。

講返persistent trees, 2-3 樹我就知點做,red-black始終理解得唔透。
好似兩種架構係equivalent 的,有 O(log n) 已經心足 ... [/quote]
睇下Princeton Professor Robert Sedgewick的Left Leaning Red-Black Tree!
垃圾回收試下用ref-count,咁就乜tree都一樣!

煙民母親生賤種 2015-4-11 01:50 PM

[quote]原帖由 [i]darigold[/i] 於 2015-4-11 05:00 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=413998619&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

講起習慣,真係唔明點解有人鐘意將粒星寫係variable前面。

char *x;
而唔係

char* x; [/quote]:fst_010::fst_010::fst_010:

做咩話我 :fst_004::fst_004:


粒星痴住 variable, 一眼就知佢係 pointer! 唔洗睇返個 char 。

又好似有 d人寫

void mth(){
}

我都唔明點解左 { 要放在 上面, 明明
void mth()
{
}

就整整齊齊

darigold 2015-4-12 09:50 AM

[quote]原帖由  真係唔明點解有人鐘意將粒星寫係variable前面。
[/quote]
[quote]原帖由  於 2015-4-11 01:50 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=414024969&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]做咩話我
粒星痴住 variable, 一眼就知佢係 pointer! 唔洗睇返個 char 。
[/quote]
冇話你,我真係唔明。而家明了。

[[i] 本帖最後由 darigold 於 2017-10-2 04:24 AM 編輯 [/i]]

darigold 2015-4-21 12:45 PM

呢條有難度

[url]https://leetcode.com/problems/largest-number/[/url]

greedy唔work, sorting是不成的。12, 121 ->12121   12, 123 -> 12312 冇好辦法order。
brute force太慢。
唔知有冇dp solution。
branch and bound冇小心tune都會TLE。

Susan﹏汪汪 2015-4-21 02:02 PM

[quote]原帖由 [i]darigold[/i] 於 2015-4-21 12:45 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=414856228&ptid=24497948][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
https://leetcode.com/problems/largest-number/

greedy唔work, sorting是不成的。12, 121 ->12121   12, 123 -> 12312 冇好辦法order。
brute force太慢。
唔知有冇dp solution。
branch and bound冇小心tune ... [/quote]
字典序?



[url=http://www.discuss.com.hk/iphone][img=100,23]http://i.discuss.com.hk/d/images/r10/iphoneD.jpg[/img][/url]

darigold 2015-4-21 03:34 PM

係張床度訓唔著,又俾我諗到答案,AC了。
唔係字典序。[url=http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-largest-number.html]http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-largest-number.html[/url]

[[i] 本帖最後由 darigold 於 2018-4-22 09:52 AM 編輯 [/i]]

darigold 2015-4-22 09:51 PM

再黎一條我覺得難既...

[url]http://andrew-algorithm.blogspot.com/2015/04/leetcode-oj-median-of-two-sorted-arrays.html[/url]

其實就係binary search搞清楚所有details也不容易。

darigold 2015-4-23 07:12 AM

有冇人想試suffix tree?

[url=https://leetcode.com/problems/longest-palindromic-substring/]https://leetcode.com/problems/longest-palindromic-substring/[/url]

Suffix tree好煩,最終學左Manacher's Algorithm

http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-longest-palindromic.html

[[i] 本帖最後由 darigold 於 2015-7-5 08:42 AM 編輯 [/i]]

darigold 2015-4-24 07:33 AM

MIT 6.851 is awesome!

darigold 2015-6-16 01:33 AM

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

[url=http://andrew-algorithm.blogspot.com/2015/06/leetcode-oj-invert-binary-tree.html]LeetCode OJ - Invert Binary Tree[/url]

Can't imagine a good programmer don't get this one - this is trivial!

[[i] 本帖最後由 darigold 於 2015-7-15 11:16 PM 編輯 [/i]]

darigold 2015-7-6 11:31 PM

復活了!

[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-longest-palindromic.html]LeetCode OJ - Longest Palindromic Substring[/url]
[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-zigzag-conversion.html]LeetCode OJ - ZigZag Conversion[/url]
[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-reverse-integer.html]LeetCode OJ - Reverse Integer[/url]
[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-string-to-integer-atoi.html]LeetCode OJ - String to Integer (atoi)[/url]
[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-binary-tree-right-side-view.html]LeetCode OJ - Binary Tree Right Side View[/url]
[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-palindrome-number.html]LeetCode OJ - Palindrome Number[/url]

45/215

[[i] 本帖最後由 darigold 於 2015-7-15 11:14 PM 編輯 [/i]]

darigold 2015-7-7 11:51 PM

唔好俾佢停 ... again!

[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-implement-queue-using-stacks.html]LeetCode OJ - Implement Queue using Stacks[/url]
[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-regular-expression-matching.html]LeetCode OJ - Regular Expression Matching[/url]

[[i] 本帖最後由 darigold 於 2015-7-15 11:15 PM 編輯 [/i]]
頁: [1] 2 3 4 5 6 7 8 9 10
查看完整版本: LeetCode