-
Notifications
You must be signed in to change notification settings - Fork 1.3k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
关于2337.Move-Pieces-to-Obtain-a-String 是否说反了? #47
Comments
这题我想了一上午,三种方法来搞都没跑通。 1.两边dp要两边dp,记录每个L/R 经过滑动可以出现的位置,然后检查target[i],如果是L就检查l[],否则检查r[],看对应位置是否可能相同。 class Solution {
public:
bool canChange(string s, string t) {
string l(1, s.back()), r(1, s[0]);
int sl = count(all(s), 'L');
int sr = count(all(s), 'R');
int tl = count(all(t), 'L');
int tr = count(all(t), 'R');
if (sl != tl || sr != tr)
return false;
//处理R
for (int i = 1; i < s.size(); ++i)
if (r.back() == 'R' && s[i] == '_')
r += 'R';
else
r += s[i];
//处理L
for (int i = s.size() - 2; i >= 0; --i)
if (l.back() == 'L' && s[i] == '_')
l += 'L';
else
l += s[i];
std::reverse(all(l));
for (int i = 0; i < t.size(); ++i)
{
if (t[i] == 'L' && t[i] == l[i])continue;
if (t[i] == 'R' && t[i] == r[i])continue;
if (t[i] == '_'&&s[i]=='_') continue;
return false;
}
return true;
}
}; 2.双指针分别扫描L/R,要求它在s里出现的位置必须小于/大于 t里出现的位置 class Solution {
public:
bool canChange(string s, string t) {
int sl = count(all(s), 'L'),sr = count(all(s), 'R'),tl = count(all(t), 'L'),tr = count(all(t), 'R');
if (sl != tl || sr != tr)return false;
//r从左向右扫,t里存在的都挪动s.
int r = 0;
for (int i = 0; i < t.size(); ++i)
{
if (t[i] == 'R') {
while (r < s.size() && s[r] != 'R')++r;
if (r == t.size())return false;
++r;
}
}
//l从右往左扫描,t里存在的都往前挪s
int l = t.size() - 1;
for (int i = t.size() - 1; i >= 0; --i)
{
if (t[i] == 'L') {
while (l >= 0 && s[l] != 'L')--l;
if (l == 0)return false;
--l;
}
}
//这个扫法也有问题,对于
//"R_L_"
// "__LR"
// 该是0 却返回1,双指针初试失败
return true;
}
}; 跟您的答案可以说就差亿点点了。 |
是的,文字解释里的这个逻辑写反了。刚改正了过来。谢谢提醒。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
来自这里
题目里写的是:
我看了代码
这句是为了保证target里某个L所在的index比start 靠左,对吗?
没看视频,因为您的文字版向来简洁精炼,不知道视频怎么讲的 >_<
The text was updated successfully, but these errors were encountered: