Nov 21, 2015 - 线段树

线段树

        线段树是一棵树,而且是二叉搜索树。它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。

        主要应用:适用于和区间统计有关的问题,例如大数据的动态修改 及多次查询就比较适合使用这种树,效果比较好。

        性质:

         1. 树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。

         2. 对于每一个非叶结点所表示的结点[a,b],其左儿子表示的区间为

         [a,(a+b)/2],右儿子表示的区间为[(a+b)/2,b]。

        3. 同一层的节点所代表的区间,相互不会重叠。

         4. 叶子节点的区间是单位长度,不可再分。

        构造过程:

         1. 构造节点node,对应的区间为[start,end]

         2. 构造node的左孩子,对应的区间为[start,start + (end - start) / 2]

         3. 构造node右孩子,对应的区间为[start + (end - start) / 2 + 1,end]

        线段树的构造过程就是二叉树递归的创建的过程,代码如下:

SegmentTreeNode* SegmentTree::GenerateTree(vector<int> &nums, int start, int end) {
    if(start > end) return nullptr;
    SegmentTreeNode *node = new SegmentTreeNode(start,end);
    if(start == end) {
        node->SetSum(nums[start]);
        return node;
    }
    int mid = start + (end - start) / 2;
    SegmentTreeNode *left = GenerateTree(nums,start,mid);
    SegmentTreeNode *right = GenerateTree(nums,mid+1,end);
    node->SetLeft(left);
    node->SetRight(right);
    node->SetSum(left->GetSum() + right->GetSum());
    return node;
}

        其中SegmentTreeNode 以及 SegmentTree为自己定义的类,最后附上整个的代码。

#include <vector>
using namespace std;

class SegmentTreeNode {
public:
    SegmentTreeNode(int a, int b);
    int GetStart();
    int GetEnd();
    void SetSum(int sum);
    int GetSum();
    void SetLeft(SegmentTreeNode* left);
    SegmentTreeNode* GetLeft();
    void SetRight(SegmentTreeNode* right);
    SegmentTreeNode* GetRight();
    
private:
    int start, end, sum;
    SegmentTreeNode* left;
    SegmentTreeNode* right;

};


class SegmentTree {
public:
    void BuildTree(vector<int> &nums, int start, int end);
    SegmentTreeNode *GetRoot();
    int ModifyTree(int i, int val);
    int QueryTree(int i, int j);

private:
    SegmentTreeNode *GenerateTree(vector<int> &nums, int start, int end);
    int _ModifyTree(int i, int val,SegmentTreeNode *node);
    int _QueryTree(int i, int j,SegmentTreeNode *node);
    SegmentTreeNode *root;
};


SegmentTreeNode::SegmentTreeNode(int a, int b):start(a),
                                               end(b),
                                               sum(0),
                                               left(nullptr),
                                               right(nullptr) {
                                                   
                                                   
    
};

int SegmentTreeNode::GetStart() {
    return start;
}
int SegmentTreeNode::GetEnd() {
    return end;
}
void SegmentTreeNode::SetSum(int sum) {
    this->sum = sum;
}
int SegmentTreeNode::GetSum() {
    return sum;
}

void SegmentTreeNode::SetLeft(SegmentTreeNode* left) {
    this->left = left;
}
SegmentTreeNode* SegmentTreeNode::GetLeft() {
    return left;
}
void SegmentTreeNode::SetRight(SegmentTreeNode* right) {
    this->right = right;
}

SegmentTreeNode* SegmentTreeNode::GetRight() {
    return right;
}

void SegmentTree::BuildTree(vector<int> &nums, int start, int end) {
    root = GenerateTree(nums, start, end);
}

SegmentTreeNode* SegmentTree::GenerateTree(vector<int> &nums, int start, int end) {
    if(start > end) return nullptr;
    SegmentTreeNode *node = new SegmentTreeNode(start,end);
    if(start == end) {
        node->SetSum(nums[start]);
        return node;
    }
    int mid = start + (end - start) / 2;
    SegmentTreeNode *left = GenerateTree(nums,start,mid);
    SegmentTreeNode *right = GenerateTree(nums,mid+1,end);
    node->SetLeft(left);
    node->SetRight(right);
    node->SetSum(left->GetSum() + right->GetSum());
    return node;
}

int SegmentTree::ModifyTree(int i, int val) {
    return _ModifyTree(i, val, root);
}

int SegmentTree::QueryTree(int i, int j) {
    return _QueryTree(i, j, root);
}

int SegmentTree::_ModifyTree(int i, int val,SegmentTreeNode *node) {
    if(node == nullptr) return 0;
    int diff;
    if(node->GetStart() == i && node->GetEnd() == i) {
        diff = val - node->GetSum();
        node->SetSum(val);
        return diff;
    }
    int mid = (node->GetStart() + node->GetEnd()) / 2;
    if(i > mid) {
        diff = _ModifyTree(i,val,node->GetRight());
    } else {
        diff = _ModifyTree(i,val,node->GetLeft());
    }
    node->SetSum(node->GetSum() + diff);
    return diff;
}

int SegmentTree::_QueryTree(int i, int j,SegmentTreeNode *node) {
    if(node == nullptr) return 0;
    if(node->GetStart() == i && node->GetEnd() == j) return node->GetSum();
    int mid = (node->GetStart() + node->GetEnd()) / 2;
    if(i > mid) return _QueryTree(i,j,node->GetRight());
    if(j <= mid) return _QueryTree(i,j,node->GetLeft());
    return _QueryTree(i,mid,node->GetLeft()) + _QueryTree(mid+1,j,node->GetRight());
}

        利用此代码在https://leetcode.com上AC过了两道题目。

Question 1: Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example: Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 Note: You may assume that the array does not change. There are many calls to sumRange function.

Question 2: Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val. Example: Given nums = [1, 3, 5]

sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8 Note: The array is only modifiable by the update function. You may assume the number of calls to update and sumRange function is distributed evenly.

        源码的下载地址:https://github.com/FyhSky/SegmentTree

Nov 21, 2015 - 自定义NSSearchField光标颜色

自定义NSSearchField光标颜色

        本文主要介绍如何自定义输入框中光标的颜色。如果想自定义NSSearchField样式,请参考老谭的一片文章:http://www.tanhao.me/pieces/1580.html/,该文章里面做了一些详细的介绍。

        改变光标颜色有两种方法:

         1. 子类化NSSearchFieldCell,重写setUpFieldEditorAttributes方法,代码片段如下。

- (NSText *)setUpFieldEditorAttributes:(NSText *)textObj
{
    NSText *text = [super setUpFieldEditorAttributes:textObj];
    [text setBackgroundColor:self.backgroundColor];
    text.drawsBackground = YES;
    [(NSTextView*)text setInsertionPointColor:[NSColor whiteColor]];
    return text;
}

        NSSearchField获取焦点,要显示光标的时候,都会调用该方法。

         2. 遍历NSSearchField的子视图(subviews), 取出_NSKeyboardFocusClipView类的对象,然后再取出里面的 NSTextView对象,调用setInsertionPointColor函数,传入想要的颜色,代码片段如下。

    if (self.searchField.subviews.count) {
        __block NSView *keyboardFocusClipView;
        [self.searchField.subviews enumerateObjectsUsingBlock:
        						^(id  obj, NSUInteger idx,
												 BOOL *stop) {
            //   NSClassFromString(@"_NSKeyboardFocusClipView");
            if ([obj isKindOfClass:[NSClipView class]]) {
                keyboardFocusClipView = obj;
                *stop = YES;
            }
        }];
        
        if (keyboardFocusClipView) {
            NSView *view = keyboardFocusClipView.subviews[0];
            [(NSTextView*)view setInsertionPointColor:cursorColor];
        }

    }

        两种方法的不同之处在于:方法一调用的前提,是输入框由无光标到有光标时才触发,如果在有光标的时候想改变光标的颜色,就只能使用方法二;方法二只有在输入框有光标的时候才会起作用,无光标的时候就没法触发。

        所以两种方法配合使用,就可以完美实现不同Theme下光标颜色的切换。

Nov 21, 2015 - GCD使用注意事项

GCD使用注意事项

        想必大家对GCD的概念都比较的熟悉,网上一搜一大堆,这里就不详细介绍了。         今天主要探讨一下GCD使用时候的一些注意事项,用不好的话有可能出现死锁。         死锁发生的场景:

 1. 使用同步函数dispatch_sync。
 2. 使用同步函数的线程跟同步函数执行的block线程为同一线程。 &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;死锁原因:

 1. 同步函数会阻塞当前线程,直到block执行完成。
 2. block线程被阻塞,block一直无法执行 &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;如下的代码片段就会发生死锁,程序运行只会输出:Before Block,然后程序卡住,无限的风火轮转起来。
- (void)testGCDDeadLock {
    dispatch_queue_t queue = dispatch_get_current_queue();
    NSLog(@"Before Block");
    dispatch_sync(queue, ^{
       NSLog(@"In Block");
    });
    NSLog(@"After Block");
}

        上面的代码片段只是为了方便测试,才使用了dispatch_get_current_queue函数,该函数在OSX10.9之后就被废弃,并且该函数不好操作,用不好会发现意想不到的后果。

        GCD给我们带了了使用线程方便的同时也埋下了隐患,因此在使用GCD相关的sync函数时,要特别的注意不能让执行block的线程为当前的线程。