#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;
}
https://leetcode.com/problems/first-unique-character-in-a-string/description/
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
int firstUniqChar(string s) {
int aiANSI[128] = { 0 };
for (char c : s)
{
aiANSI[c]++;
}
for (int i = 0; i < s.size(); i++)
{
if (aiANSI[s[i]] == 1)
{
return i;
}
}
return -1;
}
};
int main()
{
Solution o;
cout << o.firstUniqChar("loveleetcode") << endl;
return 0;
}