LeetCode Note.

Common Container

1. string

• substr(i,str.length()-i)
• find
• rfind
• c_str()
• erase

2. vector

• 用emplace_front, emplace, emplace_back 代替 push_front, insert, push_back
• emplace 相關函式可以減少記憶體拷貝和移動。當插入 rvalue，它節約了一次 move 構造，當插入 lvalue，它節約了一次 copy 構造。
• pop_back()

3. queue and deque

Hint: Deque is short for “Double ended queue”.

• Queue: you can insert only in one end and remove from the other.
• Deque: you can insert and remove from both ends.
• Methods:
  • emplace_back(val)
  • erase
  • empty()
  • push_front(val)
  • pop_back()

4. stack

• s.top()
• s.pop()
• s.push()

5. map and unordered_map

std::unordered_map<char,int> umap;
string J = "12345678abcdef";
for (unsigned i=0; i<J.length(); ++i)
    umap.insert( pair<char, int>( J.at(i), i));
//...
if(umap.find('a') != umap.end())
//...

unordered_map <char, char> table;

string pattern,word;
for(i = 0; i< pattern.length(); i++)
{
    auto ret = table.insert(std::pair <char,char> (pattern[i],word[i]));
    if(ret.second == false)
    {
        //already exist
    }
}

6. set and unordered_set

常用於紀錄是否有重複之類的

• .insert

unordered_set <char> mark;
auto ret = mark.insert('a');
if(ret.second == false)
{
     //already exist
}

---

Functions or Methods

1.找容器極值

int max = *std::max_element(nums.begin(),nums.end())
int min = *std::min_element(nums.begin(),nums.end())
int sum = std::accumulate(nums.begin(), nums.end(), 0)

2.型態極值

有些題目會用到極值來判斷

#include <limits>
#include <iostream>

int main()
{
    std::cout << "bool\t"
              << std::numeric_limits<bool>::lowest() << "\t\t"
              << std::numeric_limits<bool>::min() << "\t\t"
              << std::numeric_limits<bool>::max() << '\n'
              << "uchar\t"
              << +std::numeric_limits<unsigned char>::lowest() << "\t\t"
              << +std::numeric_limits<unsigned char>::min() << "\t\t"
              << +std::numeric_limits<unsigned char>::max() << '\n'
              << "int\t"
              << std::numeric_limits<int>::lowest() << '\t'
              << std::numeric_limits<int>::min() << '\t'
              << std::numeric_limits<int>::max() << '\n'
              << "float\t"
              << std::numeric_limits<float>::lowest() << '\t'
              << std::numeric_limits<float>::min() << '\t'
              << std::numeric_limits<float>::max() << '\n'
              << "double\t"
              << std::numeric_limits<double>::lowest() << '\t'
              << std::numeric_limits<double>::min() << '\t'
              << std::numeric_limits<double>::max() << '\n';
}

Possible output:

bool 0 0 1
uchar 0 0 255
int -2147483648 -2147483648 2147483647
float -3.40282e+38 1.17549e-38 3.40282e+38
double -1.79769e+308 2.22507e-308 1.79769e+308

3. 排序 sort

• std::sort(vector.begin(), vector.end(), std::less<int>()) : 由大排到小
• std::sort(vector.begin(), vector.end(), std::greater<int>()) : 由小排到大

4. 轉換大小寫

// c++
string str;
std::transform(str.begin(), str.end(), str.begin(), ::tolower);
std::transform(str.begin(), str.end(), str.begin(), ::toupper);
for_each(str.begin(), str.end(), [](char &x){x = tolower(x);});
for_each(str.begin(), str.end(), [](char &x){x = toupper(x);});

// c
int offset = 'A' - 'a';
for(int i =0; i < str.length() ; i++)
{
    if(str[i] >='A' && str[i] <= 'Z')
    {
        str[i] -= offset;
    }
}

5. for_each

for_each(A.begin(),A.end(), [](int &a){ a *= a;});
for_each(str.begin(), str.end(), [](char &x){x = tolower(x);});
for_each(str.begin(), str.end(), [](char &x){x = toupper(x);});
for_each(nums.begin(), nums.end(), [&sum, &nums](int& n) { sum += n; });

6. Lambda

Capturing Local Variables by Reference inside Lambda

// Local Variables
std::string msg = "Hello";
int counter = 10;
// Defining Lambda function and
// Capturing Local variables by Reference
auto func = [&msg, &counter] () {
                       //...
                       };

Capture All Local Variables from outer scope by Value

// Capturing all Local variables by Value
auto func = [=] () {
                   //...
                   };

Capture all local variables from outer scope by Reference

// Capturing all Local variables by Reference
auto func = [&] () {
                   //...
                   };

7. count_if

vector <int> count;
...
count_if(begin(count), end(count), [&maxi](const auto &p) {return p == maxi;}

What’s the most efficient way to erase duplicates and sort a vector

//ust using vector, sort + unique
sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

//Convert to set (manually)
set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

//Convert to set (using a constructor)
set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
...

## 河內塔

```c
#include <iostream>
#include <cstdio>
using namespace std;
int cnt; //全局變量，每次調用會+1

void move(int id, char from, char to) // 打印移動方式：編號，從哪個盤子移動到哪個盤子
{
    printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if(n == 0)//注意遞歸的出口，不然就是死遞歸了
        return;
    hanoi(n - 1, x, z, y); //將n-1個在x柱子上的盤子通過z這個柱子移動到y這個柱子上。
    move(n, x, z);
    hanoi(n - 1, y, x, z); //將n-1個在y柱子上的盤子通過x這個柱子移動到z這個柱子上。
}

int main()
{
    int n;
    cnt = 0;
    scanf ("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

the positive number separated into vector

int n = 12345678;
deque <int> dq; 
while (n > 0)
{
    dq.push_front(n%10);
    n /= 10;
}
//check range
if( ans > INT_MAX/10 || ans == INT_MAX/10 && n > INT_MAX %10)

名詞

the smallest in lexicographical order

最小字典序