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;
}
#include <iostream>
#include <tuple>
using namespace std;
int main()
{
std::tuple<int, char> foo(10, 'x');
auto bar = std::make_tuple("text", 3.1, 14, 'y');
std::get<2>(bar) = 100;
int myint;
char mychar;
std::tie(myint, mychar) = foo;
cout << "myint = " << myint << ", mychar = " << mychar << endl;
std::tie(std::ignore, std::ignore, myint, mychar) = bar;
cout << "myint = " << myint << ", mychar = " << mychar << endl;
mychar = std::get<3>(bar);
std::get<0>(foo) = std::get<2>(bar);
std::get<1>(foo) = mychar;
std::cout << "foo contains: ";
std::cout << std::get<0>(foo) << ' ';
std::cout << std::get<1>(foo) << '\n';
return 0;
}
#include <iostream>
#include <tuple>
using namespace std;
int main()
{
auto mytuple = std::make_tuple(10, 'a');
std::tuple_element<0, decltype(mytuple)>::type first = std::get<0>(mytuple);
std::tuple_element<1, decltype(mytuple)>::type second = std::get<1>(mytuple);
cout << "mytuple contains: " << first << " and " << second << '\n';
return 0;
}
#include <iostream>
#include <tuple>
using namespace std;
int main()
{
std::tuple<int, char, double> mytuple(10, 'a', 3.14);
cout << "mytuple has ";
cout << std::tuple_size<decltype(mytuple)>::value;
cout << " elements.\n";
return 0;
}
http://www.redblobgames.com/pathfinding/a-star/introduction.html
https://leetcode.com/problems/nth-digit/description/
Find the n^th digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 2^31).
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
/*
iMinNum iMaxNum iMinDigit iMaxDigit iBase
1 2 3 ...... 9 9 - 1 + 1 = 9 1 9 1
10 11 12 ...... 99 99 - 10 + 1 = 90 10 9 + 90x2 = 189 2
100 ............ 999 999 - 100 + 1 = 900 190 9 + 90x2 + 900x3 = 2889 3
1000 ............ 9999 9999 - 1000 + 1= 9000
.....
例：int n = 12.
那么可以找到12是在第二个区间内的。
iMinNum = 10; iMaxNum = 99; iBase = 2;
iMinDigit = 10; iMaxDigit = 189;
iDigitOffset = n - iMinDigit = 12 - 10 = 2; 在这个区间内偏移2位。
iNumOffset = iDigitOffset / iBase = 2 / 2 = 1; 在这个区间内的第几个数。
iNum = iMinNum + iNumOffset = 10 + 1 = 11; 这个数就是11。
iDigitInNum = iDigitOffset % iBase = 0; 就是在11这个数的第0位。
*/
#include <iostream>
using namespace std;
class Solution {
public:
int findNthDigit(int n) {
long long iBase = 1;
long long iMinNum = 1;
long long iMaxNum = 9;
long long iMinDigit = 1;
long long iMaxDigit = 9;
while (!bInRange(n, iMinDigit, iMaxDigit))
{
iBase++;
iMinNum = iMaxNum + 1;
iMaxNum = iMinNum * 10 - 1;
iMinDigit = iMaxDigit + 1;
iMaxDigit = iMaxDigit + (iMaxNum - iMinNum + 1) * iBase;
}
long long iDigitOffset = n - iMinDigit;
long long iNumOffset = iDigitOffset / iBase;
long long iNum = iMinNum + iNumOffset;
long long iDigitInNum = iDigitOffset % iBase;
return iGetNumDigit(iNum, iDigitInNum, iBase);
}
bool bInRange(long long n, long long iMinDigit, long long iMaxDigit)
{
if (n >= iMinDigit && n <= iMaxDigit)
{
return true;
}
else
{
return false;
}
}
long long iGetNumDigit(long long iNum, long long iDigit, long long iBase)
{
long long t = iBase - 1 - iDigit;
while (t > 0)
{
iNum /= 10;
t--;
}
return iNum % 10;
}
};
int main()
{
//1000000000
Solution o;
cout << o.findNthDigit(10) << endl;
cout << o.findNthDigit(11) << endl;
cout << o.findNthDigit(12) << endl;
cout << o.findNthDigit(13) << endl;
cout << o.findNthDigit(20) << endl;
cout << o.findNthDigit(500) << endl;
return 0;
}
https://github.com/haoel/leetcode/blob/master/algorithms/cpp/nthDigit/NthDigit.cpp
https://leetcode.com/problems/rotate-function/description/
Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 10^5.
Example:
A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
if (A.empty())
{
return 0;
}
int iMaxSum = 0;
int iPreSum = 0;
int iLastIndex = A.size() - 1;
int iMaxBase = A.size() - 1;
for (int i = 0; i < A.size(); i++)
{
iMaxSum = iMaxSum + i * A[i];
}
iPreSum = iMaxSum;
for (int i = 0; i < A.size() - 1; i++)
{
int iCurSum = iPreSum;
for (int j = 0; j < A.size(); j++)
{
if (j != iLastIndex)
{
iCurSum += A[j];
}
else
{
iCurSum -= A[j] * iMaxBase;
}
}
iLastIndex--;
if (iCurSum > iMaxSum)
{
iMaxSum = iCurSum;
}
iPreSum = iCurSum;
}
return iMaxSum;
}
};
int main()
{
vector<int> A;
A.push_back(4);
A.push_back(3);
A.push_back(2);
A.push_back(6);
Solution o;
cout << o.maxRotateFunction(A) << endl;
return 0;
}
https://leetcode.com/problems/find-the-difference/description/
Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.
#include <iostream>
using namespace std;
class Solution {
public:
char findTheDifference(string s, string t) {
int aiANSI[128] = { 0 };
for (char c : s)
{
aiANSI[c]++;
}
for (char c : t)
{
aiANSI[c]--;
}
for (int i = 0; i < 128; i++)
{
if (aiANSI[i] != 0)
{
return (char)i;
}
}
return 0;
}
};
int main()
{
Solution o;
cout << o.findTheDifference("abcd", "abcde") << endl;
return 0;
}