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中配对的另一个人编号。
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的最新下标排除即可，模拟排序子过程。
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;
}
};