每日学习——4.4号

---

前言：

今天是写博客第一天，想要将csdn的博客作为我每日进步的见证。

首先说明一下，此次专栏连载的内容会非常杂，会包括一天学习所得的所有内容，即可能包括我的必修课和数学建模，算作是记录我学习足迹的一个平台吧。

正文：

1.对于sort函数，注意其cmp函数要在类外面定义，不然会出错。

可参考这篇文章。

错误：reference to non-static member function must be called_initMyHeart的博客-CSDN博客

这个经验源于审错题了，忽略数组元素要连续的条件，将数组排序了，导致错误，因此思考的。

这个题目在下面也会探讨。

2.runtime error: addition of unsigned offset to 0x602000000130 overflowed to 0x60200000012c (stl_vector.h)
原因很简单，往往是由于下标出现了小于零的-1。

3.字典树：

有两种方法：

1.用链表模拟

2.用数组模拟空间（上面的idx纯粹是标记一下此处有值了）；

代码如下（示例）：

有关动态存储数组的可以看一下这篇博客：

C++建立动态二维数组_longshengguoji的博客-CSDN博客_c++定义动态二维数组

#include
using namespace std;
#include
const int n = 26;//每一个结点能延伸出多少子节点
/*这是构建二维数组，咱们只用到指针数组的部分
使用数组指针，分配一个指针数组，将其首地址保存在b中，然后再为指针数组的每个元素分配一个数组
              
           int **b=new int*[row];       //分配一个指针数组，将其首地址保存在b中                                                    
           for(i=0;ison[c] == nullptr)//友元不能访问私有数据？？？？？？
            {
                p->son[c] = new tire(s[i]);//直接调用构造函数
            }
            p = p->son[c];
        }
        p->cnt++;
    }
    friend int search(string s, tire* root);

};
int search(string s,tire* root)
{
    tire* p = root;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - 'a';
        if (p->son[c] == nullptr)
        {
            return 0;
        }
        else
        {
            p = p->son[c];
        }
    }
    return p->cnt;
}
int tire2[105][n];
int cnt[105];
int idx = 0;
void insert(string s)
{
    int p = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - 'a';
        if (!tire2[p][c])tire2[p][c] = ++idx;
        p = tire2[p][c];
    }
    cnt[p]++;
}
int search(string s)
{
    int p = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - 'a';
        if (!tire2[p][c])return 0;
        p = tire2[p][c];
    }
    return cnt[p];
}
int main()
{

}

例题：

构造字典树：
力扣

const int n=26;

class Trie {
public:
char val;
Trie**son;
int cnt;
    /** Initialize your data structure here. */
    Trie(char a=0) {
        val=a;
        son=new Trie*[26];
        for(int i=0;ison[c]==nullptr)
            {
                p->son[c]=new Trie(word[i]);
            }
            p=p->son[c]; 
        }
        p->cnt++;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie*p=this;
        for(int i=0;ison[c]==nullptr)return 0;//非常的奇怪：此处用p索引，直接写son会错。

好吧
						//我是憨憨，一点也不奇怪，这仍然在root的成员函数中，显然son还是root的son，怎么可能对嘛！！
            p=p->son[c];
        }
        return p->cnt;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string word) {
         Trie*p=this;
        for(int i=0;ison[c]==nullptr)return 0;
            p=p->son[c];
        }
        return 1;

    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

 4.

线段树：

力扣

这个一开始sum的终止条件写错了，不知道怎么想的写成了start<=l&&r>=end.这就不可能对了。

还有，传进去的是要求给定的数组大小，而不是你模拟完全二叉树的数组大小。

void bulid(vector& nums,vector&nod,int node,int start,int end)
{
    if(start==end)
   { nod[node]=nums[start];
   return ;
   }
    
    int mid=(end-start)/2+start;
    int left_node=2*node+1;
    int right_node=2*node+2;
    bulid(nums,nod,left_node,start,mid);
    bulid(nums,nod,right_node,mid+1,end);
    nod[node]=nod[left_node]+nod[right_node];
}
void up(vector&nod,int node,int start,int end,int index,int val)
{
    if(start==end)
    {
        nod[node]=val;
        return;
    }
      int mid=(end-start)/2+start;
      int left_node=2*node+1;
    int right_node=2*node+2;
      if(index>=start&&index<=mid)
      {
          up(nod,left_node,start,mid,index,val);
      }
      else
      {
          up(nod,right_node,mid+1,end,index,val);
      }
      nod[node]=nod[left_node]+nod[right_node];
}
int sum(vector&nod,long long  node,long long  start,long long  end,int l,int r)
{
    if(rend)//终止条件不要找错！！！
    return 0;
    if(start>=l&&end<=r)
    {
        return nod[node];
    }
     long long  mid=(end-start)/2+start;
      long long  left_node=2*node+1;
    long long  right_node=2*node+2;
    return sum(nod,left_node,start,mid,l,r)+sum(nod,right_node,mid+1,end,l,r);

}
class NumArray {
vectornode;
int size=0;
public:
    NumArray(vector& nums) {
        node.resize(100000,0);
        size=nums.size();
        
        bulid(nums,node,0,0,size-1);
    }
    
    void update(int index, int val) {
    up(node,0,0,size-1,index,val);

    }
    
    int sumRange(int left, int right) {
      return   sum(node,0,0,size-1,left,right);
 
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */