class A{
public:
    virtual void func(){
        printf("A %d\n", _i);
    }
    virtual void func2(){
        printf("A2 %d\n", _i);
    }

    int _i = 10;
};

class B : public A{
public:
    virtual void func(){
        printf("B %d\n", _i);
    }

    int _i = 20;
};

int main() {
    B b;
    A *pa = &b;
    
    pa->func();		// B 20
    pa->func2();	// A2 10

    return 0;
}

 5 class A{
 6 public:
 7     virtual ~A() {
 8         printf("%s\n", "A destruct");
 9     }
10 };
11 
12 class B : public A{
13 public:
14     virtual ~B() {
15         printf("%s\n", "B destruct");
16     }
17 };
18 
19 int main() {
20     B a;
21 
22     return 0;
23 }

class A{
public:
    int _i = 1;
};

class B : virtual public A{
public:
    int _i = 2;
};

class C : virtual public A{
public:
    int _i = 3;
};

class D : public B, public C{
public:
    int _i = 4;
};

D a;
void *p = &a;
int *pi = (int *)p;

for (int i = 0; i < sizeof(a) / 4; ++i)
    printf("%d\n", pi[i]);

printf("val:%d\n", a._i);

A: 	1
B: 	4196632
    0
    2
    1
C: 	4196632
    0
    3
    1
D:	4196760
    0
    2
    0
    4196784
    0
    3
    4
    1
    0

D a;
A *pa = &a;
printf("%d\n", pa->_i);
B *pb = &a;
printf("%d\n", pb->_i);
C *pc = &a;
printf("%d\n", pc->_i);
D *pd = &a;
printf("%d\n", pd->_i);

D a;
C *pd = &a;
printf("%d\n", pd->A::_i);

4196760	// 2. 它减去 24 到了这里 
    	// 3. 用这里的值寻址得到了某个数 x 
0
2
0
4196784	// 1. 这是一开始 C 指针指向的内存
    	// 4. 用这个指针 + x 得到了虚基类数据的地址
0
3
4
1
0

D a;
long long *pl = (long long *)&a;
long long *pl2 = (long long *)&pl;
*pl2 = *pl;

printf("%ld\n", *pl);	// 16

class E : virtual public A{
public:
    int _i = 555;
};

class D : public B, public C, public E{
public:
    int _i = 444;
};

int main() {
    D a;
    long long *pl = (long long *)&a;
    long long *pl2 = (long long *)&pl;
    *pl2 = *pl;
    printf("%ld\n", *pl);   // 32

    pl = (long long *)&a + 2;
    pl2 = (long long *)&pl;
    *pl2 = *pl;
    printf("%ld\n", *pl);   // 16

    pl = (long long *)&a + 4;
    pl2 = (long long *)&pl;
    *pl2 = *pl;
    printf("%ld\n", *pl);   // 0

4196856	(32)// 2. 通过这个地址拿到偏移
0
222
0
4196880	(16)// 1. C对象, 当我要找虚基类对象时, 我先往上移动固定字节
    		// 这些移动的大小都是在编译时就写死了的常量(编译器自动计算)
    		// 往上移动的字节会随着数据大小而改变, 但是数据中的地址是不变的
    		// 比如我这里是4196880, 那么无论往上移动多少
    		// 上一个地址中存的值恒定为 当前值 - 24 (4196856)
    	// 3. 根据拿到的偏移 + 地址获取虚基类数据
0
333
0
4196904 (0)// E对象, 它如果想拿到虚基类数据, 执行和 C 对象一样的操作就好
0
555
444
111
0

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int deep_A = 0, deep_B = 0;
        
        ListNode *temp_head = headA;
        while (temp_head) {
            temp_head = temp_head->next;
            ++deep_A;
        }
        
        temp_head = headB;
        while (temp_head) {
            temp_head = temp_head->next;
            ++deep_B;
        }
        
        int distance = abs(deep_A - deep_B);
        if (deep_A > deep_B) {
            while (distance) {
                headA = headA->next;
                --distance;
            }
        } else {
            while (distance) {
                headB = headB->next;
                --distance;
            }
        }
        
        while (headA && headB && headA != headB) {
            headA = headA->next;
            headB = headB->next;    
        }
        
        return headA;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA;
        ListNode *q = headB;
        while (p != q) {
            p = (p ? p->next: headB);
            q = (q ? q->next: headA);
        }
        return p;
    }
};

static const int _ = [] () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
} ();

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        size_t size = nums.size();
        if ( !size ) return 0;

        int b = 0;
        int e = size;
        int ret = nums[0];
        while (b < e) {
            int tb = b;
            while (b < e && nums[b] != 0) ++b;
            if (b - tb <= 1) {
                ret = max(ret, nums[tb]);
                if (b < e)
                    ret = max(ret, nums[b]);
                b += 1;
                continue;
            }

            int sum = 1;
            int tb2 = tb;
            while (tb2 < b) sum *= nums[tb2++];

            if (sum < 0) {
                int sumneg1 = 1;
                tb2 = tb;
                while (tb2 < b) { 
                    sumneg1 *= nums[tb2];
                    if (nums[tb2] < 0) break;
                    ++tb2;
                }
                int sum1 = sumneg1 / nums[tb2] == 1 ? sumneg1 : 
                    sumneg1 / nums[tb2];

                int sumneg2 = 1;
                tb2 = b - 1;
                while (tb2 >= tb) {
                    sumneg2 *= nums[tb2];
                    if (nums[tb2] < 0) break;
                    --tb2;
                }
                int sum2 = sumneg2 / nums[tb2] == 1 ? sumneg2 : 
                    sumneg2 / nums[tb2];

                sum /= max(sumneg1, sumneg2);
                sum = max(sum, sum1);
                sum = max(sum, sum2);
            }

            ret = max(ret, sum);
            b += 1;
        }

        return ret;
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        int max_num[len] = {0};
        int min_num[len] = {0};
        int max = nums[0];
        int min = nums[0];
        max_num[0] = nums[0];
        min_num[0] = nums[0];
        for (int i = 1; i < len; ++i) {
            int tmp1 = max_num[i-1] * nums[i];
            int tmp2 = min_num[i-1] * nums[i];
            int cur_max_num = tmp1 > tmp2 ? tmp1 : tmp2;
            int cur_min_num = tmp1 < tmp2 ? tmp1 : tmp2;
            max_num[i] = cur_max_num >= nums[i] ? cur_max_num : nums[i];
            min_num[i] = cur_min_num <= nums[i] ? cur_min_num : nums[i];
            max = max > max_num[i] ? max : max_num[i];
            min = min < min_num[i] ? min : min_num[i];
        }

        return max;
    }
};

const static int _ = [] () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
} ();

class Solution {
public:
    int candy(vector<int>& ratings) {
        size_t size = ratings.size();
        if (!size) return 0;
        if (size == 1) return 1;

        vector<int> candys(size, 0);  

		// 填充所有可以直接确定的数
        if (ratings[0] <= ratings[1]) 
            candys[0] = 1;
        if (ratings[size - 1] <= ratings[size - 2]) 
            candys[size - 1] = 1;
        for (int i = 1; i + 1 < size; ++i) {
            int minn = min(ratings[i], ratings[i - 1]);
            minn = min(minn, ratings[i + 1]);

            if (ratings[i] == minn)
                candys[i] = 1;
        }

		// 正向遍历
        if (ratings[0] > ratings[1] && candys[1]) 
            candys[0] = candys[1] + 1;
        if (ratings[size - 1] > ratings[size - 2] && candys[size - 2]) 
            candys[size - 1] = candys[size - 2] + 1;
        for (int i = 1; i + 1 < size; ++i) {
            if (candys[i] == 0) {
                int minn, maxn;
                // 当他是临近的人中权重最大的人时, 他的糖果数是
         		// max(left, right) + 1
                if (ratings[i + 1] == ratings[i - 1]) {
                    if (candys[i + 1] && candys[i - 1])
                        candys[i] = max(candys[i + 1], candys[i - 1]) + 1;
                    continue;
                }
                else if (ratings[i + 1] > ratings[i - 1]) {
                    minn = i - 1;
                    maxn = i + 1;
                } 
                else {
                    minn = i + 1;
                    maxn = i - 1;
                }
				
				// 当他只比其中一个大时, 他的糖果数是 min + 1
                if (ratings[i] <= ratings[maxn] && candys[minn])
                    candys[i] = candys[minn] + 1;
                // 这里和第一处的判断是相同的, 第一处只是为了减少一些操作
                if (ratings[i] > ratings[maxn] && candys[maxn] && candys[minn])
                    candys[i] = max(candys[maxn], candys[minn]) + 1;
            }
        }

		// 反向遍历, 逻辑相同
        for (int i = size - 2; i >= 1; --i) {
            if (candys[i] == 0) {
                int minn, maxn;
                if (ratings[i + 1] == ratings[i - 1]) {
                    if (candys[i + 1] && candys[i - 1])
                        candys[i] = max(candys[i + 1], candys[i - 1]) + 1;
                    continue;
                }
                else if (ratings[i + 1] > ratings[i - 1]) {
                    minn = i - 1;
                    maxn = i + 1;
                } 
                else {
                    minn = i + 1;
                    maxn = i - 1;
                }

                if (ratings[i] <= ratings[maxn] && candys[minn])
                    candys[i] = candys[minn] + 1;
                if (ratings[i] > ratings[maxn] && candys[maxn] && candys[minn])
                    candys[i] = max(candys[maxn], candys[minn]) + 1;
            }
        }
        if (ratings[0] > ratings[1] && candys[1]) 
            candys[0] = candys[1] + 1;
        if (ratings[size - 1] > ratings[size - 2] && candys[size - 2]) 
            candys[size - 1] = candys[size - 2] + 1;

        int ret = 0;
        for (int i = 0; i < size; ++i)
            ret += candys[i];

        return ret;
    }

private:
};

class Solution {
 public:
  int candy(vector<int>& ratings) {
    vector<int> num(ratings.size(), 1);
    for (int i = 1; i < ratings.size(); ++i) {
      if (ratings[i] > ratings[i-1]) {
        num[i] = num[i-1] + 1;
      }
    }
    for (int i = ratings.size() - 2; i >= 0; --i) {
      if (ratings[i] > ratings[i+1] && num[i] <= num[i+1]) {
        num[i] = num[i+1] + 1;
      }
    }
    int sum = 0;
    for (int i = 0; i < num.size(); ++i) {
      sum += num[i];
    }
    return sum;
  }
};

static int x = []() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  return 0;
}();

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // nums.size() return value is size_t !!!!
        if (nums.size() < 3) return 0;
        if (nums.size() == 3) return nums[0] + nums[1] + nums[2];
        cut(nums);
        int length = nums.size() - 1;
        minn = nums[0] + nums[1] + nums[2];
        targetp = target;

        for (int i = 0; i <= length; ++i) {
            for (int i2 = 0; i2 <= length; ++i2) {
                if (i2 != i) {
                    for (int i3 = 0; i3 <= length; ++i3) {
                        if (i3 != i2 && i3 != i) {
                            if ( !isMin(nums[i] + nums[i2] + nums[i3]) )
                                break;
                        } // 3 if
                        else continue;
                    } // 3
                } // 2 if
                else continue;
            } // 2
        } // 1

        return minn;
    }

private:
    void cut(vector<int>& nums) {
        sort(nums.begin(), nums.end());
    }

    bool isMin(int newn) {
        minn = abs(newn - targetp) > abs(targetp - minn) ? minn : newn;

        return newn < targetp;
    }

    int minn;
    int targetp;
};

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        if (n < 3) return 0;
        int rnum = nums[0] + nums[1] + nums[2];
        sort(nums.begin(), nums.end());

        for (int i = 0; i < (n - 2); ++i) {
            int lb = i + 1, ub = n - 1;
            while (lb < ub) {
                int tmpsum = nums[i] + nums[lb] + nums[ub];
                if (tmpsum == target) return target;
                if (tmpsum > target) {
                    if ((tmpsum - target) < abs(rnum - target)) rnum = tmpsum;
                    --ub;
                } else {
                    if ((target - tmpsum) < abs(rnum - target)) rnum = tmpsum;
                    ++lb;
                }

            }
        }
        return rnum;
    }
};

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

        doit(digits, {});

        return ret;
    }

private:
    void doit(string digits, string const& str) {
        if (digits.size() == 0) {
            ret.emplace_back(str);
            return;
        }

        vector<char>& charset = dict[int(digits[0]) - 48];

        for (int i = 0; i < charset.size(); ++i) {          
            doit({digits.begin() + 1, digits.end()}, str + charset[i]);
        }
    }

    map<int, vector<char>> dict = {
        {2, {'a', 'b', 'c'}},
        {3, {'d', 'e', 'f'}},
        {4, {'g', 'h', 'i'}},
        {5, {'j', 'k', 'l'}},
        {6, {'m', 'n', 'o'}},
        {7, {'p', 'q', 'r', 's'}},
        {8, {'t', 'u', 'v'}},
        {9, {'w', 'x', 'y', 'z'}}
    };

    vector<string> ret;
};

class Solution {
public:
    int countNodes(TreeNode* root) {
        stack<pair<TreeNode*, bool>> nodes;
        
        TreeNode* cursor = root;
        int ldeep = 0, rdeep = 0;
        while (cursor) {
            cursor = cursor->left;
            ++ldeep;
        }
        cursor = root;
        while (cursor) {
            // 1 means next is a right node
            nodes.push(make_pair(cursor, 1));
            cursor = cursor->right;
            ++rdeep;
        }
        int ret = (1 << ldeep) - 1;
        // is a full binary tree
        if (ldeep == rdeep) 
            return ret;
        
        while (!nodes.empty()) {
            cursor = nodes.top().first;
            if (!cursor->right) --ret;
            if (!cursor->left) --ret;
            if (cursor->left || cursor->right)
                return ret;
            
            nodes.pop();
            --rdeep;
            // current node is right node, so next node is left node
            if (!nodes.empty() && nodes.top().second) {
                nodes.top().second = 0;
                nodes.push(make_pair(nodes.top().first->left, 1));
                ++rdeep;
                continue;
            }
            
            // find next node with next node is right node
            while (!nodes.empty() && !nodes.top().second) {
                nodes.pop();
                --rdeep;
            }
            // means some errors occur
            if (nodes.empty()) return -1;
            nodes.top().second = 0;
            cursor = nodes.top().first->left;
            while (cursor) {
                nodes.push(make_pair(cursor, 1));
                cursor = cursor->right;
                ++rdeep;
            }
            // get the bottom element
            if (ldeep == rdeep) return ret;
        }
        
        // means some errors occur
        return -2;
    }
};

inline bool is_high (TreeNode* root, int path, int high) {
    high--;
    while (high >= 0) {
        bool flag = path & (1 << high);
        if (flag && root->right) {
            root = root->right;
        } else if (!flag && root->left) {
            root = root->left;
        } else {
            return false;
        }
        high--;
    }

    return true;
}

class Solution {
public:
    int countNodes (TreeNode* root) {
        if (!root) return 0;

        int high = 0;
        TreeNode* node = root->left;
        while (node) {
            high++;
            node = node->left;
        }

        int first = 0;
        int last = 1 << high;
        while (first < last) {
            int mid = (first + last) / 2;
            if (is_high(root, mid, high)) {
                first = mid + 1;        
            } else {
                last = mid;
            }
        }

        return (1 << high) - 1 + last;
    }
};

while (first < last) {
    int mid = (first + last) / 2;
    if (is_high(root, mid, high)) {
        first = mid + 1;        
    } else {
        last = mid;
    }
}