第五天-数组
36-有效的数独73-矩阵置零 第六天-字符串
387-字符串中的第一个唯一字符383-赎金信242-有效的字母异位词
第五天-数组 36-有效的数独
思路：简单模拟
利用set或hashmap进行判重操作
其中条件1和2可以一起做
a[i][j] 行 a[j][i] 列
对于3*3宫格内的判重，利用一个二重循环在对应的行列中进行判重即可
class Solution {
public:
bool forsamllmat(int row, int col,vector>& board)
{
set mat;
int size = mat.size();
for(int i=row;i>& board) {
for(int i=0;i<9;i++)
{
set row;
set col;
int size1 = row.size();
int size2 = col.size();
for(int j=0;j<9;j++)
{
if(board[i][j]!='.')
{
row.insert(board[i][j]);
if(row.size()==size1)
return false;
}
if(board[j][i]!='.')
{
col.insert(board[j][i]);
if(size2==col.size())
return false;
}
size1 = row.size();
size2 = col.size();
}
}
int r = 0;
int c = 0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(!forsamllmat(r, c, board))
return false;
r += 3;
}
r = 0;
c += 3;
}
return true;
}
};
73-矩阵置零
思路：将出现零的行列做上标记，再次遍历时，将对应的行列元素变为0
这里用了两种标记的思路：
1. 利用两个固定长度m,n的vector进行标记，分别标记行和列，当某元素的行或列被标记，则置为0 2. 利用不定长的vector，当元素为0时，将其行列从vector中删除，将不在行列vector中的元素置为0
两种实现方法都在下面给出（第二种方法稍微有点笨，但是可以用于练习STL中remove和erase的用法）
//标记方法一
class Solution {
public:
void setZeroes(vector>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector r(row);
vector c(col);
for(int i=0;i
//标记方法二
class Solution {
public:
void setZeroes(vector>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector r,c;
for(int i = 0;i
第六天-字符串
387-字符串中的第一个唯一字符
题目稍微有点绕，他所指的第一个不重复的字符是基于整个字符串来说，所以我们应该统计字符串中的词频，并按照字符串的顺序找到第一个词频为1的字符返回即可
class Solution {
public:
int firstUniqChar(string s) {
if(s=="")
return -1;
unordered_map m;
for(auto &it:s)//统计词频
{
m[it]++;
}
for(int i=0;i
383-赎金信
思路：同样是统计词频……
利用vector进行26个字母的统计，然后依次比较对应字母的词频即可
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
//需要magazine中的字符种类包含ransomNote中的字符种类
vector m1(26), m2(26);
for(int i=0;i
242-有效的字母异位词
思路：上一题的加强版——条件变了变，整体思路依旧是统计词频
class Solution {
public:
bool isAnagram(string s, string t) {
int len1 = s.size();
int len2 = t.size();
if(len1!=len2)//需要长度一致才可能是异位词
return false;
vector m1(26),m2(26);
for(int i=0;i 
