Skip to main content

4 Data Structure

Array​

  • 数组越界
  • 数组是否可以重复,重复的处理

LinkedList​

易错点:每一步p->next检查p!=NULL

Stack​

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647]

if there are no brackets, we could evaluate easily

if there are brackets, we could see each part = nonbracket + evaluate(bracket), but nonbracket should be store in a stack

Problems: evaluate(bracket) could be -3, so the new expression could contain 3*-3, 3+-3, 3--3. We need to handle those.

int calculate(string &s) {
    stack<string> nonbracket;
    string curStr; 
    for(auto p: s){
        if(p=='('){
            nonbracket.push(curStr);
            curStr = "";
        }
        else if(p==')'){
            curStr = to_string(evaluate(curStr));
            curStr = nonbracket.top() + curStr;
            nonbracket.pop();
        }
        else if(p!=' ') curStr +=p;
    }
    return evaluate(curStr);
}
long long evaluate(string input){
    int i =0, j =0;
    long long base = 0, temp = 0;
    input = '+' + input;
    while(i<input.size()){
        if(input[i]=='+'||input[i]=='-'){
            base += temp;
            j = i+1;
            if(input[j]=='-')++j;
            while(isdigit(input[j]))++j;
            temp = stoll(input.substr(i+1,j-1-i));
            temp = input[i]=='+'?temp: -temp;
            i = j;
        }
        else if(input[i]=='*'||input[i]=='/'){
            j = i+1;
            if(input[j]=='-')++j;
            while(isdigit(input[j]))++j;
            if(input[i]=='*') temp *= stoll(input.substr(i+1,j-1-i));
            else temp /= stoll(input.substr(i+1,j-1-i));
            i = j;
        }
    }
    return base + temp;
}

Monotonic Stack​

  • Mono-decreasing(pop smaller elements) stack keeps the result as greater as possible
  • Mono-increasing stack keeps the result as smaller as possible

Deque​

Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> ans;
    for(int i=0;i<nums.size();++i){
        while(!dq.empty()&&dq.front()<nums[i])dq.pop_front();
        dq.push_front(nums[i]);
        if(i-k>=0&&!dq.empty()&&dq.back()==nums[i-k])dq.pop_back();
        if(i>=k-1) ans.push_back(dq.back());
    }
    return ans;
}

Tree​

1.Traverse​

  • Preorder Traversal: printing directory listing(ls)
  • Postorder Traversal: gathering file size

Level traverse

思路1:bfs(要建树的数据结构)​
思路2:dfs(要Node结构体)​
struct sq {
    int index;
    int data;
};
void order(int i,int j) {
    if (node[i].lchild != -1) {
        level.push_back({2 * j,node[i].lchild});
        order(node[i].lchild,2 * j);
    }
    in.push_back(i);
    if (node[i].rchild != -1) {
        level.push_back({2 * j+1,node[i].rchild});
        order(node[i].rchild,2 * j+1);
    }

}
bool cmp(sq a,sq b) {
    return a.index<b.index;
}

搜符合要求路径(不需要Node结构体)

const int maxn = 1010;
vector<int> g[maxn];//已知结点关系
void dfs(int x, int dp) {//depth运用
    path[depth] = w[x];
    if (g[x].size() == 0) {
        ll temp = 0;
        for (int i = 0; i <= depth; i++) temp += path[i];
        if (temp == s) {
            for (int i = 0; i <= depth; i++) ans[len].push_back(path[i]);
            len++;
        }
        return;
    }
    for (int i = 0; i < g[x].size(); i++) {
        dfs(g[x][i], dp + 1);
    }
}

2.空间问题​

方法1:vector.resize(k)+vector本身也可以用下标(√)​
方法2:int child[100]+int k=0;​

3.查找vector中某值的lower uper​

PAT1043

试比较以下和for循环+i--,会有for第一值退出时多减了 若是递增序列，不如直接找比他小的下一个，比他大的上一个

if(!isMirror) {
    while(i <= tail && pre[root] > pre[i]) i++;
    while(j > root && pre[root] <= pre[j]) j--;
} else {
    while(i <= tail && pre[root] <= pre[i]) i++;
    while(j > root && pre[root] > pre[j]) j--;
}

4.Node形参问题->段错误探讨​

struct Node {
    vector<int> child;
    double sp = 0;
};
void dfs(int x,int dp) {
    int i;
    if(v[x].child.size()!=0) {
        for (i = 0; i<v[x].child.size(); ++i) 
        if (dp+1 > pw.size()-1)
            pw.push_back(pow(r, dp+1));
            dfs(v[x].child[i],dp+1);
    } 
    else sum += 1.0*v[x].sp*p*pw[dp];
}

如果将dfs第一个参数写为Node x会爆空间,更不谈存几个double了,直接用节点图或者层分布图

void dfs(int x, int depth) {
    if (g[x].size() == 0) {
        ans += (dat[x] * pow(1 + r, depth));
        return;
    }
    for (int i = 0; i < g[x].size(); i++) {
        dfs(g[x][i], depth + 1);
    }
}

段错误总结:

(1)越界访问

  • 数组开小了导致指针指向了为开辟的数组区域，出现了越界访问多层
  • for循环中内层循环本来打算写j或者k，却因为习惯或忘记误写成了外层循环的变量i或j，导致数组访问i或j下标的时候发⽣了越界
  • 两次自增的顺序and双重[]数组
    --each[s[start]];
    ++start;

(2)栈空间和堆空间

⼤数组在main函数⾥⾯的话是存储在栈⾥，⽽栈空间是在进程创建时初始化，有固定的⼤⼩，⼀般为⼏⼗KB，所以太⼤的数组会耗光栈空间。⽽全局变量占⽤的堆空间，堆空间中的内存是按需分配，⾃由增⻓的，可以⾮常⼤，⽐如32位的系统中可以⼤到4GB。将⼤数组放在全局变量中能避免栈溢出​

(3)树 null->data,null->left,null->right

Graph​

1.数连通分量(Disjoint Sets)​

PAT1013 Battle Over Cities

当删除其中一个顶点及其相关的边之后，计算出剩下的图的连通分量，那么增加的边就应该是求出的连通分量-1​

法1:每次dfs前判断visit[i]==0;

void dfs(int s) {
    visit[s] = 1;
    for(int i = 1; i<=n; ++i)
    if(g[s][i]==1&&visit[i]==0)dfs(i);
}
...main:
for (i = 0; i < k; ++i) {
    sum = 0;cin >> m;
    fill(visit.begin(),visit.end(),0);
    visit[m] = 1;
    for (j = 1; j<=n; ++j)
        if (visit[j] == 0){dfs(j);sum++;}
    printf("%d\n", sum-1);
}

法2:数根结点father[v]==v;

while(K--){
    int v;int num=0;
    scanf("%d",&v);
    iota(father,father+N+1,0);//初始化并查集
    for(int i=1;i<N+1;++i)
        if(i!=v)for(int j:graph[i])
            if(j!=v)uni(i,j);
    for(int i=1;i<=N;++i)
        if(i!=v&&father[i]==i)
            ++num;
    printf("%d\n",num-1);
}

Leetcode947

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ithi^{th} stone, return the largest possible number of stones that can be removed.

int removeStones(vector<vector<int>>& stones) {
    if(stones.size() <= 1) return 0;
    int res = stones.size(), len = stones.size();
    vector<int> p(len,-1);
    for(int i =0;i < len;i++){
        for(int j = i+1;j < len;j++){
            if(stones[j][0] == stones[i][0] || stones[j][1] == stones[i][1])
                union(p, i, j);
        }
    }
    for(auto e : p){
        if(e == -1) res--;
    }
    return res;
}

2.有关是对边dfs还是点dfs​

PAT1034

给出多个人之间的通话长度，按照这些通话将他们分成若干个组，各个组的总权值是该组内所有通话长度之和，每个人的权值是其参与的所有通话长度之和。求组数和组内通话最长的​

每个点至少有一个连线，故可以对边搜数量关系的运用:边权和=点权和/2

之后的操作--PAT2019春7-3 Telefraud Detection

电信诈骗判断嫌疑犯,若犯人之间通过话说明是一个团伙​
for(i=1;i<=n;++i)
    if(sus[i]==1)
        for(j=i+1;j<=n;++j)
            if(sus[j]==1&&g[i][j]>0&&g[j][i]>0)uni(i,j);
w=1;
for(i=1;i<=n;++i){
    if(sus[i]==1){
        if(mp[findf(i)]==0){
            mp[findf(i)]=w;
            gang[w].push_back(i);
            w++;
        }//将联通分量转换为gang
        else gang[mp[findf(i)]].push_back(i);
    }
}

PAT1021

给定N个结点和N-1条边，问能否构成一棵树，如果能，则输出作为树的根节点时使得整棵树深度最大的结点，如果不能，输出这个图中有几个连通分量。​

能否构成树，要么有>1个连通分量,要么有环

3.Hamiltonian Cycle​

tip
(1)是否是N+1个点​
(2)除起点外，每个点是否只出现了1次​
(3)经过的边是否存在​
(4)起点是否等于终点​
caution

剔除重复点时要用set(往往隐含)

void check(int index) {
    int sum = 0, cnt, flag = 1;
    scanf("%d", &cnt);
    set<int> s;
    vector<int> v(cnt);
    for (int i = 0; i < cnt; i++) {
        scanf("%d", &v[i]);
        s.insert(v[i]);
    }
    for (int i = 0; i < cnt - 1; i++) {
        if(e[v[i]][v[i+1]] == 0) flag = 0;//3
        sum += e[v[i]][v[i+1]];
    }
    if (flag == 0)
    printf("Path %d: NA (Not a TS cycle)\n", index);
    else if(v[0]!=v[cnt-1]||s.size()!=n)//4,2
    printf("Path %d: %d (Not a TS cycle)\n", index, sum);
    else if(cnt != n + 1)printf("Path %d: %d (TS cycle)\n", index, sum);//1
    else printf("Path %d: %d (TS simple cycle)\n", index, sum);
}