tips

发表于

#2d vector resize 可以用 dp.resize(matrix.size() + 1, vector(matrix.size() + 1, 0));

#统计是否包含某个字符(字母)可以统计字母出现的次数，比如字母就设定一个26元素的数组数组，统计字符在字母表中出现的字数即可

#BST的inorder遍历相当于生序排列，要熟悉用栈来实现

#删除bst节点，分三种情况: 1. 如果删除节点为叶子节点，直接删除，指向null。2. 如果其结点只包含左子树，或者右子树的话，此时直接删除该结点，并将其左子树，或者右子树设置为其父结点的左子树或者右子树即可，此操作不会破坏树结构。

  1. 当结点的左右子树都不空的时候，一般的删除策略是用其右子树的最小数据（容易找到）代替要删除的结点数据并递归删除该结点（此时为null），因为右子树的最小结点不可能有左孩子，所以第二次删除较为容易。z的左子树和右子树均不空。找到z的后继y，因为y一定没有左子树，所以可以删除y并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替z的值.如图：

容易犯错的概念

c++ list是双向链表，iterator是双向迭代器，但是只支持++, –, != ==操作，不能比较也不能向前跨越，如果需要前进多步，则需要用advance函数，前提是要检查是否到达.end()。

list的insert(iterator position, const value_type& val)，返回值是一个iterator，所以如果要在最末位插入元素并且返回一个iterator指向最后一个元素，可以用insert，而不用push_back.

list的erase，的参数是iterator(iterator erase(iterator position)，或者iterator erase (iterator first, iterator last)），范围[first, last);，不支持用index，返回值也是一个iterator；但是unordered_map支持key和iterator的删除，因为元素是一个pair嘛，也好理解

list的swap是交换两个containor，而不是两个元素

以上为LRUCache踩过的坑，算法明白了，老有bug，记录下来不能再犯错了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class LRUCache {
    int m_capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> hs;
    
public:
    LRUCache(int capacity) {
        m_capacity = capacity;
    }
    
    int get(int key) {
        if (hs.find(key) == hs.end()) return -1;
        // erase的参数为iterator
        pair<int, int> p = *hs[key];
        cache.erase(hs[key]);
        hs[key] = cache.insert(cache.end(), p);
        return (*hs[key]).second;
    }
    
    void put(int key, int value) {
        // 如果key有重叠，一定要把以前的擦掉，不然会残留在containor内，超过容量会把需要的元素弹出的
        if (hs.find(key) != hs.end()) {
            cache.erase(hs[key]);
            hs[key] = cache.insert(cache.end(), make_pair(key, value));
        }
        else {
            if (cache.size() == m_capacity) {
                hs.erase(cache.front().first);
                cache.pop_front();
                // hashtable erase可以是iterator也可以是key
                hs[key] = cache.insert(cache.end(), make_pair(key, value));
            }
            else {
                hs[key] = cache.insert(cache.end(), make_pair(key, value));
            }
        }
    }
};

##继续iterator，数组型和节点型iterator的区别
链接：https://www.nowcoder.com/test/question/done?tid=6738151&qid=55374
来源：牛客网

当使用一个容器的insert或者erase函数通过迭代器插入或删除元素”可能”会导致迭代器失效
iterator失效主要有两种情况：
1、iterator变量已经变成了“野指针”，对它进行*,++,–都会引起程序内存操作异常；
2、iterator所指向的变量已经不是你所以为的那个变量了。
不同的容器，他们erase()的返回值的内容是不同的，有的会返回被删除元素的下一个的iterator，有的则会返回删除元素的个数。
对于非结点类，如数组类的容器 vector,string,deque 容器标准写法是这样:

1
2
3
4
5
6
7
8
9
10
 //vector<int> m_vector;
 for(vector<int>::iterator iter = m_vector.begin(); iter != m_vector.end();)
{
    if(需要删除)
    {
        iter=m_vector.erase(iter);
    }
    else
        ++iter;
}

数组型数据结构：该数据结构的元素是分配在连续的内存中，insert和erase操作，都会使得删除点和插入点之后的元素挪位置，所以，插入点和删除掉之后的迭代器全部失效，也就是说insert(iter)(或erase(iter))，然后在iter++，是没有意义的。解决方法：erase(*iter)的返回值是下一个有效迭代器的值。 iter =cont.erase(iter);

对于结点类容器(如:list,map,set)是这样:

1
2
3
4
5
6
7
8
9
10
 //map<int,int> m_map;
for(map<int,int>::iterator iter = m_map.begin(); iter != m_map.end(); )
{
    if(需要删除)
    {
        m_map.erase(iter++);
    }
    else
        ++iter;
}

链表型数据结构：对于list型的数据结构，使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.解决办法两种，erase(*iter)会返回下一个有效迭代器的值，或者erase(iter++).

树形数据结构： 使用红黑树来存储数据，插入不会使得任何迭代器失效；删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以采用erase(iter++)。

##友元
静态成员函数属于整个类所拥有，没有this指针
友员函数不是这个类的成员，没有this
类的非静态成员函数 有this

##复习static关键字

02/23/2017 指针的引用

http://www.cppblog.com/doing5552/archive/2010/09/28/127994.html
or
http://www.cnblogs.com/li-peng/p/4116349.html

// 例如： MYCLASS* p = new MYCLASS；
func1（p）；
上面这段代码的这种处理方法想必谁都用过，创建一个MYCLASS对象，然后将它传入func1函数。现在假设此函数要修改pMyClass： void

1
2
3
4
func1（MYCLASS *pMyClass）{
    DoSomething（pMyClass）；
    pMyClass = // 其它对象的指针
}

第二条语句在函数过程中只修改了pMyClass的值。并没有修改调用者的变量p的值。如果p指向某个位于地址0x008a00的对象，当func1返回时，它仍然指向这个特定的对象。（除非func1有bug将堆弄乱了，完全有这种可能。）

现在假设你想要在func1中修改p的值。这是你的权利。调用者传入一个指针，然后函数给这个指针赋值。以往一般都是传双指针，即指针的指针，例如，CMyClass**。

1
2
3
4
5
6
7
MYCLASS* p = NULL；
func1（&p）；
void func1（MYCLASS** pMyClass）；{
    *pMyClass = new MYCLASS；
    ……
}

调用func1之后，p指向新的对象。
如果你理解指针的指针，那么你肯定就理解指针引用，因为它们完全是一回事。如果你象下面这样声明函数：

1
2
3
4
void func1（MYCLASS *& pMyClass）{
    pMyClass = new MYCLASS； 
    ……
}

其实，它和前面所讲得指针的指针例子是一码事，只是语法有所不同。传递的时候不用传p的地址&p，

02/25/2017
对于数组，如果要求一段的和，可以另外一个数组，然后累积求和

02/26/2017
c++的priority_queue只能用数组指针初始化？如果好像没办法像vector一样vector {1, 2}这样初始化。并且priority_queue不支持迭代器，只能用!pq.empty()来判断

x&(x-1)统计1的个数，x|(x+1)统计0的个数

02/27/2017
如果返回是int型，别直接开根号比较