力扣刷题日记:时间效率与空间效率均打败100%用户

小鸡
阅读101喜欢0·算法发表2020-06-04更新2020-06-04


昨天公司新人群里前辈发了两题力扣的算法题让大家锻炼,一题简单难度一题中等难度,今天早上做了下,两题均在时间效率和空间效率上击败100%的提交用户,使用的是C++编写,下面分析题目。

第一题:旋转字符串

难度简单

给定两个字符串, A 和 B。

A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde',在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后,A 能变成B,那么返回True。

示例 1:
输入: A = 'abcde', B = 'cdeab'
输出: true
示例 2:
输入: A = 'abcde', B = 'abced'
输出: false

这一题其实就是暴力法直接循环了,理论上时间复杂度最短O(n),最长O(n^2),但是测试用例好像大多比较简单,没想到执行时间这么短。我的方法就是遍历循环字符串B中的与A字符串首字符相同的字符,然后再一层遍历判断两个字符串是否旋转。太简单暴力了。。。  

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :6.4 MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
bool rotateString(string A, string B) {
int lenB = B.length();
if (lenB != A.length())
return false;
for (int i = 0; i < lenB; i++) {
if (B[i] == A[0]) {
for (int j = 0; j < lenB; j++) {
if (j+i < lenB && A[j] != B[j+i] || j+i >= lenB && A[j] != B[j+i-lenB])
goto next;
}
return true;
}
next:;
}
return lenB == 0 ? true : false;
}
};


第二题:重构字符串

难度中等

给定一个字符串S,检查是否能重新排布其中的字母,使得两相邻的字符不同。若可行,输出任意可行的结果。若不可行,返回空字符串。

示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""


这一题同样也是两层循环,在思路有点类似冒泡,第一层遍历的时候,遇到相邻的两个相同元素,考虑以下三种情况:

  1. 能插到头部,则直接插到头部
  2. 后面未遍历的元素有与之不同的,则交换
  3. 前面已经遍历过的元素有两个相邻的不同的元素,则插入
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :6.5 MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
string reorganizeString(string S) {
int lenS = S.length();
for (int i = 1; i < lenS; i++) {
if (S[i] == S[i-1]) {
// 情况1:头部能插入直接在头部插入
if (i == lenS-1 && S[i] != S[0]) {
S.insert(0,1,S[lenS-1]);
S.erase(lenS);
continue;
}
// 情况2:尾部能换直接与尾部元素换
for (int j = i+1; j < lenS; j++) {
if (S[i] != S[j]) {
S[i] = S[j];
S[j] = S[i-1];
goto next;
}
}
// 情况3:前部已排元素能插入则直接插入
for (int j = 0; j < i-1; j++){
if (S[j] != S[i] && S[j+1] != S[i]) {
S.insert(j+1,1,S[i]);
S.erase(i,1);
goto next;
}
}
return "";
next:;
}
}
return S;
}
};


随想
博客
机器学习
教程
邻家酒肆
前端
深度学习
算法
小程序
资源
cpp
html
javascript
python
sql
node

最近文章