前言
纪念一下本站的第一篇文章，希望之后可以定期坚持写些自己感兴趣的东西，不局限于算法。
第一题:矩阵重叠
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 输出：true
示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1] 输出：false
说明：
- 两个矩形
rec1和rec2都以含有四个整数的列表的形式给出。 - 矩形中的所有坐标都处于
-10^9和10^9之间。
解题思路：
这题比较简单只要保证一个矩形的上界大于另一个矩形的下界即可
代码如下：
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
int x1=rec1[0],x2=rec1[2];
int y1=rec1[1],y2=rec1[3];
int X1=rec2[0],X2=rec2[2];
int Y1=rec2[1],Y2=rec2[3];
return (x2>X1&&X2>x1&&y2>Y1&&Y2>y1)?true:false;
}
};
第二题:推多米诺
一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。
在开始时，我们同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。
同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。
就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。
给定表示初始状态的字符串 “S” 。如果第 i 张多米诺骨牌被推向左边，则 S[i] = 'L'；如果第 i 张多米诺骨牌被推向右边，则 S[i] = 'R'；如果第 i 张多米诺骨牌没有被推动，则 S[i] = '.'。
返回表示最终状态的字符串。
示例1:
输入：".L.R...LR..L.."
输出："LL.RR.LLRRLL.."
示例2:
输入： "RR.L"
输出： "RR.L"
说明： 第一张多米诺骨牌没有给第二张施加额外的力。
提示：
0 <= N <= 10^5- 表示多米诺骨牌状态的字符串只含有
'L'，'R'; 以及'.';
解题思路:
- 用栈的结构存储二种数据，
'L','R'。'.'不同存储 - 当输入的是
'R'时压栈，输入是'L'时,栈顶的'R'出栈,多米诺牌向中间推
算法细节:
- 每次都要记录最近操作过的
'L','R'在string中的位置 - 连续遇到两个
'R'要把两个'R'之间的'.'设为'R',连续遇到两个'L'同理 'L'作为第一个遇到的值时要把'L'的左半边都变为'L''R'作为第一个遇到的值时要把'R'的左半边都变为'R'
class Solution {
public:
string pushDominoes(string dominoes) {
vector<int> stack;// 0 left 1 right
int lastR=dominoes.size();
int lastL = -1;
for (int i = 0; i<dominoes.size(); i++) {
if (dominoes[i] == 'R') {
if (stack.size() == 0)
lastR = i;
else {
for (int j = lastR; j <= i; j++)
dominoes[j] = 'R';
lastR = i;
stack.pop_back();
}
stack.push_back(1);
}
if (dominoes[i] == 'L') {
if (stack.size() == 0 && lastL == -1) {
for (int k = 0; k <= i; k++)
dominoes[k] = 'L';
lastL = i;
}
else if (stack.size() == 0 && lastL != -1) {
for (int k = lastL; k <= i; k++)
dominoes[k] = 'L';
lastL = i;
}
else {
lastL = i;
while (lastR + 1<lastL - 1) {
lastR++;lastL--;
dominoes[lastR] = 'R';
dominoes[lastL] = 'L';
}
stack.pop_back();
}
}
}
if(stack.size()!=0){
for(int i=lastR;i<dominoes.size();i++)
dominoes[i]='R';
}
return dominoes;
}
};
第三题:新21点
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
示例1:
输入： N = 10, K = 1, W = 10
输出： 1.00000
说明： 爱丽丝得到一张卡，然后停止。
示例2:
输入: N = 6, K = 1, W = 10
输出 : 0.60000
说明 : 爱丽丝得到一张卡，然后停止。
在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。
示例3:
输入： N = 21, K = 17, W = 10
输出： 0.73278
提示：
0 <= K <= N <= 100001 <= W <= 10000- 如果答案与正确答案的误差不超过
10^-5，则该答案将被视为正确答案通过。 - 此问题的判断限制时间已经减少。
解题思路:
这题用的动态规划的思路，用递归比较容易想但是会超时。
到数字n的几率:dp[n] = sum(dp[n-w]/w + dp[n-w+1]/w + .... dp[n-1]/w)
但是本题限制到>=K之后不再增加。所以当n>=K的时候，dp[n] = sum(dp[n-w]/w + dp[n-w+1]/w + .... dp[K-1]/w)
最后返回结果就是 sum(dp[K:N+1])。
class Solution {
public:
double new21Game(int N, int K, int W) {
vector<double> dp(10001,0);
dp[0]=1;
double now=0;
for(int i=1;i<=N;i++){
if(i<=K) now+=dp[i-1];
if(i>W) now-=dp[i-1-W];
dp[i]=now/W;
}
double ans=0;
for(int i=K;i<=N;i++){
ans+=dp[i];
}
return ans;
}
};
用递归思路很简单，但是会超时- -,代码如下:
class Solution {
public:
double new21Game(int N, int K, int W) {
vector<int> add;
for (int i = 0; i<W; i++) {
add.push_back(i + 1);
}
float res = 0;
float ans = 1;
DFS(add, 0, ans, res, K, N);
return res;
}
void DFS(vector<int> add, int sum, float ans, float &res, int K, int N) {
if (sum >= K) {
if (sum <= N) res += ans;
return;
}
for (auto w : add) {
DFS(add, sum+w, ans/add.size(), res, K, N);
}
}
};
第四题:相似字符串组
如果我们交换字符串X 中的两个不同位置的字母，使得它和字符串Y 相等，那么称 X 和 Y 两个字符串相似。
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；"rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
我们给出了一个不包含重复的字符串列表 A。列表中的每个字符串都是 A 中其它所有字符串的一个字母异位词。请问 A 中有多少个相似字符串组？
示例：
输入：["tars","rats","arts","star"] 输出：2
提示：
A.length <= 2000A[i].length <= 1000A.length * A[i].length <= 20000A中的所有单词都只包含小写字母。A中的所有单词都具有相同的长度，且是彼此的字谜。- 此问题的判断限制时间已经延长。
备注：
字母异位词[anagram]，一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
解题思路:
- 用dif记录2个字符串的相异度，为
2时则为相似 - 构造一个数组构造一个
森林结构，index-根结点index：比如f[2]=3,表示2所在树 的根节点是3 - 每当两个字符串相似的时候，把一棵树的
根节点指向另一棵树的根节点 - 最后的结果返回
根节点的数目
class Solution {
private:
vector<int> f=vector<int> (2001,0);
public:
int findDaddy(int x){
if(f[x]==x) return x;
f[x]=findDaddy(f[x]);
return f[x];
}
int numSimilarGroups(vector<string> A) {
int n = A.size(), len = A[0].size();
for (int i = 0; i<n; i++) f[i] = i;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int dif = 0;
if (i == j) continue;
for (int k = 0; k < len; k++) {
dif += (A[i][k] != A[j][k] ? 1 : 0);
}
if (dif == 2) {
int I=findDaddy(i),J=findDaddy(j);
if(I!=J)f[I]=J;
}
}
}
int ans=0;
for(int i=0;i<n;i++)
{
int fa=findDaddy(i);
if(fa==i)ans++;
}
return ans;
}
};
