昨天休息了一天，今天继续开始！
8道easy+8道medium还行
(medium)48. 旋转图像
一个很简单找规律题，问题在于其要求不使用另一个矩阵来存储；而我们可以发现，若从i,j开始旋转，旋转4次就不会出现重复旋转/少旋转的情况，因而我们直接旋转四次，然后i j的范围为[0,n/2)和[0,(n+1)/2]。代码如下：
int vis[21][21];
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
//若行从0开始，则第i行->n-i-1列; i,j->(j,n-i-1);->(n - i - 1,n - j - 1);->(n - j - 1,i)
for(int i=0;i<n/2;i++)
{
for(int j=0;j<(n+1)/2;j++)
{
//temp[j][n-i-1] = matrix[i][j];
int temp = matrix[i][j];
//左下角到左上角
matrix[i][j] = matrix[n - j - 1][i];
//右下角到左下角
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
//右上角到右下角
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
//左上角到右上角
matrix[j][n - i - 1] = temp;
}
}
return ;
}
};(medium)73. 矩阵置零
没想到用第一行第一列来作为标志位存储，一直想用个东西来存储i行/列是否有0。想到这个思路之后就很简单了。代码如下：
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
//flag1是第一行是否有0的标志位，flag2是第一列
bool flag1=0;
bool flag2=0;
for(int i=0;i<n;i++)
{
if(!matrix[0][i])
{
flag1 = 1;
break;
}
}
for(int i=0;i<m;i++)
{
if(!matrix[i][0])
{
flag2 = 1;
break;
}
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
if(!matrix[i][j])
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i=1;i<m;i++)
{
if(!matrix[i][0])
{
for(int j=1;j<n;j++)
{
matrix[i][j] = 0;
}
}
}
for(int j=1;j<n;j++)
{
if(!matrix[0][j])
{
for(int i=1;i<m;i++)
{
matrix[i][j] = 0;
}
}
}
if(flag1)
{
for(int i=0;i<n;i++)
matrix[0][i] = 0;
}
if(flag2)
{
for(int i=0;i<m;i++)
matrix[i][0] = 0;
}
return ;
}
};(medium)289. 生命游戏
一道很有趣的位运算题，由于board[i][j]只可能为1或0，那么我们就可以用高位记录下一次的状态，然后整体运行完之后再把高位转移到低位；这种也可拓展为限制了board[i][j]数据范围的状态转移题。代码如下：
int mx[9] = {0,0,1,-1,-1,-1,1,1};
int my[9] = {1,-1,0,0,-1,1,-1,1};
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int m = board.size();
int n = board[0].size();
int cnt = 0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(board[i][j]&1)
{
cnt = 0;
for(int k=0;k<8;k++)
{
if(i+mx[k]>=0&&i+mx[k]<m&&j+my[k]>=0&&j+my[k]<n)
if(board[i+mx[k]][j+my[k]]&1)
cnt++;
}
if(cnt == 2 || cnt == 3)
board[i][j] += 2;
}
else
{
cnt = 0;
for(int k=0;k<8;k++)
{
if(i+mx[k]>=0&&i+mx[k]<m&&j+my[k]>=0&&j+my[k]<n)
if(board[i+mx[k]][j+my[k]]&1)
cnt++;
}
if(cnt == 3)
board[i][j] += 2;
}
}
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
board[i][j] = board[i][j] >> 1;
return ;
}
};(easy)383. 赎金信
本来由于字符串只由小写字母构成只用数组a[26]即可，但是是属于哈希表专题，所以还是用哈希表吧(。代码如下：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int n = ransomNote.size();
int m = magazine.size();
unordered_map<char,int> a;
for(int i=0;i<m;i++)
a[magazine[i]]++;
for(int i=0;i<n;i++)
{
if(!a[ransomNote[i]])
return 0;
a[ransomNote[i]]--;
}
return 1;
}
};(easy)205. 同构字符串
也是一道哈希表版题，没啥可说的。代码如下：
class Solution {
public:
bool isIsomorphic(string s, string t) {
int n = s.size();
unordered_map<char,int> a;
unordered_map<char,int> b;
unordered_map<char,char> ys;
unordered_map<char,bool> vis;
int cnt = 0;
for(int i=0;i<n;i++)
{
a[s[i]]++;
b[t[i]]++;
vis[t[i]] = 0;
}
for(int i=0;i<n;i++)
{
if(a[s[i]]!=b[t[i]])
{
return 0;
}
else
{
if(!ys[s[i]])
{
if(vis[t[i]])
return 0;
ys[s[i]] = t[i];
vis[t[i]] = 1;
}
else if(ys[s[i]]!=t[i])
return 0;
}
}
return 1;
}
};(easy)290. 单词规律
也是哈希表版题，我逐渐理解哈希表的一切.jpg。代码如下：
class Solution {
public:
bool wordPattern(string pattern, string s) {
int n = pattern.size();
int m = s.size();
unordered_map<char,string> a;
unordered_map<string,char> b;
unordered_map<char,bool> vis;
int st = 0;
int cnt = 0;
int length = 0;
bool isst = 0;
for(int i=0;i<m;i++)
{
if(s[i]!=' ')
{
if(!isst)
{
isst = 1;
st = i;
}
length++;
}
else if(isst)
{
string temp = s.substr(st,length);
if(cnt>n)
return 0;
if(!vis[pattern[cnt]])
{
if(b[temp] && b[temp]!=pattern[cnt])
return 0;
vis[pattern[cnt]] = 1;
a[pattern[cnt]] = temp;
b[temp] = pattern[cnt];
}
else if(a[pattern[cnt]] != temp)
return 0;
printf("%s",s.substr(st,length).c_str());
cnt++;
length = 0;
isst = 0;
}
}
if(isst)
{
string temp = s.substr(st,length);
printf("%s",s.substr(st,length).c_str());
if(cnt>n)
return 0;
if(!vis[pattern[cnt]])
{
if(b[temp] && b[temp]!=pattern[cnt])
return 0;
vis[pattern[cnt]] = 1;
a[pattern[cnt]] = temp;
b[temp] = pattern[cnt];
}
else if(a[pattern[cnt]] != temp)
return 0;
}
if(cnt!=n-1)
return 0;
return 1;
}
};(easy)242. 有效的字母异位词
这位更是easy级，我的代码针对进阶情况，因而使用哈希表而不是数组。代码如下：
class Solution {
public:
bool isAnagram(string s, string t) {
int n = s.size();
int m = t.size();
if(n!=m)
return 0;
unordered_map<char,int> a;
for(int i=0;i<n;i++)
{
a[s[i]]++;
a[t[i]]--;
}
for(int i=0;i<n;i++)
if(a[s[i]])
return 0;
return 1;
}
};(medium)49. 字母异位词分组
我的思路很简单，就是把strs[i]取出来排个序，如果新的有序字符串出现过那就把它push_back进原本的序列，不然就新建一个以它为首的序列。代码如下：
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
int n = strs.size();
int cnt = 0;
unordered_map<string,int> num;
unordered_map<string,bool> vis;
vector<vector<string>> ans;
for(int i=0;i<n;i++)
{
string s = strs[i];
sort(s.begin(),s.end());
if(!vis[s])
{
num[s] = cnt;
vis[s] = 1;
ans.push_back({});
cnt++;
}
ans[num[s]].push_back(strs[i]);
}
return ans;
}
};(easy)1. 两数之和
也是很简单的一个思路，检查target-nums[i]的值是否存在即可。我算了下我的效率应该是O(2*n*map调用效率+n)。代码如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
int n = nums.size();
unordered_map<int,int> a;
for(int i=0;i<n;i++)
{
a[nums[i]]++;
}
for(int i=0;i<n;i++)
{
int temp = target - nums[i];
a[nums[i]]--;
if(a[temp])
{
ans.push_back(i);
for(int j=0;j<n;j++)
{
if(j != i && nums[j] == temp)
{
ans.push_back(j);
return ans;
}
}
}
a[nums[i]]++;
}
return ans;
}
};(easy)202. 快乐数
也是很简单的一个判重，因为如果不是快乐数就会陷入无限循环，所以只要判断现在计算到的数是否计算过就行。因为需要判断的数很小(2^31换算成十进制也才10位，然后10位数每位为9，平方加起来也才9*9*10=810)，所以我最开始使用的数组，但是因为是在哈希表专题所以用哈希表；不过我的数组肯定更快(。数组代码如下：
bool vis[811];//9*9*10=810
class Solution {
public:
int target(int n)
{
int sum = 0;
int temp;
while(n>=10)
{
temp = n % 10;
sum = sum + (temp * temp);
n = n / 10;
}
sum = sum + (n * n);
return sum;
}
bool isHappy(int n) {
memset(vis,0,sizeof(vis));
if(n == 1)
return 1;
if(n>810)
n = target(n);
while(!vis[n])
{
if(n == 1)
return 1;
vis[n] = 1;
n = target(n);
}
return 0;
}
};哈希表版代码如下：
class Solution {
public:
int target(int n)
{
int sum = 0;
int temp;
while(n)
{
temp = n % 10;
sum = sum + (temp * temp);
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(set.find(n) == set.end())
{
if(n == 1)
return 1;
set.insert(n);
n = target(n);
}
return 0;
}
};(easy)219. 存在重复元素 II
很简单的一道贪心+哈希表思路，每次更新最新遍历到的nums[i]位置即可。代码如下：
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int,int> pos1;
for(int i=n-1;i>=0;i--)
{
if(!pos1[nums[i]])
pos1[nums[i]] = i;
else
{
if(pos1[nums[i]]-i<=k)
return 1;
pos1[nums[i]] = i;
}
}
return 0;
}
};(medium)128. 最长连续序列
一道官方优化方式很好的题，我自己的想法是300ms上下，加了个官方的优化就直接快的多了，不过我直接sort的效率比官方的快(
官方优化+set代码如下：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
int maxn = 0;
unordered_set<int> set;
for(int i=0;i<n;i++)
{
set.insert(nums[i]);
}
for(auto l : set)
{
if(set.count(l + maxn)&&!set.count(l - 1))
{
int r = l;
while(set.count(r + 1))
r++;
maxn = max(maxn,r - l + 1);
//l = r;最开始以为set可以按顺序调用，后面发现不行，不然的话应该跟官方哪个set.count(l-1) == 0的优化是一个道理
}
}
return maxn;
}
};sort版本代码如下：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
int maxn = 0;
sort(nums.begin(),nums.end());
int i=0;
while(i<n)
{
int temp = 1;
int r = i;
while(r+1<n&&nums[r+1]<=nums[r]+1)
{
temp++;
r++;
}
maxn = max(maxn,nums[r]-nums[i]+1);
if(i!=r)
i = r;
else
i++;
}
return maxn;
}
};(easy)228. 汇总区间
很简单的一个，对我最大的问题是处理输出(悲)。输出的转换是抄的题解，我是真不会(。代码如下：
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
int n = nums.size();
int l = 0;
int r = 0;
vector<string> ans;
while(r < n && l < n)
{
r = l;
while(r<n-1&&nums[r + 1] == nums[r] + 1)
{
r++;
}
if(l == r && r < n)
{
string temp = to_string(nums[l]);
//printf("%d\n",nums[l]);
l++;
ans.push_back(move(temp));
}
else if(r < n)
{
string temp = to_string(nums[l]);
temp.append("->");
temp.append(to_string(nums[r]));
ans.push_back(move(temp));
//printf("%d->%d\n",nums[l],nums[r]);
l = r + 1;
}
}
return ans;
}
};(medium)56. 合并区间
很简单的一道区间排序，唯一问题就是我对多重vector数组的使用还是不够熟练。代码如下：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
int n = intervals.size();
int i=0;
vector<vector<int>> ans;
while(i<n)
{
int l = intervals[i][0];
int r = intervals[i][1];
int j = i + 1;
while(j<n&&intervals[j][0]<=r)
{
r = max(r, intervals[j][1]);
j++;
}
ans.push_back({l,r});
i = j;
}
return ans;
}
};(medium)57. 插入区间
内容其实和上道题大差不差，只不过是需要注意判断在什么情况下插入、插入之后是否合并。代码如下：
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n = intervals.size();
int ln = newInterval[0];
int rn = newInterval[1];
vector<vector<int>> ans;
int i=0;
bool newflag = 0;
while(i<n)
{
int l = intervals[i][0];
int r = intervals[i][1];
int j = i + 1;
if(!newflag)
{
//可合并
if(ln<=r&&rn>=l)
{
newflag = 1;
l = min(l,ln);
r = max(r,rn);
while(j<n&&r>=intervals[j][0])
{
l = min(l,intervals[j][0]);
r = max(r,intervals[j][1]);
j = j + 1;
}
}
//单独一个区间
else if(ln<=r)
{
newflag = 1;
ans.push_back(newInterval);
}
}
ans.push_back({l,r});
i = j;
}
if(!newflag)
ans.push_back(newInterval);
return ans;
}
};(medium)452. 用最少数量的箭引爆气球
换皮题，之前合并区间是求合集，这里是求交集；找一个点能被最多的框框住，就是一个sort完之后左区间取max,右区间取min的题。代码如下：
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end());
int n = points.size();
int i = 0;
int ans = n;
while(i < n)
{
int j = i + 1;
int l = points[i][0];
int r = points[i][1];
while(j<n&&points[j][0]>=l&&points[j][0]<=r&&l<=r)
{
ans--;
l = max(l,points[j][0]);
r = min(r,points[j][1]);
j++;
}
i = j;
}
return ans;
}
};