code-review

  • code-review

二分查找

  • 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
    void search(vector<int>& nums,int left,int right,int target)//最左,没找到的话 最左接近
    {
    int mid = 0;
    while (left <= right)
    {
    mid = left + (right - left) / 2;
    if (target > nums[mid])
    {
    left = mid + 1;
    }
    else
    right = mid - 1;
    }
    cout <<"left= "<<left<<" "<<nums[left] << endl;////第一个大于等于7的位置
    cout << "right= " << right << " " << nums[right] << endl;////最后一个小于7的位置
    }

    void search2(vector<int>& nums, int left, int right, int target)//最右,没找到的话 最右接近
    {
    int mid = 0;
    while (left <= right)
    {
    mid = left + (right - left) / 2;
    if (target >= nums[mid])
    {
    left = mid + 1;
    }
    else
    right = mid - 1;
    }
    cout << "left= " << left << " " << nums[left] << endl;//第一个大于7的位置
    cout << "right= " << right << " " << nums[right] << endl;////最后一个小于等于7的位置
    }

数据结构

二叉树

二叉树遍历

  • 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
    vector<int> preorder(TreeNode* root)
    {
    vector<int> ret;
    stack<pair<TreeNode*,bool>> mystack;
    mystack.push({root,false});//

    bool visited;
    while(!mystack.empty())
    {
    root=mystack.top().first;
    visited=mystack.top().second;
    mystack.pop();
    if(root==nullptr)
    continue;
    if(visited)
    {
    ret.push_back(root->val);
    }
    else
    {
    //前序遍历 中 左 右
    mystack.push({root->right,false});
    mystack.push({root->left,false});
    mystack.push({root,true});
    //中序遍历 左 中 右
    mystack.push({root->right,false});
    mystack.push({root,true});
    mystack.push({root->left,false});
    //后序遍历 左 右 中
    mystack.push({root,true});
    mystack.push({root->right,false});
    mystack.push({root->left,false});
    }

    }
    return ret;
    }

队列

模拟循环队列

  • 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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    //数据模拟循环链表
    class requeue{
    private:
    int SIZE;
    int head;
    int tail;
    vector<int> data;
    public:
    requeue(int sz)
    {
    SIZE=sz;
    head=-1;
    tail=-1;
    data.resize(SIZE);
    }
    bool full()
    {
    return (tail+1)%SIZE==head;
    }
    bool empty()
    {
    return head==-1;
    }
    bool push(int val)
    {
    if(full())
    return false;
    tail=(tail+1)%SIZE;
    data[tail]=val;
    }
    bool pop()
    {
    if(empty())
    return false;
    if(head==tail)// 整个都pop完毕了
    {
    head=tail=-1;
    return true;
    }
    head=(head+1)%SIZE;
    return true;
    }
    int getfront()
    {
    if(empty())
    return -1;
    return data[head];
    }
    int gettail()
    {
    if(empty())
    return -1;
    return data[tail];
    }
    }

链表

合并K个有序链表

  • 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
    class cmp{
    public:
    bool operator()(const ListNode* p1,const ListNode* p2){
    return p1->val > p2->val;
    }
    };//构建最小堆

    class Solution {
    public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode dummy(-1),*root=&dummy;
    priority_queue<ListNode*,vector<ListNode*>,cmp> q;
    int n=lists.size();
    for(int i=0;i<n;i++)//构建最小堆
    {
    if(lists[i]==NULL) continue;
    q.push(lists[i]);
    }
    while(!q.empty()){//每次取出最小值,并连接成链表
    ListNode* node=q.top();
    q.pop();
    root->next=node;
    root=root->next;
    if(node->next!=NULL) q.push(node->next);
    root->next=NULL;
    }
    return dummy.next;
    }
    };

链表环检测

  • 1
     

TOP -K

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int findKthLargest(vector<int>& nums, int k)//找到第K大的数
    {
    priority_queue<int, vector<int>, greater<int> >pq;//最小堆
    for(auto num:nums)
    {

    if(pq.size()<k)
    pq.push(num);
    else if(num>pq.top())
    pq.pop(),pq.push(num);
    }
    return pq.top();
    }

LRU

  • 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
    39
    40
    41
    42
    43
    44
    45
    class LRUCache {
    private:
    int cap;
    list<pair<int,int>> cache;//存放key-value 键值对
    unordered_map<int,list<pair<int,int>>::iterator> mymap;//存放key--key_value的迭代器,为了给定key定位,key-value在cache中位置
    public:
    LRUCache(int capacity) {
    cap=capacity;
    }


    int get(int key) {
    auto it=mymap.find(key);
    if(it==mymap.end())
    return -1;
    pair<int,int> data=*mymap[key];//返回数据
    cache.erase(mymap[key]);//cache 更新位置 将最近的使用的key放到第一个
    cache.push_front(data);//
    mymap[key]=cache.begin();//map更新位置
    return data.second;
    }

    void put(int key, int value) {
    auto it=mymap.find(key);
    if(it==mymap.end())//如果不存在
    {
    if(cache.size()==cap)//如果LRU已满
    {
    auto back=cache.back();//删除尾端元素
    cache.pop_back();
    mymap.erase(back.first);
    }

    cache.push_front(make_pair(key,value));//cache插入到最前
    mymap[key]=cache.begin();//map 更新位置
    }
    else
    {
    cache.erase(mymap[key]);
    cache.push_front(make_pair(key,value));
    mymap[key]=cache.begin();
    }

    }
    };
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
  
*

# BFS

* 模板

* ```c++
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> used; // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;////!!!!!!!!!!!!
add root to used;///!!!!!!!!!!!!!!!!
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;//!!!!!!!!!!!
add next to used;//!!!!!!!!!
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
  • 注意 添加queue 和visited时机

大数问题

  • 找出Top 10 (找出出现次数最多的10个)
    • 先用Hash表统计每个Query出现的次数,O(N)
    • 采用最小堆数据结构找出Top 10,N*O(logK);
    • 最终的时间复杂度是:O(N) + N’*O(logK)。(N为1000万,N’为300万)。

并查集

  • 题目:

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
        给定若干个32int数字集合,每个集合中的数字无重复,譬如:
      {1,2,3} {2,5,6} {8}
      将其中交集不为空的集合合并,保证合并完成后所有集合之间无交集,输出合并后的集合个数以及最大集合中元素的个数。

      输入格式:
      1. 第一行为一个数字N,表示集合数。
      2. 接下来N行,每行一个非空集合,包含若干个数字,数字之间用空格分开。
      假设第i个集合的大小为Si,数据满足N<=100000,ΣSi<=500000

      输出格式:
      1. 第一行为合并后的集合个数。
      2. 第二个为最大集合中元素的个数。
      输入
      3
      1 2 3
      2 5 6
      8
      输出
      2
      5
  • 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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    //并查集
    #include <bits/stdc++.h>
    using namespace std;

    class DisjointSet
    {
    private:
    std::unordered_map<int, int> parent;//index=包含的值,value=父亲
    std::unordered_map<int, int> rank; // 秩index=某棵树的根节点,value=树的高度

    public:
    void add(int x)
    {
    if(parent.find(x) == parent.end()) {//如果从未添加过,去重
    parent[x] = x;//初始时,每个节点的父亲是自己
    rank[x] = 0;//高度为0
    }
    }
    int find(int x)
    {
    // 查找根节点,并包含路径压缩,提高运行效率
    //将所有节点到根节点的距离压缩至1步,parent[x] 为x的根节点
    return x == parent[x] ? x : (parent[x] = find(parent[x]));
    }
    //把一个集合的根节点的父节点指向其另一个集合的根节点。这样就完成了Union操作。
    void to_union(int x1, int x2)
    {
    int f1 = find(x1);
    int f2 = find(x2);
    if (f1 == f2) return;
    // 按秩合并,find-union操作最坏的运行时间提高至O(log n)
    if (rank[f1] > rank[f2])
    parent[f2] = f1;
    else {
    parent[f1] = f2;
    if (rank[f1] == rank[f2])//当两个树的rank 高度相等时,需要调整rank高度信息+1
    ++rank[f2];
    }
    }
    void printRes()
    {
    int cnt = 0, len_max;
    map<int, int> set;//index=根节点,value=size
    for(auto it = parent.begin(); it != parent.end(); it++) {
    find(it->first); // 将所有节点到根节点的距离压缩至1步
    if(set.find(it->second) == set.end()) set[it->second] = 0;
    set[it->second]++; // 统计合并后每个集合的大小
    if(it->first == it->second) cnt++; // 当根节点为本身时,集合数加一
    }
    for(auto p = set.begin(); p != set.end(); p++)
    len_max = max(len_max, p->second);
    cout << cnt << endl << len_max << endl;
    // for(auto it = parent.begin(); it != parent.end(); it++) {
    // cout << it->first << " " << it->second << endl;
    // }
    }
    };
    int main(void)
    {
    DisjointSet ans = DisjointSet();
    int n, a, b;
    cin >> n;
    while(n--) {
    scanf("%d", &a);
    ans.add(a);
    while(getchar() != '\n') {//按照行建立树
    scanf("%d", &b);
    ans.add(b);
    ans.to_union(a, b);
    }
    }
    ans.printRes();
    return 0;
    }

动态规划

所有合法的序列的个数

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    链接:https://www.nowcoder.com/questionTerminal/13483f545ad7499c97a3bbcdcdb9312a?answerType=1&f=discussion
    来源:牛客网
    给出一个数字N,对于数字序列 1,2,3 ... N。现在在其中插入“+”, "-", " ",使得表达式的和为M。" "的含义是把相邻的两个数字组成一个数。例如:1 + 2 3 - 4,含义是:1 + 23 - 4 = 20
    给出N和M,求出所有合法的序列的个数。

    两个整数N,M ( 1 <= N <= 7, -100 <= M <= 100)
    合法序列的个数
    7 0
    6

    样例中的六种合法序列
    1+2-3+4-5-6+7
    1+2-3-4+5+6-7
    1-2 3+4+5+6+7
    1-2 3-4 5+6 7
    1-2+3+4-5+6-7
    1-2-3-4-5+6+7
  • 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
    /*
    DFS
    从前往后 DFS时,遇到减号-,没有办法统计当前的计算结果,传递到下一个
    同时考虑多次“”时的连乘问题
    */
    // before: 需要判定的符号前面的数字的个数,初始为8
    // des: 需要判定的符号后面的数字,初始为9
    // n:方程右边的结果
    // ex:阶乘数,因为符号有三种可能,加号,减号,或者没有,如果没有,那么ex就用于计算当前值
    //当before 和des中间为“”时,res没办法更新,同时ex+1
    int dp(int before, int des, int res, int ex)//拆成两个, res是目前的计算结果
    {
    if (before == 0)//默认在最前端有个+号,des
    {
    if (des == res)//到头了,0+des = res
    {
    return 1;
    }
    else {
    return 0;
    }
    }
    else {
    //减法 加法 空格
    return dp(before - 1, before, res + des, 1) + dp(before - 1, before, res - des, 1) + dp(before - 1, before*pow(10, ex) + des, res, ex + 1);
    }
    }

    dp(N-1, N, M, 1);

字符串编辑距离

  • 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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    /*
    有两个字符串,其中可以通过删除一个字符,修改一个字符,增加一个字符来改变,使其两个字符串完全相等。其中改变的次数为距离的相似度。

    比如:

    abcdde

    abcedd

    对于两个长度相等的字符串,相似度距离为:2

    最左边+1=删除本身的编辑距离+删除本身
    最上边+1=上一个的编辑距离+直接添加一个
    左上角+1=当前不相同,直接替换
    左上角=当前相同,
    */
    int ldistance(const string source,const string target)
    {
    //step 1

    int n=source.length();
    int m=target.length();
    if (m==0) return n;
    if (n==0) return m;
    //Construct a matrix
    typedef vector< vector<int> > Tmatrix;
    Tmatrix matrix(n+1);
    for(int i=0; i<=n; i++) matrix[i].resize(m+1);

    //step 2 Initialize
    //第一行 第一列 初始化,表示,
    for(int i=1;i<=n;i++) matrix[i][0]=i;
    for(int i=1;i<=m;i++) matrix[0][i]=i;

    //step 3
    for(int i=1;i<=n;i++)
    {
    const char si=source[i-1];
    //step 4
    for(int j=1;j<=m;j++)
    {

    const char dj=target[j-1];
    //step 5
    int cost;
    if(si==dj){
    cost=0;
    }
    else{
    cost=1;
    }
    //step 6
    const int above=matrix[i-1][j]+1;//上边+1
    const int left=matrix[i][j-1]+1;//左边+1
    const int diag=matrix[i-1][j-1]+cost;//左上角+cost
    matrix[i][j]=min(above,min(left,diag));

    }
    }//step7
    return matrix[n][m];
    }

最长公共子序列(LCS)

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /*
    子序列和子串的区别

    简单理解就是子串是连续的,子序列是不连续的。

    例如 abcaurssas,其中 acusa就是一个子序列,abca就是一个子串。
    给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB

    则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
    */
  • 2012111100085930

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int lcs_common(const string& str1, const string& str2)
    {
    int len1 = str1.size();
    int len2 = str2.size();
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

    for (int i = 1; i <=len1; i++)
    {
    for (int j = 1; j <= len2; j++)
    {
    if (str1[i - 1] == str2[j - 1])
    dp[i][j] = dp[i - 1][j - 1] + 1;
    else
    {
    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    }
    }
    }

    //lcs_print_one(str1,str2,str1.length()+1,str2.length()+1,dp);
    string lcs_str;
    lcs_print_all(str1, str2, str1.length() + 1, str2.length() + 1, dp, lcs_str);
    return dp[len1][len2];
    }
    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    //打印一个LCS
    void lcs_print_one(const string& str1, const string& str2, int i, int j, vector<vector<int>>&veca)
    {
    string lcs_str;
    while (i > 0 && j > 0)
    {
    if (str1[i - 1] == str2[j - 1])
    {
    lcs_str = str1[i - 1] + lcs_str;
    --i;
    --j;
    }
    else
    {
    if (veca[i - 1][j] >= veca[i][j - 1])
    {
    --i;
    }
    else
    --j;
    }
    }
    cout << lcs_str << endl;
    }
    //打印所有LCS
    void lcs_print_all(const string& str1, const string& str2, int i, int j, vector<vector<int>>&veca,string lcs_str)//lcs_str不可以为引用
    {
    // string lcs_str;
    while (i > 0 && j > 0)
    {
    if (str1[i - 1] == str2[j - 1])
    {
    lcs_str = str1[i - 1] + lcs_str;
    --i;
    --j;
    }
    else
    {
    if (veca[i - 1][j] > veca[i][j - 1])//往最长的方向找
    --i;
    else if(veca[i - 1][j] < veca[i][j - 1])
    --j;
    else {//相等时表示有多个LCS,上,左都要查询
    lcs_print_all(str1,str2,i-1,j,veca,lcs_str);
    lcs_print_all(str1, str2, i , j-1, veca,lcs_str);
    return;
    }
    }
    }
    cout << lcs_str << endl;
    }

最长公共子串

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //dp[i][j] 以i 和 j结尾的最大公共子串
    int lcs_common(const string& str1, const string& str2)
    {
    int len1 = str1.size();
    int len2 = str2.size();
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    for (int i = 1; i <=len1; i++)
    {
    for (int j = 1; j <= len2; j++)
    {
    if (str1[i - 1] == str2[j - 1])
    dp[i][j] = dp[i - 1][j - 1] + 1;
    else
    {
    //dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    dp[i][j]=0;
    }
    }
    }
    return dp[len1][len2];
    }

最少零钱数

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //无限多个小钱 拼成大钱,个数最少
    int least_coins(vector<int>& coins,int amount)
    {
    int sz=coins.size();
    vector<int> dp(amount+1,INT_MAX);
    dp[0]=0;// 0钱 0个
    for(int i=1;i<=amount;i++)
    {
    for(int j=0;j<sz;j++)
    {
    if(i>=coins[j])
    {
    if(dp[i-coins[j]]!=INT_MAX)
    dp[i]=min(dp[i],dp[i-coins[j]]+1);
    }
    }
    }
    return dp[amount]!=INT_MAX?dp[amount]:-1;
    }

最多组合数

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //dp[i][j]用前i个钱 拼j钱的最多组合数
    void most_coins(vector<int>& coins,int n)
    {
    int sz=coins.size();
    vector<vector<int>> dp(sz+1,vector<int>(n+1,0));
    dp[0][0]=1;//0个钱拼0钱 =1
    for(int i=1;i<=sz;i++)
    {
    dp[i][0]=1;//i个钱拼0钱=1 什么也不给???
    for(int j=1;j<=n;j++)
    {
    //拼j钱时,是否用第i个钱
    if(j>=coins[i])
    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];
    else
    dp[i][j]=dp[i-1][j];
    }
    }

    }
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //dp[i][j]用前i个钱 拼j钱的最多组合数
    void most_coins(vector<int>& coins,int n)
    {
    int sz=coins.size();
    vector<vector<int>> dp(sz+1,vector<int>(n+1,0));
    dp[0][0]=1;//0个钱拼0钱 =1
    for(int i=1;i<=sz;i++)
    {
    // dp[i][0]=1;//i个钱拼0钱=1 什么也不给???
    for(int j=0;j<=n;j++)
    {
    //拼j钱时,是否用第i个钱
    if(j>=coins[i])
    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];
    else
    dp[i][j]=dp[i-1][j];
    }
    }

    }
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    const int mod = 1e9 + 7;
    int n;
    cin >> n;
    vector<int> dp(n + 1, 0);
    vector<int> coins{ 1,2,5,10 };
    dp[0] = 1;//拼0钱为1,什么都不给,不就是0嘛
    for (int i = 0; i < coins.size(); i++)
    {
    for (int j = coins[i]; j <= n; j++)
    dp[j] = dp[j] + dp[j - coins[i]];
    }
    cout << dp[n] % mod << endl;

手撕代码

  • 手写string

    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
    39
    40
    41
    42
    43
    class my_string
    {
    private:
    char* m_data;
    public:
    my_string(const char* cstr = 0)
    {
    if (cstr)
    {
    m_data = new char[strlen(cstr)+1];
    strcpy(m_data,cstr);
    }
    else
    {
    m_data = new char[1];
    *m_data = '\0';
    }
    }
    my_string(const my_string& str_)
    {
    m_data = new char[strlen(str_.m_data)+1];
    strcpy(m_data,str_.m_data);
    }
    my_string& operator=(const my_string& str_)
    {
    if (this == &str_)
    return *this;
    delete[] m_data;
    m_data = new char[strlen(str_.m_data)+1];
    strcpy(m_data,str_.m_data);
    return *this;
    }
    virtual ~my_string()
    {
    delete[] m_data;
    }
    char* get_c_str() const { return m_data; }
    };
    ostream& operator<< (ostream& os, const my_string& str)
    {
    os << str.get_c_str();
    return os;
    }
  • strcpy / memcpy / memmov / atoi

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    unsigned int ip2str(const string& ip)
    {
    unsigned int ret=0;
    int pos =-1, pos2 = 0;

    while ((pos = ip.find('.', pos+1)) != string::npos)
    {
    cout << ip.substr(pos2,pos-pos2)<< endl;
    pos2 = pos+1;
    ret <<= 8;
    ret |= stoi(ip.substr(pos2, pos - pos2) ) & 0xff;
    }
    cout << ip.substr(pos2) << endl;
    ret <<= 8;
    ret |= stoi(ip.substr(pos2))&0xff;

    cout <<"ret= "<<ret<< endl;
    return 0;
    }
  • 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
    char* mystrncpy2(char* dst, const char* src, int len)
    {
    assert(dst != nullptr && src != nullptr);
    char* res = dst;

    int offset = 0;
    if (strlen(src) < len)//src长度小于Len
    {
    offset = len - strlen(src);// 要补全的'\0'的个数
    len = strlen(src);
    }
    char* tmp;
    if (dst >= src && dst <= src + len - 1)//存在内存重叠
    {
    dst = dst + len - 1;
    src = src + len - 1;
    tmp = dst;
    while (len--)
    *dst-- = *src--;
    }
    else
    {
    while (len--)
    {
    *dst++ = *src--;
    }
    tmp = dst;
    }
    while (offset--)
    *tmp++ = '\0';
    return res;
    }
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    char* mystrcpy(char* dst, const char* src)
    {
    if (dst == nullptr || src == nullptr)
    return nullptr;
    char* dst2 = dst;
    while ((*dst2 = *src) != '\0')
    {
    dst2++;
    src++;
    }
    return dst;
    }
  • memcpy

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      void * mymemcpy(void* dst, void* src,int n)
      {
      if (src == nullptr || dst == nullptr)
      return nullptr;
      char* dst2 = static_cast<char*>(dst);
      char* src2 = static_cast<char*>(src);
      while (n--)
      {
      *dst2++ = *src2++;
      }
      return dst;
      }

读写锁

  • https://www.iteye.com/blog/eric-gcm-2162288

  • 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
    39
    40
    class readwrite_lock  
    {
    public:
    readwrite_lock()
    : read_cnt(0)
    {
    }
    void readLock()
    {
    read_mtx.lock();
    if (++read_cnt == 1)
    write_mtx.lock();

    read_mtx.unlock();
    }

    void readUnlock()
    {
    read_mtx.lock();
    if (--read_cnt == 0)
    write_mtx.unlock();

    read_mtx.unlock();
    }

    void writeLock()
    {
    write_mtx.lock();
    }

    void writeUnlock()
    {
    write_mtx.unlock();
    }

    private:
    mutex read_mtx;
    mutex write_mtx;
    int read_cnt; // 已加读锁个数
    };
文章目录
  1. 1. 二分查找
  2. 2. 数据结构
    1. 2.1. 二叉树
      1. 2.1.1. 二叉树遍历
    2. 2.2. 队列
      1. 2.2.1. 模拟循环队列
    3. 2.3. 链表
      1. 2.3.1. 合并K个有序链表
      2. 2.3.2. 链表环检测
  3. 3. TOP -K
  4. 4. LRU
  5. 5. 大数问题
  6. 6. 并查集
  7. 7. 动态规划
    1. 7.1. 所有合法的序列的个数
    2. 7.2. 字符串编辑距离
    3. 7.3. 最长公共子序列(LCS)
    4. 7.4. 最长公共子串
    5. 7.5. 最少零钱数
    6. 7.6. 最多组合数
  8. 8. 手撕代码
    1. 8.1. 读写锁