https://leetcode.com/problems/word-pattern/description/
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Examples:
"abba", str = "dog cat cat dog" should return true."abba", str = "dog cat cat fish" should return false."aaaa", str = "dog cat cat dog" should return false."abba", str = "dog dog dog dog" should return false.Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
bool wordPattern(string pattern, string str)
{
map<char, string> mapPatternToString;
map<string, char> mapStringToPattern;
vector<string> vecSubString = splitString(str, ' ');
if (vecSubString.size() != pattern.size())
{
return false;
}
for (int i = 0; i < vecSubString.size(); i++)
{
char c = pattern[i];
map<char, string>::iterator iterPTS = mapPatternToString.find(c);
if (iterPTS == mapPatternToString.end())
{
mapPatternToString.insert(std::pair<char, string>(c, vecSubString[i]));
}
else
{
if (strcmp(iterPTS->second.c_str(), vecSubString[i].c_str()) != 0)
{
return false;
}
}
map<string, char>::iterator iterSTP = mapStringToPattern.find(vecSubString[i]);
if (iterSTP == mapStringToPattern.end())
{
mapStringToPattern.insert(std::pair<string, char>(vecSubString[i], c));
}
else
{
if (iterSTP->second != c)
{
return false;
}
}
}
return true;
}
vector<string> splitString(string str, char sep)
{
vector<string> result;
string strSubString;
const char * pcStr = str.data();
for (int i = 0; i <= str.size(); i++)
{
if (i == str.size() || str[i] == ' ')
{
strSubString.append(1, '\0');
result.push_back(strSubString);
strSubString.clear();
}
else
{
strSubString.append(1, str[i]);
}
}
return result;
}
};
int main()
{
Solution o;
bool bRet = o.wordPattern("jquery", "jquery");
return 0;
}
https://leetcode.com/problems/first-bad-version/description/
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
#include <iostream>
using namespace std;
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n)
{
int iFirstBad = 0;
int iStart = 1;
int iEnd = n;
while (iStart <= iEnd)
{
int iMid = iStart + (iEnd - iStart) / 2;
if (isBadVersion(iMid))
{
iEnd = iMid - 1;
iFirstBad = iMid;
}
else
{
iStart = iMid + 1;
}
}
return iFirstBad;
}
};
int main()
{
return 0;
}
https://leetcode.com/problems/ugly-number/description/
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
Note that 1 is typically treated as an ugly number.
#include <iostream>
using namespace std;
class Solution {
public:
bool isUgly(int num)
{
if (num < 1)
{
return false;
}
if (num == 1)
{
return true;
}
while (1)
{
if (num % 2 == 0)
{
num = num / 2;
continue;
}
else if (num % 3 == 0)
{
num = num / 3;
continue;
}
else if (num % 5 == 0)
{
num = num / 5;
continue;
}
else
{
break;
}
}
return num == 1;
}
};
int main()
{
Solution o;
bool bRet = o.isUgly(14);
return 0;
}
https://leetcode.com/problems/add-digits/description/
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
#include <iostream>
using namespace std;
/*
1 1
2 2
3 3
...
8 8
9 9
10 1
11 2
12 3
13 4
...
17 8
18 9
19 1
20 2
21 3
22 4
...
*/
class Solution {
public:
int addDigits(int num)
{
if (num <= 9)
{
return num;
}
else
{
if (num % 9 == 0)
{
return 9;
}
else
{
return num % 9;
}
}
}
};
int main()
{
return 0;
}
https://leetcode.com/problems/binary-tree-paths/description/
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
[“1->2->5”, “1->3”]
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void Traverse(TreeNode * root, vector<int> & vecPathValue, vector<string> & result)
{
if (NULL == root)
{
return;
}
vecPathValue.push_back(root->val);
if (root->left == NULL && root->right == NULL)
{
string str;
for (int i = 0; i < vecPathValue.size(); i++)
{
if (i == 0)
{
char acTemp[128] = { 0 };
sprintf(acTemp, "%d", vecPathValue[i]);
str = str + string(acTemp);
}
else
{
char acTemp[128] = { 0 };
sprintf(acTemp, "->%d", vecPathValue[i]);
str = str + string(acTemp);
}
}
result.push_back(str);
}
else
{
Traverse(root->left, vecPathValue, result);
Traverse(root->right, vecPathValue, result);
}
vecPathValue.pop_back();
}
vector<string> binaryTreePaths(TreeNode* root)
{
vector<int> vecPathValue;
vector<string> result;
Traverse(root, vecPathValue, result);
return result;
}
};
int main()
{
return 0;
}
https://leetcode.com/problems/valid-anagram/description/
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.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
#include <iostream>
#include <string>
#include <set>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t)
{
if (s.size() != t.size())
{
return false;
}
int aiANSI[128] = { 0 };
for (int i = 0; i < s.size(); i++)
{
aiANSI[s[i]]++;
}
for (int i = 0; i < t.size(); i++)
{
if (aiANSI[t[i]] <= 0)
{
return false;
}
else
{
aiANSI[t[i]]--;
}
}
return true;
}
};
int main()
{
Solution o;
bool bRet = o.isAnagram("ab", "a");
return 0;
}