1583. 统计不开心的朋友 #模拟 #暴力

题目链接

题意

有n为朋友，对每位朋友i，preference[i]包含 按亲密度从大到小 的朋友编号。

朋友们会被分为若干对，配对情况由pairs数组给出，即pair[i]={xi, yi}表示xi与yi相互配对。

当x与y相互配对且u与v相互配对的情况下，如果同时满足下面两个条件，x就会不高兴：

  • x->u亲密度 大于 x->y；
  • u->x亲密度 大于 u->v；

分析

初看题目，我以为一旦满足上述两条件，不但x不高兴，u也会不高兴。然而，这是错的。

对于数据6, preferences=[[1,4,3,2,5],[0,5,4,3,2],[3,0,1,5,4],[2,1,4,0,5],[2,1,0,3,5],[3,4,2,0,1]], pairs = [[3,1],[2,0],[5,4]]，只有5号是高兴的，这是因为5号对4号亲密度太高(rank=4)，5号只能去找1（rank=5），然而1号对3号的亲密度更高(rank=5)，被3号锁住，因而5是高兴的。

由此，我们不应该遍历pairs，而是将pairs中的配对情况记录到每个人身上，再遍历每个人，检查是否不开心。

下面代码中rank[i][j]代表i号对j号的亲密度。而mypair[i]代表i在pair中配对的另一个人编号。

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
class Solution {
private:
    int rank[505][505], mypair[505];
public:
    bool Judge(int cur, int n){ //判断是否不开心
        int p = mypair[cur];
        for (int i = 0; i < n; i++){
            if(rank[cur][p] < rank[cur][i]
            && rank[i][mypair[i]] < rank[i][cur]) //按照题目要求
                return true;
        }
        return false;
    }
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n - 1; j++) 
                rank[i][preferences[i][j]] = n - j; //存下i的朋友亲密度
        for (int i = 0; i < n / 2; i ++){ //将每对pair中两人对应队友记录下来
            mypair[pairs[i][0]] = pairs[i][1]; 
            mypair[pairs[i][1]] = pairs[i][0];
        }
        int ans = 0;
        for(int i = 0; i < n; i++) 
            if(Judge(i, n)) ans++;
        return ans;
    }
};

1585. 检查字符串是否可以通过排序子字符串得到另一个字符串 #暴力 #排序思想 #模拟

题目链接

题意

给定字符串s和t，可通过若干次的下述操作将s转化为t——选择s中一个非空子字符串并将它包含的字符就地升序排序。现要你判断s通过这些操作能否得到t。其中子字符串定义为一个字符串中连续的若干字符。

分析

更详细的证明过程参考零神的题解

模拟s到t的过程，对t串一个个字符进行考虑。首先考虑t[0]（t串的首字符）在s串中首位置，记为s[t_0](=t[0])。我们怎么知道字符s[t_0]能否通过排序使其放到s首位呢？只有当s[t_0]都小于s[0],s[1],...,s[t_0 - 1]这些元素，即比s[t_0]小的元素 都在s[t_0]的右侧，这时候s[t_0]有机会通过排序将原来位置降到s的首位置。当我们比较完，确定满足该条件时，s[t_0]以后不再考虑，转而考虑下一字符t[1]，找到在s中对应的 最前位置s[t_i]，判断s[t_i]能否移动到s中的第1个位置……

如何实现？我们为10个数字的每个数字都准备一个队列，用来存储该数字在s串中的位置。为什么要用队列？因为我们在检查cur前面的数字是否在cur左侧时，只需要用查询数字0,1,...,cur-1的当前一个位置即可，若检查不出，说明可以将cur搬到前面，接下来直接将该cur的最新下标排除即可，模拟排序子过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isTransformable(string s, string t) {
        vector< queue<int> > pos(10);
        for (int i = 0; i < s.length(); i++)
            pos[s[i] - '0'].push(i); //存下每一种数字在s串中的位置
        for (int i = 0; i < t.length(); i++){ //遍历t串中每一个字符
            int cur = t[i] - '0';
            if(pos[cur].empty()) //说明s串字符数量与t串不相等，显然无法满足题意
                return false;
            for (int j = 0; j <= cur; j++){ //检查s串中 比t[i]小 的字符 所在的下标
                if(!pos[j].empty() && pos[j].front() < pos[cur].front())
                    return false; 
                //如果t串中t[i]的左边，存在一个比t[i]还小的字符，显然不能将t[i]冒泡到前面
            }
            pos[cur].pop(); //即时更新数字cur的下标
        }
        return true;
    }
};