Count Binary Substrings
"""简单,但是需要判断啥时候计数“清零”
"""
class Solution {
public:
int countBinarySubstrings(string s) {
if(s.size()<=1)
return 0;
int zero = 0, one = 0, res=0;
char pre = s[0];
for(char c:s){
if(c=='0'){
if(pre == '1')
zero = 1;
else
zero++;
if(one>=zero)
res++;
}
if(c=='1'){
if(pre == '0')
one = 1;
else
one++;
if(zero>=one)
res++;
}
pre = c;
}
return res;
}
};
"""简洁
http://www.cnblogs.com/grandyang/p/7716150.html
"""
class Solution {
public:
int countBinarySubstrings(string s) {
int res = 0, pre = 0, cur = 1, n = s.size();
for (int i = 1; i < n; ++i) {
if (s[i] == s[i - 1]) ++cur;
else {
pre = cur;
cur = 1;
}
if (pre >= cur) ++res;
}
return res;
}
};
Degree of an Array
"""仔细分析,一次循环一次过!
"""
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
unordered_map<int,int> m;
unordered_map<int, pair<int,int>> m2;
int n = 0, res = 0;
for(int j=0;j<nums.size();j++){
int i = nums[j];
m[i] ++;
if(n<m[i])
res = j-m2[i].first+1;
if(n==m[i])
res = min(res, j-m2[i].first+1);
n = max(n, m[i]);
if(m[i] ==1)
m2[i] = {j,j};
else
m2[i].second = j;
}
return res;
}
};
1-bit and 2-bit Characters
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
int i = 0, n = bits.size();
while(i<n-1){
i = bits[i]==0? i+1:i+2;
}
return i==n-1;
}
};
Longest Word in Dictionary
class Solution {
public:
string longestWord(vector<string>& words) {
string res;
unordered_set<string> s;
sort(words.begin(), words.end());
for(int j=0;j<words.size();j++){
string i = words[j];
if(i.size()==1 || s.count(i.substr(0,i.size()-1))){
res = res.size()<i.size()?i:res;
s.insert(i);
}
}
return res;
}
};
Find Pivot Index
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int s = 0, cur = 0;
for(int i=0;i<nums.size();i++){
s += nums[i];
}
for(int i=0;i<nums.size();i++){
if(s-nums[i]==2*cur)
return i;
cur += nums[i];
}
return -1;
}
};
Self Dividing Numbers
class Solution {
public:
bool helper(int n){
int m = n;
while(m){
if(m%10==0 || n%(m%10)!=0)
return false;
m/=10;
}
return true;
}
vector<int> selfDividingNumbers(int left, int right) {
vector<int> res;
for(int i=left;i<=right;i++){
if(helper(i))
res.push_back(i);
}
return res;
}
};
Flood Fill
"""
LeetCode -- reference binding to null pointer of type 'value_type'
https://blog.csdn.net/m0_38088298/article/details/79249044
另外: if(val == newColor)
return image;
一句避免了A添加B进队列,B又添加A的死循环。
"""
class Solution {
public:
bool out_of_bound(int m, int n, int i, int j){
return (i<0 || j<0 || i>=m || j>=n);
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
//BFS
int val = image[sr][sc];
if(val == newColor)
return image;
vector<vector<int>> dirs = {{0,-1},{0,1},{-1,0},{1,0}};
int m = image.size();
int n = image[0].size();
queue<vector<int>> q;
q.push({sr,sc});
image[sr][sc] = newColor;
while(!q.empty()){
for(vector<int> dir:dirs){
int i = q.front()[0]+dir[0];
int j = q.front()[1]+dir[1];
if(!out_of_bound(m,n,i,j)){
if(image[i][j] == val){
image[i][j] = newColor;
q.push({i,j});
}
}
}
q.pop();
}
return image;
}
};
Find Smallest Letter Greater Than Target
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
for(char c: letters){
if(c>target)
return c;
}
return letters[0];
}
};
Largest Number At Least Twice of Others
class Solution {
public:
int dominantIndex(vector<int>& nums) {
int first = 0;
int second = 0;
int p = 0;
for(int i=0;i<nums.size();i++){
int n = nums[i];
if(n>first){
second = first;
first = n;
p = i;
}
else if(n>second)
second = n;
}
return first>=2*second?p:-1;
}
};
Prime Number of Set Bits in Binary Representation
class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
for(int j=L;j<=R;j++){
int i = j;
int cur = 0;
while(i){
cur += i&1;
i>>=1;
}
if(cur%2!=0 && cur%3!=0 && cur>1)
res++;
if(cur==2||cur==3)
res++;
}
return res;
}
};
"""简短--
"""
class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
for (int i = L; i <= R; ++i) {
int cnt = __builtin_popcount(i);
res += cnt < 4 ? cnt > 1 : (cnt % 2 && cnt % 3);
}
return res;
}
};
Minimum Distance Between BST Nodes
class Solution {
public:
void helper(TreeNode* node, int& res, int& pre){
if(!node)
return;
helper(node->left, res, pre);
if(pre!=-1)
res = min(res, node->val-pre);
pre = node->val;
helper(node->right, res, pre);
}
int minDiffInBST(TreeNode* root) {
int res = INT_MAX;
int pre = -1;
helper(root, res, pre);
return res;
}
};
Letter Case Permutation
class Solution {
public:
void helper(string S, vector<string>& res, int i){
if(i==S.size()){
res.push_back(S);
return;
}
helper(S,res,i+1);
if(isalpha(S[i])){
S[i]=isupper(S[i]) ? tolower(S[i]) : toupper(S[i]);
helper(S,res,i+1);
}
}
vector<string> letterCasePermutation(string S) {
vector<string> res;
helper(S, res, 0);
return res;
}
};
Rotate String
class Solution {
public:
bool rotateString(string A, string B) {
if(A.size()!=B.size())
return false;
if(A=="" && B=="")
return true;
for(int i=0;i<A.size();i++){
int k = 0;
for(int j=i;j<A.size()+i;j++){
if(A[j%A.size()] != B[(k++)%A.size()])
break;
if(k==A.size()-1)
return true;
}
}
return false;
}
};
Unique Morse Code Words
"""这里用了set。
"""
class Solution {
public:
int uniqueMorseRepresentations(vector<string>& words) {
vector<string> mos={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
unordered_set <string> encodes;
for(string word:words){
string encode = "";
for(char c:word){
encode+=mos[c-'a'];
}
encodes.insert(encode);
}
return encodes.size();
}
};