day3 题目：206. 反转链表、199. 二叉树的右视图、bytedance-016. 16. 最短移动距离

学习计划链接：冲刺春招 - 精选笔面试 66 题大通关

今日知识点：链表、二叉树，难度仍为简单、中等、困难（字节：重新定义简单）。

# 206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

# 思路

day1 做的里边就有这题的思路，也不用多说了

# 完整代码

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var reverseList = function(head) {

    let prev = null;

    let nowv = head;

    while(nowv) {

        let temp = nowv.next;

        nowv.next = prev;

        prev = nowv;

        nowv = temp;

    }

    return prev;

}

# 199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:
输入: [1,null,3]
输出: [1,3]

示例 3:
输入: []
输出: []

# 思路

这才是简单题吧啊喂，bfs 就完事了，先右后左，高度若是小于 maxh 则不放入答案数组

# 完整代码

/**

 * @param {TreeNode} root

 * @return {number[]}

 */

var rightSideView = function(root) {

    if(!root) return [];

    let maxh = 0;

    let ans = [];

    function bfs(root, h) {

        if(!root) return;

        if(h > maxh) {

            maxh = h;

            ans.push(root.val);

        }

        bfs(root.right, h+1);

        bfs(root.left, h+1);

    }

    bfs(root, 1);

    return ans;

};

# bytedance-016. 16. 最短移动距离

给定一棵 n 个节点树。节点 1 为树的根节点，对于所有其他节点 i，它们的父节点编号为 floor (i/2) (i 除以 2 的整数部分)。在每个节点 i 上有 a [i] 个房间。此外树上所有边均是边长为 1 的无向边。
树上一共有 m 只松鼠，第 j 只松鼠的初始位置为 b [j]，它们需要通过树边各自找到一个独立的房间。请为所有松鼠规划一个移动方案，使得所有松鼠的总移动距离最短。

输入：

• 输入共有三行。
• 第一行包含两个正整数 n 和 m，表示树的节点数和松鼠的个数。
• 第二行包含 n 个自然数，其中第 i 个数表示节点 i 的房间数 a [i]。
• 第三行包含 m 个正整数，其中第 j 个数表示松鼠 j 的初始位置 b [j]。
  输出：
• 输出一个数，表示 m 只松鼠各自找到独立房间的最短总移动距离。
  示例：

输入：
5 4
0 0 4 1 1
5 4 2 2
输出：4
解释：前两只松鼠不需要移动，后两只松鼠需要经节点 1 移动到节点 3
提示：

对于 30% 的数据，满足 n,m <=100。
对于 50% 的数据，满足 n,m <=1000。
对于所有数据，满足 n,m<=100000，0<=a [i]<=m, 1<=b [j]<=n。

# 思路

字节，重新定义简单题！还是看评论才有的思路 QAQ
注意下标从 1 开始...
读入房间数的时候，记录总房间数 sum，用 cnt 记录未被使用房间数，读入松鼠时将其所处节点的 a [b] 减一，后续从最低层开始遍历，遇到松鼠将其往上走，遇到房间且还有需求时将房间往上走（但是只能解决自上而下的最短路径，等官方题解了。）
ps: 开不开快读影响很大！
pps: 测试用例好像很弱，所以估计还有 bug

# 完整代码

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 100005;

int n, m, sum, cnt;

int a[maxn], b;

int ans;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> n >> m;

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

        cin >> a[i];

        sum += a[i];   // 总房间数

    }

    for(int i = 1; i <= m; ++i) {

        cin >> b;

        --a[b];  // 占用该房间，可能使其为

    }

    cnt = sum-m;    // 剩余未被使用房间数

    for(int i = n; i > 1; --i) {

        if(!a[i]) continue;

        if(a[i] > 0 && cnt > 0) {  // 该房间还有用

            int nowh = a[i];

            if(cnt > nowh) cnt -= nowh;

            else {

                int cost = nowh-cnt;

                cnt -= cost;

                a[i/2] += cost;

                ans += cost;

            }

        } else {    // 松鼠 往上走

            int cost = abs(a[i]);

            ans += cost;

            a[i/2] += a[i];

            a[i] = 0;

        }

    }

    cout << ans << endl;

    return 0;

}