# 242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false.

Note: You may assume the string contains only lowercase alphabets.

/*solution 1,52ms*/
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.empty()&&t.empty())
return true;
if(s.size()!=t.size())
return false;
unordered_map<char,int> hash;
unordered_map<char,int> hash2;
bool flag=false;
for(int i=0;i<s.size();i++)
hash[s[i]]++;
for(int i=0;i<t.size();i++)
hash2[t[i]]++;
for(int i=0;i<s.size();i++){
if(hash[s[i]]==hash2[s[i]])
flag=true;
else
return false;
}
return flag;
}
};



• 当s中的字母被储存在哈希表中时，其对应的值+1;
• 当t中的字母被储存在哈希表中时，其对应的值-1;

/*solution2 36ms*/
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size()!=t.size())
return false;
unordered_map<char,int> hash;
for(int i=0;i<s.size();i++){
hash[s[i]]++;
hash[t[i]]--;
}
for(auto pos:hash)
if(pos.second!=0)
return false;
return true;
}
};



/*solution 3,use array instead of hash-table,12ms*/
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size()!=t.size())
return false;
int count[26]={0};
for(int i=0;i<s.size();i++){
count[s[i]-'a']++;
count[t[i]-'a']--;
}
for(int pos:count)
if(pos!=0)
return false;
return true;
}
};


# 204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

class Solution {
public:
int countPrimes(int n) {
int count=0;
bool isprime[n];
for(int i=0;i<n;i++)
isprime[i]=true;
for(int i=2;i<sqrt(n);i++){
if(isprime[i]){
for(int j=2;j*i<n;j++)
isprime[j*i]=false;
}
}
for(int i=2;i<n;i++){
if(isprime[i]==true)
count++;
}
return count;
}
};


# 378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.


Note: You may assume k is always valid, 1 ≤ k ≤ n2.

/*solution 1,use heap,144ms,O(n^2 *  logk),k is the size of heap*/
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
priority_queue<int> heap;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[i].size();j++){
heap.emplace(matrix[i][j]);
if(heap.size()>k)
heap.pop();
}
}
return heap.top();
}
};


1. 大于或等于k,说明选择的mid太大，需要调整到左半区，则high=mid-1;
2. 小于k，说明我们选定的mid太小，需要调整到右半区，则low=mid+1;

/*solution 2,use binary-search,O(nlogn),56ms*/
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int low=matrix[0][0],n=matrix.size(),high=matrix[n-1][n-1],cnt=0,mid=low+((high-low)>>1);
while(low<=high){
mid=low+((high-low)>>1);
cnt=0;
for(int i=0;i<matrix.size();i++)
cnt=cnt+upper_bound(matrix[i].begin(),matrix[i].end(),mid)-matrix[i].begin();
if(cnt<k)
low=mid+1;
else
high=mid-1;
}
return low;
}
};


# 74.Search a 2D Matrix

74.Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example,

Consider the following matrix:

[
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]


Given target = 3, return true.

/*solution1
Traverse the 2D matrix*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())
return false;
int i=0,j=0;
int row=matrix.size(),col=matrix[0].size();
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(matrix[i][j]==target)
return true;
return false;
}
};


/*solution2
use binary-search in rows*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())
return false;
int row=matrix.size(),i=0;
int low=0,size=matrix[0].size(),high=size-1,mid=0;
for(i=0;i<row;i++){
low=0;
high=size-1;
while(low<=high){
mid=low+(high-low)/2;
if(matrix[i][mid]==target)
return true;
if(matrix[i][mid]<target)
low=mid+1;
else
high=mid-1;
}
}
return false;
}
};



class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())
return false;
int low=0,size=matrix.size(),high=size-1,mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(matrix[mid][0]==target)
return true;
if(matrix[mid][0]>target)
high=mid-1;
else
low=mid+1;
}
int row=high;

if(row<0)
return false;
low=0;
high=matrix[0].size()-1;
mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(matrix[row][mid]==target)
return true;
if(matrix[row][mid]>target)
high=mid-1;
else
low=mid+1;
}
return false;
}
};


# 66.Plus One

66.Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

/*solution1*/
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int i=0,size=digits.size(),carry=1;
for(i=size-1;i>=0;i--){
int digit=(digits[i]+carry)%10;
carry=(digits[i]+carry)/10;
digits[i]=digit;
if(carry==0)
return digits;
}
vector<int> res(size+1,0);
res[0]=1;
return res;
}
};



/*solution2*/
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int i=0,size=digits.size();
for(i=size-1;i>=0;i--){
if(digits[i]==9)
digits[i]=0;
else{
digits[i]++;
return digits;
}
}
digits[0]=1;
digits.push_back(0);
return digits;
}
};