void tripleWeight(double w) {
 w *= 3; // 重量三倍
}

int main() {
 double weight = 1.06;
 tripleWeight(weight);
 cout << weight << endl; //weigt仍是1.06
}

void tripleWeight(double& weight_ref) {
 weight_ref *= 3; // 重量三倍
}

int main() {
 double weight = 1.06;
 tripleWeight(weight);
 cout << weight << endl; //weight会变为3.18, 但我们通常不会这样编写代码……
} 

void tripleWeight(double& weight_ref);
...
tripleWeight(1.06);//别这么做!编译器出错 1.06是一个临时值，没有实际存储位置，不能被引用修改

void eliminateNegativity(vector<int> v)
{
  for (int i = 0; i < v.size(); i++)
  {
    if (v[i] < 0)
      v[i] *= -1; //负数 * -1
    cout << v[i] << endl;
  }
}

int main()
{
  vector<int> vec = {-1, 0, -4, 5};
  eliminateNegativity(vec);
  return 0;
}

void printGrid(Grid<char>& grid) {
 for(int r = 0; r < grid.numRows(); r++) {
     for(int c = 0; c < grid.numCols(); c++) {
         cout << grid[r][c];
     }
     cout << endl;
  }
}

Grid<char> word = {{'y', 'e'}, {'e', 'h'}, {'a', 'w'}};
printGrid(word);

output:
ye
eh
aw

struct GridLocation {
    int row;    
    int col;
}                     //结构定义(可以是不同类型的成员)

GridLocation origin = {0, 0}; 
// or
GridLocation origin;
origin.row = 0;
origin.col = 0; //您可以使用点号表示法访问结构体中的成员 成员名后面不需要括号

enqueue(value)  // or add(value )入队
dequeue()  // or remove() 离队 因为是先进先出 所以是移除首次添加的值
peek()  // or front() 查看队首
isEmpty() // 队列是否为空

Queue<int> line; // {}, empty queue
line.enqueue(42); // {42}
line.enqueue(-3); // {42, -3}
line.enqueue(17); // {42, -3, 17}
cout << line.dequeue() << endl; // 取出42 (队列目前为 {-3, 17})
cout << line.peek() << endl; // 显示-3 (队列目前为 {-3, 17})
cout << line.dequeue() << endl; // 取出-3 (队列目前为 {17})

// or
Queue<int> line = {42, -3, 17};

Stack<string> wordStack; // {}, empty stack
wordStack.push("Kylie"); // {"Kylie"}
wordStack.push("Nick"); // {"Kylie", "Nick"}
wordStack.push("Trip"); // {"Kylie", "Nick", "Trip"}
cout << wordStack.pop() << endl; // “Trip”
cout << wordStack.peek() << endl; // "Nick"
cout << wordStack.pop() << endl; // "Nick" (stack is {"Kylie"})
// 直接表示
Stack<string> wordStack = {"Kylie", "Nick", "Trip"};
// 顶部 是最右边的元素Trip

//取出队列中的元素
Queue<int> queueIdiom1;
// produce: {1, 2, 3, 4, 5, 6}
for (int i = 1; i <= 6; i++) {
  queueIdiom1.enqueue(i);
}
while (!queueIdiom1.isEmpty()) {
  cout << queueIdiom1.dequeue() << " ";
}
cout << endl;
//output: 1 2 3 4 5 6

//取出栈中的元素
Stack<int> stackIdiom1;
// produce: {1, 2, 3, 4, 5, 6}
for (int i = 1; i <= 6; i++) {
  stackIdiom1.push(i);
}
while (!stackIdiom1.isEmpty()) {
  cout << stackIdiom1.pop() << " ";
}
cout << endl;
//output: 6 5 4 3 2 1

//队列
Queue<int> queueIdiom2 = {1,2,3,4,5,6};

int origQSize = queueIdiom2.size();

for (int i = 0; i < origQSize; i++) {
   int value = queueIdiom2.dequeue();
 // 只保留偶数
   if (value % 2 == 0) {
       queueIdiom2.enqueue(value);
   }
}
cout << queueIdiom2 << endl;
//output: 2, 4, 6

//栈
Stack<int> stackIdiom2 = {1,2,3,4,5,6};
Stack<int> result;

int origSSize = stackIdiom2.size();

for (int i = 0; i < origSSize; i++) {
  int value = stackIdiom2.pop();
 // stackIdiom2的偶数添加到result
  if (value % 2 == 0) {
      result.push(value);
  }
}
cout << result << endl;
//output: 6, 4, 2

add(value) //向集合中添加一个值。如果集合里已经有这个值，则不重复添加
contains(value) //检查集合中是否包含某个值。包含返回 true，否则返回 false。
remove(value) //集合中删除某个值。如果这个值不存在，什么也不做
size() //返回集合中元素的数量
isEmpty() //判断集合是否为空。为空返回 true，否则返回 false

Set<string> friends;
friends.add("nick");
friends.add("kylie");
friends.add("trip");
// 也可以这样  Set<string> friends = {“nick”, “kylie”, “trip”};
cout << boolalpha << friends.contains("voldemort") << noboolalpha
    << endl;
for(string person : friends) {
    cout << person << endl;
}

for (type currElem : set) {
 // process elements one at a time
}

m.clear() //清空 Map，删除所有键值对
m.containsKey(key) //判断 Map 是否包含指定的键。包含返回 true，否则返回 false
m[key] //or m.get(key) 获取指定 key 对应的 value，如果 key 不存在，返回 value 类型的默认值
m.isEmpty() //判断 Map 是否为空。没有任何键值对返回 true
m.keys() //返回 Map 中所有 key 的集合（Vector）
m[key] = value //or m.put(key, value) 添加一个键值对，如果 key 已存在，则更新它对应的 value
m.remove(key) //删除指定 key 的键值对，如果 key 不存在，不做任何操作
m.size() //返回 Map 中键值对的数量
m.values() //返回 Map 中所有 value 的集合（Vector）

// 将字符串键映射到字符串值
Map<string, string> phoneBook;

//插入新值
// key                value
phoneBook["Jenny"] = "867-5309"; // or
phoneBook.put("Jenny", "867-5309");

//访问值
string jennyNumber = phoneBook["Jenny"]; // or
string jennyNumber = phoneBook.get("Jenny");
cout << jennyNumber << endl;

// 将字符串键映射到 Vector<double> 值
Map<string, Vector<double>> accounts;

Map<string, int> freqMap;
while (true) {
    string text = getLine("Enter some text: ");
    cout << "Times seen: " << freqMap[text] << endl;
    freqMap[text]++; //自动插入仅在使用 [] 运算符时才会发生，而不会使用 .get() 函数
 } 

Map<string, int> freqMap;
//...
// 获取密钥以测试它是否在地图中
if (freqMap[key] == 0) { // 这个判断永远是true
cout << key << " is in the map" << endl;
}

Map<string, int> freqMap;
...
// 使用 containsKey 函数，不自动插入
if (freqMap.containsKey(key)) { // 正确的做法
    cout << key << " is in the map" << endl;
}

string countingSort(string s) {

    map<char, int> freqMap;
    
    for (char ch: s) {
        freqMap[ch]++;
    }
    
    string sortedString;
    for (char ch = 'a'; ch <= 'z'; ch++) {
        for (int i = 0; i < freqMap[ch]; i++) { //如果ch不存在与s中,freqMap[ch] = 0
                sortedString.push_back(ch);
            }
        }
    return sortedString;
}

              COLD
            /  |   \
        BOLD  CORD  SOLD
        /       |      \
   ❌  BALD     CARD    SORD  ❌
                 |
               WARD 
                 |
               WARM

 vector<string> maze = {
        "S.....", // S为起点
        ".###..", // .表示路 #表示障碍
        "...#..", 
        ".###..",
        "....E." // E为目标点 计算最短要走几步
    };

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct node {
    int x;
    int y;
    int step;
    bool operator==(const node& other) {
        return (other.x == x && y == other.y);
    }
};

class bfs1 {
public:
    int bfs(vector<string> maze) {
        //初始化
        int n = maze.size();
        int m = maze[0].size();
        node s = {0, 0, 0};
        node e = {4, 4, 0};
        queue<node> q;
        vector<vector<int>> visited(n, vector<int>(m, 0)); //搜索状态  未访问：0 已访问:1
        visited[s.x][s.y] = true;
        q.push(s); //添加起始位置坐标

        while (!q.empty()) {
            node cur = q.front(); //记录队列中第一个元素
            q.pop();              //删除

            if (cur == e)
                return cur.step;

            //方向变化量
            int dx[4] = {-1, 1, 0, 0};
            int dy[4] = {0, 0, -1, 1};

            for (int i = 0; i < 4; i++) {
                //新坐标
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >=m) //越界访问
                    continue;
                if (maze[nx][ny] == '#') //遇到障碍
                    continue;
                if (visited[nx][ny]) //已访问过
                    continue;

                visited[nx][ny] = true; //访问记录
                q.push({nx, ny, cur.step + 1}); //添加新坐标并让step+1
            }
        }
        return -1; //如果队列为空
    }
};

int main()
{
    vector<string> maze = {
        "S.....",
        ".###..",
        "...#..",
        ".###..",
        "....E."
    };

    bfs1 test;
    cout << test.bfs(maze);
    return 0;
}

feedingTimes (map<string, vector<string>>)
|
+-- ["Cat"]
|      |
|      +-- vector<string>
|             |
|             +-- [0] --> "07:00"
|             |
|             +-- [1] --> "12:00"
|
+-- ["Dog"]
       |
       +-- vector<string>
              |
              +-- [0] --> "08:00"
              |
              +-- [1] --> "11:00"

feedingTimes["Cat"] = {"7:00", "9.00"};
cout << feedingTimes["Cat"][0]; //输出一个string "7:00"

feedingTimes (map<string, vector<string>>)
|
+-- ["Cat"]
|      |
|      +-- vector<string>
|             |
|             +-- [0] --> "07:00"
|             |
|             +-- [1] --> "12:00"

feedingTimes (map<string, vector<string>>)
|
+-- ["Cat"]
|      |
|      +-- vector<string>
|             |
|             +-- [0] --> "07:00"
|             |
|             +-- [1] --> "12:00"
|             |
|             +-- [2] --> "14:00"

feedingTimes (map<string, vector<string>>)
|
+-- ["Cat"]
|      |
|      +-- vector<string>
|             |
|             +-- [0] --> "07:00"
|             |
|             +-- [1] --> "12:00"
 

times3 (vector<string>)
  |
  +-- [0] --> "07:00"
  |
  +-- [1] --> "12:00"
  |
  +-- [2] --> "14:00"

for (int i = 1; i < n; i++)
{
	x++;
}

for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= n; j++)
	{
		x++
	}
}

for (int i = 1; i < n; i++)
{
	x++;
}

for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= n; j++)
	{
		x++
	}
}

int sum = 0;
for (int i = 1; i <= n; i++)
{
	sum += i;
}

vector<int> v;
for (int i = 1; i <= n; i++)
{
	v.push_back(i);
}

vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		matrix[i][j] = 0;
	}
}

假设有
A
B
C
D
E
---------------------
我问A
A: 后面有人 → 问 B
B: 后面有人 → 问 C
C: 后面有人 → 问 D
D: 后面有人 → 问 E

E: 后面没人 → 返回 0

D 收到 0 → 返回 0 + 1 = 1
C 收到 1 → 返回 1 + 1 = 2
B 收到 2 → 返回 2 + 1 = 3
A 收到 3 → 返回 3 + 1 = 4
---------------------
A 后面有 4 个人 
总人数 = 4 + A自己 = 5

int count(Person* p)
{
    if(p->behind == nullptr)
        return 0;

    return count(p->behind) + 1;
}

int sum(int n)
{
    if(n == 1)
    {
        return 1;
    }
    else
    {
    	return n + sum(n - 1); //假设(相信)sum(n-1)正确
    }
}

5! = 5 x 4!
4! = 4 x 3!
3! = 3 x 2!
2! = 2 x 1!
1! = 1 x 0!
0! = 1

int factorial(int n)
{
  if (n == 0)
  {
    return 1;
  }
  else
  {
    return n * factorial(n - 1);
  }
}

int main()
{
  int n = factorial(5);
  cout << "5! = " << n << endl;
  return 0;
}

      dog → god
 stressed → desserts
recursion → noisrucer
    level → level
        a → a

string fan(string str)
{
  if (str.empty()) //递归终止条件
    return "";

  string temp(1, str.back()); //取出最后一个字符
  str.pop_back();             //删除最后一个字符

  return temp + fan(str);     //拼接并返回
}

                    *
                    |
              *-----+-----*
              |           |
              *           *
          *---+---*   *---+---*
          |       |   |       |
          *       *   *       *
        *-+-*   *-+-* *-+-* *-+-*
        | | |   | | | | | | | | |
        * * *   * * * * * * * * *

整体
 |
 +-- 部件（它自己也是整体）
        |
        +-- 更小的自己

void hanoi(int n, char from, char temp, char to)
{
  if (n == 1)
  {
    cout << from << " -> " << to << endl;
    return;
  }

  // 把 n-1 个盘子移动到辅助柱
  hanoi(n - 1, from, to, temp);

  // 移动最大的盘子
  cout << from << " -> " << to << endl;

  // 把 n-1 个盘子移动到目标柱
  hanoi(n - 1, temp, from, to);
}

int main() {
  hanoi(3, 'A', 'B', 'C');

  return 0;
}

// 内部辅助函数(实际负责二分查找)
int binarySearchHelper(const vector<int>& v, int targetVal, int left, int right) {
    if (left > right) return -1; //Base cases

    int mid = left + (right - left) / 2;

    if (v[mid] == targetVal) return mid; //Base cases
    if (v[mid] > targetVal)  return binarySearchHelper(v, targetVal, left, mid - 1);
    return binarySearchHelper(v, targetVal, mid + 1, right); //Recursive cases
}

// 外部主函数(自动获取 vector 的首尾索引)
int binarySearch(vector<int>& v, int targetVal) {
    if (v.empty()) return -1; //Base cases
    return binarySearchHelper(v, targetVal, 0, v.size() - 1); //Recursive cases
}

开始
 |
 +-- 左边
 |    |
 |    +-- 死路 ❌
 |
 +-- 右边
      |
      +-- 出口 ✅

choose:
    选择走左边

explore:
    继续探索左边的路

unchoose:
    发现死路，回来

choose:
    改走右边

HHT
THT
TTT
HTH
...

        ""
       /  \
      H    T
     / \  / \
   HH HT TH TT

              ""
            /    \
           H      T
         /  \    /  \
        HH  HT  TH  TT
      
HHH HHT HTH HTT THH THT TTH TTT

choose:
    选择 H 或 T

explore:
    递归生成剩余位置

unchoose:
    删除刚才选择，尝试另一种可能

void generate(string soFar, int length)
{
  if (soFar.length() == length)
  {
    cout << soFar << endl;
    return;
  }

  generate(soFar + "H", length);
  generate(soFar + "T", length);
}

int main() {
  string str = "";
  generate(str, 3);

  return 0;
}

/*
output: 
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT

*/

void listPermutationsHelper(string remaining, string soFar)
{
  if (remaining.empty())
    cout << soFar <<endl;
  else
  {
    for (int i = 0; i < remaining.length(); i++)
    {
      char nextLetter = remaining[i];
      string rest = remaining.substr(0, i) + remaining.substr(i + 1);
      listPermutationsHelper(rest, soFar + nextLetter);
    }

  }
}

void listPermutations(string s)
{
  listPermutationsHelper(s, "");
}

void printsubset(vector<string> team)
{
  for (int i =0 ; i < team.size(); i++)
  {
    cout << team[i] << endl;
  }
  cout << endl;
}

void generateTeams(vector<string>& people, vector<string>& team, int index)
{
  if (index == people.size())
  {
    printsubset(team);
    return;
  }

    // 选择当前人
  team.push_back(people[index]);
  generateTeams(people, team, index + 1);
    
    // 不选择当前人
  team.pop_back();
  generateTeams(people, team, index + 1);
}

void generateTeamsHelper(vector<string> people)
{
  vector<string> team;
  generateTeams(people, team, 0);
}

int main()
{

  vector<string> people = {"Nick", "Kylie", "Trip"};
  generateTeamsHelper(people);
  return 0;
}

void generateTeams(vector<int>& people, vector<int>& team, int index, int currentSum)
{
  if (index == people.size())
  {
    if (currentSum == 0)
    {
      printsubst(team);
    }

    return;
  }

  team.push_back(people[index]); //选择
  generateTeams(people, team, index + 1, currentSum + people[index]);
  team.pop_back(); //回退
  generateTeams(people, team, index + 1, currentSum); //不选择
}

vector<string> maze = {
    "#######",
    "#S#  E#",
    "# # # #",
    "#   # #",
    "#######"

bool solveMaze(vector<string>& maze, int row, int col, vector<pair<int, int>>& path, vector<vector<bool>>& visited)
{
  if (maze[row][col] == 'E') //基本情况
  {
    path.push_back({row,col}); //记录正确路径
    return true;
  }

  visited[row][col] = true; //标记访问过的地方
  path.push_back({row, col}); //添加路径

  int dr[4] = {-1, 1, 0, 0};// 四个方向
  int dc[4] = { 0, 0,-1, 1};

  for (int i = 0; i < 4; i++) //循环四个方向
  {
    int nr = row + dr[i]; //下一步的位置
    int nc = col + dc[i];

    if (nr >= 0 && nr < maze.size() && nc >= 0 && nc < maze[0].size() && maze[nr][nc] != '#' && !visited[nr][nc]) //下一步位置是否可走
    {
      //新一轮 如果true则找到终点 如果false则继续for循环 直到所有路径失败则返回上一个栈帧个false 让它尝试其他格子的四个方向 
      if (solveMaze(maze, nr, nc, path, visited))
      {
        return true;
      }
    // else
    //   return false 错误 这样是给第一个solveMaz false
    }
  }
  path.pop_back();
  return false; //这个false是给 上一个栈帧 也就是上面的if()里的solveMaze 不是第一个solveMaze
}

int main()
{
  vector<string> maze = {
    "#######",
    "#S#  E#",
    "# # # #",
    "#   # #",
    "#######"
};
  vector<pair<int, int>> path;
  vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size(), false));

  if(solveMaze(maze,1,1,path,visited))
  {
    for(auto p:path)
    {
      cout << "("
           << p.first
           << ","
           << p.second
           << ")"
           << endl;
    }
  }
  else
  {
    cout << "No path";
  }
  return 0;
}

{A,B,C,D,E,} {F,G}
or
{ }{C,D}

                    开始
                     |
                    A?
                  /    \
              不选A     选A
               /          \
              B?          B?
            /   \        /   \
         不选B  选B  不选B  选B
           |      |      |      |
          C?     C?     C?     C?

set<set<char>> combinationsRec(set<char>& remaining, int k, set<char>& chosen)
{
  if (k == 0) //基本情况
  {
    return {chosen};
  }

  if (remaining.size() < k)
  {
    return {};
  }

  set<set<char>> result;
  char first = *remaining.begin();
  //选择
  remaining.erase(first);

  //探索
  chosen.insert(first);
  auto include = combinationsRec(remaining, k - 1, chosen);
  result.insert(include.begin(), include.end());

  chosen.erase(first);
  auto exclude = combinationsRec(remaining, k, chosen);
  result.insert(exclude.begin(), exclude.end());

  //撤销
  remaining.insert(first);

  return result;
}

void combinationsRecHelper(set<char>& remaining)
{
  set<char> chosen;
  auto result = combinationsRec(remaining, 3, chosen);
  for (set<char> i : result)
  {
    for (char j : i)
    {
      cout << j << " ";
    }
    cout << endl;
  }
}

int main()
{
  set<char>remaining = {'a', 'b', 'c' ,'d', 'e', 'f'};
  combinationsRecHelper(remaining);
  return 0;
}

targetWeight = 10; //背包容量

struct BackpackItem
{
  string name;
  int value; //生存价值
  int weight; //重量
};

 vector<BackpackItem> items = {
    {"Water", 10, 5},
    {"Knife", 6, 3},
    {"Food", 8, 4},
    {"Compass", 4, 2},
    {"Tent", 12, 7}
  };

struct BackpackItem
{
  string name;
  int value; // 生存价值
  int weight; // 重量
};

int fillBackpackHelper(vector<BackpackItem> &items, int capacityRemaining,
                       int curValue, int index)
{
  if (index == items.size() || capacityRemaining == 0) // 基本情况
  {
    return curValue;
  }

  // 不选择 without得到的“不选择当前物品后,下面整棵子树能得到的最大价值”
  int without =
      fillBackpackHelper(items, capacityRemaining, curValue, index + 1);

  // 选择 with得到的是“选择当前物品后,下面整棵子树能得到的最大价值”
  int with = curValue;
  if (items[index].weight <= capacityRemaining)
  {
    with = fillBackpackHelper(items, capacityRemaining - items[index].weight,
                              curValue + items[index].value, index + 1);
  }
  else
  {
    with = 0;
  }
  return max(without, with);
}

int fillBackpack(vector<BackpackItem> &items, int targetWeight)
{
  return fillBackpackHelper(items, targetWeight, 0, 0);
}

int main()
{

  vector<BackpackItem> items = {{"Water", 10, 5},
                                {"Knife", 6, 3},
                                {"Food", 8, 4},
                                {"Compass", 4, 2},
                                {"Tent", 12, 7}};
  cout << fillBackpack(items, 10);
  return 0;
}

int dfs(vector<BackpackItem>& items, int cap, int index, vector<vector<int>> memo)
{
  if (index == items.size() || cap == 0) //基本情况
    return 0;
  if (memo[index][cap] != -1) //备忘录 如果再次出现相同情况直接返回之前算过的
    return memo[index][cap];

  int without = dfs(items, cap, index + 1, memo); //选择

  int with = 0;
  if (items[index].weight <= cap) //不选择
  {
    with = items[index].value + dfs(items, cap - items[index].weight, index + 1, memo);
  }

  memo[index][cap] = max(with, without);
  return memo[index][cap];

}

int fun(vector<BackpackItem> items, int tw)
{
  vector<vector<int>> memo(items.size(), vector<int>(tw + 1, -1)); //都初始化为 -1
  return dfs(items, tw, 0, memo);
}

struct BackpackItem {
   int survivalValue;
   int weight;
};
struct Juror {
   string name;
   int bias;
};

//RangomBag.h
#pragma once //防止头文件重复包含
#include <vector>

class RandomBag { //定义类名
public: //公共部分
  void add(int value); //方法(成员函数)
  int removeRandom(); 
  int size(); const //使用const关键字的意思是“我保证这个函数不会改变对象的状态"
  bool isEmpty(); const
  
private: //私有部分
  vector<int> elems; //成员变量
};

#include "RandomBag.h" 
using namespace std;

void RandomBag::add(int value) { //::运算符称为作用域解析运算符,用于指定查找对象的位置
	elems.push_back(value);
}

int RandomBag::removeRandom() {
if (elems.isEmpty()) {
	cout << "Aaaaahhh!";
	}
	
	int index = randomInteger(0, size() - 1); //这段代码调用了类内的`size()`函数,类的实现可以使用公共接口
	int result = elems[index];
	elems.pop_back(index);
	return result;
}
	
int RandomBag::size() const { //我们还要记得把const也添加到实现中
	return elems.size();
}
bool RandomBag::isEmpty() const {
	return size() == 0; 
}