A.二进制矩阵中的特殊位置

解题思路：
预处理所有行列和，遍历所有元素，如果该元素为1，并且行列和都为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
class Solution {
public:
    int rows[105],cols[105];
    int numSpecial(vector<vector<int>>& mat) {
        int n = mat.size();
        if(!n)  return 0;
        int m = mat[0].size();
        memset(rows,0,sizeof(rows));
        memset(cols,0,sizeof(cols));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                rows[i] += mat[i][j];
                cols[j] += mat[i][j];
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mat[i][j]==1 && rows[i]==1 && cols[j]==1)
                    ans++;
            }
        }
        return ans;
    }
};

B.统计不开心的朋友

解题思路：
模拟。
代码展示：

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
class Solution {
public:
    int pei[505];
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        for(int i=0;i<n/2;i++){
            int x = pairs[i][0],y = pairs[i][1];
            pei[x] = y; pei[y] = x;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            int x = i,y = pei[i];
            for(int j=0;j<n;j++){
                int u = preferences[i][j];
                if(u==y)    break;
                bool tmp=false;
                for(int k=0;k<n;k++){
                    int v = preferences[u][k];
                    if(v == pei[u]) break;
                    if(v==x){
                        tmp=true;break;
                    }
                }
                if(tmp){
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
};

C.连接所有点的最小费用

解题思路：
最小生成树，并查集。任意两点生成边，边长为两点的曼哈顿距离。答案即为此无向图的最小生成树的边和。最小生成树Kruskal算法：把图中的所有边按边长从小到大排序；按边长从小到大选择边，所选的边连接的两个顶点不在一个集合内，则选择此边，并将两个顶点所在集合合并，直到选择到n条边。判定是否在一个内以及集合合并采用并查集完成。
代码展示：

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 Solution {
public:
    int fa[1005];
    struct node{
        int fr,to,dis;
        node(int f,int t,int d){
            fr = f; to = t; dis = d;
        }
    };
    int find(int x){
        if (x == fa[x])
            return x;
        else
            return fa[x] = find(fa[x]);
    }
    static bool cmp(node x,node y){
        return x.dis<y.dis;
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(),ans=0;
        vector<node> d;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int t = fabs(points[i][0]-points[j][0])+fabs(points[i][1]-points[j][1]);
                d.push_back(node(i,j,t));
            }
        }
        sort(d.begin(),d.end(),cmp);
        for (int i = 0; i < n; i++)
            fa[i] = i;
        int m = d.size();
        for (int i = 0; i < m; i++){
            int x = find(d[i].fr), y = find(d[i].to);
            if (x != y){
                fa[x] = y;
                ans += d[i].dis;
            }
        }
        return ans;
    }
};

D. 检查字符串是否可以通过排序子字符串得到另一个字符串

解题思路：
贪心。逆序对的个数不能增加。预处理s中每个字符的位置，遍历t中所有字符，需要保证所有字典序小的字符不能出现在后面。

代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isTransformable(string s, string t) {
        int n = s.size();
        vector< queue<int> > ts(10);
        for(int i=0;i<s.size();i++){
            ts[s[i]-'0'].push(i);
        }
        for(int i=0;i<n;i++){
            int d = t[i]-'0';
            if(ts[d].empty())   return false;
            for(int j=0;j<d;j++){
                if(!ts[j].empty() && ts[j].front() < ts[d].front()) return false;
            }
            ts[d].pop();
        }
        return true;
    }
};

做题情况：
AC 三题
排名：312 / 4492
总结反思：
第二题又读错题了，Wa了一发，第四题有大概思路，但不够完整。