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;
}
map: 红黑树
unordered_map: hash表
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
typedef unordered_map<string, string> stringmap;
stringmap merge(stringmap a, stringmap b)
{
stringmap temp(a);
temp.insert(b.begin(), b.end());
return temp;
}
int main()
{
stringmap first;
stringmap second({ {"apple", "red"}, {"lemon", "yellow"} });
stringmap third({ { "orange", "orange" },{ "strawberry", "red" } });
stringmap fourth(second);
stringmap fifth(merge(third, fourth));
stringmap sixth(fifth.begin(), fifth.end());
for (auto & x : sixth)
{
std::cout << " " << x.first << ":" << x.second;
}
std::cout << endl;
return 0;
}
/*
mapped_type& at ( const key_type& k );
const mapped_type& at ( const key_type& k ) const;
Average case: constant.
Worst case: linear in container size.
*/
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
std::unordered_map<string, int> mymap = {
{"Mars", 3000},
{"Saturn", 60000},
{"Jupiter", 70000}
};
mymap.at("Mars") = 3396;
mymap.at("Saturn") += 272;
mymap.at("Jupiter") = mymap.at("Saturn") + 9638;
for (auto & x : mymap)
{
std::cout << x.first << ": " << x.second << std::endl;
}
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
std::unordered_map<string, double> mymap = {
{"milk", 2.30},
{"potatoes", 1.90},
{"eggs", 0.40}
};
std::cout << "mymap.size() is " << mymap.size() << std::endl;
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, string> mymap;
mymap = {
{"Australia", "Canberra"},
{"U.S.", "Washington"},
{"France", "Paris"}
};
std::cout << "mymap contains:";
for (auto it = mymap.begin(); it != mymap.end(); ++it)
cout << " " << it->first << ":" << it->second;
cout << endl;
cout << "mymap's buckets contains:\n";
for (unsigned i = 0; i < mymap.bucket_count(); ++i)
{
cout << "bucket #" << i << " contains:";
for (auto local_it = mymap.begin(i); local_it != mymap.end(i); ++local_it)
{
cout << " " << local_it->first << ":" << local_it->second;
}
cout << endl;
}
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, string> mymap = {
{"us", "United States"},
{"uk", "United Kingdom"},
{"fr", "France"},
{"de", "Germany"}
};
for (auto & x : mymap)
{
cout << "Element [" << x.first << ":" << x.second << "]";
cout << " is in bucket #" << mymap.bucket(x.first) << endl;
}
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, string> mymap = {
{"house", "maison"},
{"apple", "pomme"},
{"tree", "arbre"},
{"book", "livre"},
{"door", "porte"},
{"grapefruit", "pamplemousse"}
};
unsigned n = mymap.bucket_count();
cout << "mymap has " << n << " buckets.\n";
for (unsigned i = 0; i < n; i++)
{
cout << "bucket #" << i << " contains: ";
for (auto it = mymap.begin(i); it != mymap.end(i); ++it)
{
cout << "[" << it->first << ":" << it->second << "] ";
}
cout << endl;
}
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, string> mymap = {
{"us", "United States"},
{"uk", "United Kingdom"},
{"fr", "France"},
{"de", "Germany"}
};
unsigned nbuckets = mymap.bucket_count();
cout << "mymap has " << nbuckets << " buckets:\n";
for (unsigned i = 0; i < nbuckets; i++)
{
cout << "bucket #" << i << " has " << mymap.bucket_size(i) << " elements.\n";
}
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, double> myrecipe;
unordered_map<string, double> mypantry = {
{"milk", 2.0},
{"flour", 1.5}
};
pair<string, double> myshopping("baking powder", 0.3);
myrecipe.insert(myshopping);
myrecipe.insert(std::make_pair<string, double>("eggs", 0.3));
myrecipe.insert(mypantry.begin(), mypantry.end());
myrecipe.insert({ {"sugar", 0.8}, {"salt", 0.1} });
cout << "myrecipe contains:" << endl;
for (auto & x : myrecipe)
{
cout << x.first << ": " << x.second << endl;
}
cout << endl;
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, double> mymap = {
{"mom", 5.4},
{"dad", 6.1},
{"bro", 5.9}
};
string input;
cout << "who? ";
getline(std::cin, input);
unordered_map<string, double>::const_iterator got = mymap.find(input);
if (got == mymap.end())
cout << "not found";
else
cout << got->first << " is " << got->second;
cout << endl;
return 0;
}