头像

我要出去乱说

百度ACG - 个人云部后端研发




离线:14小时前


最近来访(1409)
用户头像
7_48
用户头像
JackWei
用户头像
村山良树
用户头像
sapphire
用户头像
lanqiaobeizmy
用户头像
lcf_ac
用户头像
太雪菜
用户头像
lzs0511
用户头像
大楼和
用户头像
Linclon
用户头像
一万小时定律
用户头像
georgethrax
用户头像
konng0120
用户头像
AcWing2AK
用户头像
冰之韵
用户头像
succyag
用户头像
新生代奥特曼
用户头像
Hanasaki
用户头像
swifties270
用户头像
你好流星


1、思路

  • 机器人每次只能往右和下两个方向移动,而且图中会有障碍物,需要判断终点是否可达;

  • 用一个布尔数组isVisited记录节点是否访问过,但不需要还原现场,因为机器人不能走回头路(它不能往左或者往上移动),若当前节点已经走过,且最终没有到达终点,说明该节点不能通向终点,不必再走。

2、代码

class Solution {
public:
    void dfs(vector<vector<int>>& obstacleGrid, vector<vector<bool>>& isVisited,
             vector<vector<int>>& res, int rows, int cols, int i, int j, bool& isFind)
    {
        if (i < 0 || i >= rows || j < 0 || j >= cols || obstacleGrid[i][j] == 1 || 
            isVisited[i][j] == 1 || isFind == true) return;

        if (i == rows - 1 && j == cols - 1)     //已经抵达终点
        {
            isFind = true;
            res.push_back({i, j});
            return;
        }

        isVisited[i][j] = true;                 //标记已走过
        res.push_back({i, j});

        dfs(obstacleGrid, isVisited, res, rows, cols, i + 1, j, isFind);
        dfs(obstacleGrid, isVisited, res, rows, cols, i, j + 1, isFind);

        //已经找到抵达终点路径,就不必再弹出了。若没有找到,会一直弹出直到数组为空
        if (!isFind) res.pop_back();
    }

    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        int rows = obstacleGrid.size(), cols = obstacleGrid[0].size();
        bool isFind = false;
        vector<vector<bool>> isVisited(rows, vector<bool>(cols, false));
        vector<vector<int>> res;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[rows - 1][cols - 1] == 1) return res;

        dfs(obstacleGrid, isVisited, res, rows, cols, 0, 0, isFind);

        return res;                             //最后是不必判空的
    }
};



1、思路

  • 树形DP套路第一步:分析答案来自哪些可能性:

    1、以root为头节点的子树,最大距离可能是左子树上的最大距离;

    2、以root为头节点的子树,最大距离可能是右子树上的最大距离;

    3、以root为头节点的子树,最大距离可能是左子树上高度 + 右子树高度 + 1(root节点本身);

  • 第二步:根据第一步的分析列出所有需要的信息,左子树和右子树需要知道自己这棵子树上的最大距离 maxDistance 以及高度 height这两个信息;

  • 第三步:根据第二步的信息汇总,用一个新的结构体 ReturnType来存储上述两个信息;

  • 第四步:设计递归函数,整合信息。

2、代码

#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

struct ReturnType                                           //新结构体
{
    int maxDistance;
    int height;

    ReturnType(int _maxDistance, int _height) : maxDistance(_maxDistance), height(_height) {}
};

void createTree(TreeNode *root)                             //建树
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right);
    }
}

ReturnType* process(TreeNode* root)
{
    if (root == nullptr) return new ReturnType(0, 0);

    ReturnType *leftData = process(root->left);
    ReturnType *rightData = process(root->right);

    //更新最大高度以及最大距离信息
    int _height = max(leftData->height, rightData->height) + 1;
    int _maxDistance = max(leftData->height + rightData->height + 1, 
    max(leftData->maxDistance, rightData->maxDistance));

    return new ReturnType(_maxDistance, _height);
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root);

    cout << process(root)->maxDistance << endl;

    return 0;
}



1、思路

  • 对二叉树进行前序遍历,找到目标节点后就返回该节点;

  • 每次递归分三种情况讨论:

    1、若当前节点的左右子树返回值都不为空,则当前节点即是最近公共祖先;

    2、若只有左子树返回值不为空,说明其中一个节点或者两个节点都在左子树,直接返回左子树的返回值;

    3、若只有右子树返回值不为空,同上。

2、代码

#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode *root)                             //建树
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right);
    }
}

TreeNode* lowestAncestor(TreeNode *root, int p, int q)
{
    if (root == nullptr) return nullptr;

    if (root->val == p || root->val == q) return root;

    TreeNode *left = lowestAncestor(root->left, p, q);
    TreeNode *right = lowestAncestor(root->right, p, q);

    if (left != nullptr && right != nullptr) return root;   //三种情况
    else if (left != nullptr) return left;
    else return right;
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root);

    int p, q;
    cin >> p >> q;

    cout << lowestAncestor(root, p, q)->val << endl;

    return 0;
}



1、思路

  • 当前状态只能由前三个状态累加而来;

  • 先初始化好前三个状态,遍历数组的同时做累加运算即可;

  • 时间复杂度为 $O(N)$ ,空间复杂度为 $(N)$ 。

2、代码

class Solution {
public:
    int waysToStep(int n) {
        if (n <= 2) return n;

        vector<int> dp(n + 1, 0);

        dp[1] = 1, dp[2] = 2, dp[3] = 4;        //状态初始化
        for (int i = 4; i < dp.size(); ++ i)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
        }

        return dp.back();                       //返回最后一个元素即可
    }
};

3、优化空间复杂度

  • 可以只用四个变量来做DP

  • 时间复杂度为 $O(N)$ ,空间复杂度为 $(N)$ 。

class Solution {
public:
    int waysToStep(int n) {
        int p = 0, q = 0, r = 0, s = 1;

        while (n -- )
        {
            p = q;
            q = r;
            r = s;
            s = ((p + q) % 1000000007 + r) % 1000000007;
        }

        return s;
    }
};



1、思路

  • 对于二叉搜索树的判断,可以在中序遍历时保存前一个节点的值,每次比较当前节点值与前一节点值,若前一节点值较大,则该二叉树不是二叉搜索树;

  • 对于完全二叉树的判断,可以按照以下标准进行:

    1、层序遍历二叉树;

    2、若当前节点有右子节点却没有左子节点,则直接返回false

    3、若当前节点并不是左右孩子都有,那么之后的节点必须都为叶子结点,否则返回false

    4、遍历过程中若不返回false,则遍历结束后返回true

2、代码

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

//建树
void createTree(TreeNode *root)
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right);
    }
}

//判断二叉搜索树(二叉树中序遍历的迭代版)
bool isBST(TreeNode *root)
{
    if (root == nullptr) return true;

    stack<TreeNode*> stk;
    TreeNode *p = root, *pre = nullptr;

    while (p != nullptr || !stk.empty())
    {
        if (p != nullptr)
        {
            stk.push(p);
            p = p->left;
        }
        else
        {
            p = stk.top();
            stk.pop();

            if (pre != nullptr && pre->val >= p->val)
            {
                return false;
            }

            pre = p;            //更新前一节点的值
            p = p->right;
        }
    }

    return true;
}

//判断完全二叉树(二叉树的层序遍历)
bool isCBT(TreeNode *root)
{
    if (root == nullptr) return true;

    queue<TreeNode*> q;
    q.push(root);

    TreeNode *left, *right;
    bool isLeaf = false;

    while (!q.empty())
    {
        TreeNode *node = q.front();
        q.pop();

        left = node->left;
        right = node->right;

        //情况 2 和 情况 3
        if ((isLeaf && (left != nullptr || right != nullptr)) || 
            (left == nullptr && right != nullptr))
        {
            return false;
        }

        if (left != nullptr)
        {
            q.push(left);
        }

        if (right != nullptr)
        {
            q.push(right);
        }
        else
        {
            //若没有右子树,则该节点之后的所有节点均为叶子节点
            isLeaf = true;
        }
    }

    return true;
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root);

    if (isBST(root))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    if (isCBT(root))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}



1、思路

  • 二叉树的后序遍历为先左、再右、最后根的顺序,即二叉树的头节点值为数组的最后一个元素;

  • 例如数组 [2, 1, 3, 6, 5, 7, 4],比4小的部分为[2, 1, 3],比4大的部分为[6, 5, 7],再继续递归地判断这两部分子树。

2、代码

#include <iostream>
#include <vector>

using namespace std;

bool isPostOrder(vector<int>& nums, int st, int ed)
{
    if (st == ed)
    {
        return true;
    }

    //leftEnd 表示左子树最后一个节点的位置, rightBegin 表示右子树第一个节点的位置
    int leftEnd = -1, rightBegin = ed;

    for (int i = st; i < ed; ++ i)
    {
        if (nums[i] < nums[ed] )                     //比最后一个元素小,说明是左子树节点
        {
            leftEnd = i;                             //标记左子树最后一个节点位置
        }
        else
        {
            if (rightBegin == ed) rightBegin = i;    //标记右子树起始节点位置
        }
    }

    if (leftEnd == -1 || rightBegin == ed)           //当前节点只存在左子树或只存在右子树的情况
    {
        return isPostOrder(nums, st, ed - 1);
    }

    if (leftEnd != rightBegin - 1)                   //不合法的情况
    {
        return false;
    }

    //继续递归判断当前节点的左子树和右子树
    return isPostOrder(nums, st, leftEnd) && isPostOrder(nums, rightBegin, ed - 1);
}

int main()
{
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; ++ i)
    {
        cin >> nums[i];
    }

    if (isPostOrder(nums, 0, n - 1))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}



1、思路

  • 我们的目标是让这个数大一点(但又不会太大),同时保证1的个数不变。那么我们就要翻转最右边但非拖尾的0,同时将拖尾连续的1放到最右边;

  • 假设非拖尾0的位置为pc1p右方1的个数,c0p右方0的个数;

  • 求较小数的思路类似,具体实现见代码。

2、代码

class Solution {
public:
    int getNext(int num)
    {
        int c = num;
        int c0 = 0;
        int c1 = 0;

        while (((c & 1) == 0) && (c != 0))  //从右往左找到第一个非零的位(即非拖尾的 0 )
        {
            c0 ++ ;
            c >>= 1;
        }

        while ((c & 1) == 1)                //统计连续 1 的个数(拖尾连续的 1 )
        {
            c1 ++ ;
            c >>= 1;
        }

        if (c0 + c1 == 31 || c0 + c1 == 0)  //不存在的情况
        {
            return -1;
        }

        int p = c0 + c1;

        num |= (1 << p);                    //翻转最右非拖尾的 0
        num &= ~((1 << p) - 1);             //清除所有 p 的右侧位
        num |= (1 << (c1 - 1)) - 1;         //在右侧插入 (c1 - 1) 个 1
        return num;
    }

    int getPrev(int num)
    {
        int c = num;
        int c0 = 0;
        int c1 = 0;

        while (c & 1 == 1)
        {
            c1 ++ ;
            c >>= 1;
        }

        if (c == 0) return -1;

        while (((c & 1) == 0) && (c != 0))
        {
            c0 ++ ;
            c >>= 1;
        }

        int p = c0 + c1;

        //num &= ((~0) << (p + 1));         //从位置 p 开始清零,这行代码力扣会报错
        for (int i = 0; i < p + 1; ++ i)    //改用 for 循环从位置 p 开始清零
        {
            num &= (~(1 << i));
        }

        int mask = (1 << (c1 + 1)) - 1;     //包括 c1 + 1 个 1 的序列
        num |= mask << (c0 - 1);

        return num;
    }

    vector<int> findClosedNumbers(int num) {
        int nextNum = getNext(num);
        int prevNum = getPrev(num);

        return {nextNum, prevNum};
    }
};



1、思路

  • 用一个 getDeep 函数计算当前子树的深度;

  • 每次递归都要判断 root 的左右子树是否平衡,并判断以 root 为根节点的子树是否平衡。

2、代码

#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode *root, int &n)     //建树
{
    if (n == 0) return;

    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

int getDeep(TreeNode *root)                     //递归计算当前子树的深度
{
    if (root == nullptr) return 0;

    return max(getDeep(root->left), getDeep(root->right)) + 1;
}

bool isBalanced(TreeNode *root)
{
    if (root == nullptr) return true;

    //递归判断 root 的左右子树是否平衡,并判断以 root 为根节点的子树是否平衡
    return isBalanced(root->left) && isBalanced(root->right) && 
            abs(getDeep(root->left) - getDeep(root->right) <= 1);
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root, n);

    if (isBalanced(root))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}


分享 算法 Tricks

记录一些算法常用的Tricks,想起来的话会在这里补充。

一:位运算

  1. n & (-n):取得最低位的1所代表的值;

  2. n & (n - 1):把n中最低位的1抹掉;

  3. n & (n - 1) == 0 && n != 0:检查n是否为2的幂;

    解释:因为 n & n-1 会把n中最低位的1抹掉,比如 1100 & 1011 == 1000 把第二位上的1给抹掉了。又因为2的幂的二进制表示中只有一个1,如 10000100 等,将这个唯一的1抹除后数值就变为0了。




1、思路

  • 按照二叉树的中序遍历顺序,将每个节点放入队列q中;

  • q中依次弹出节点,并按照弹出的顺序重新连接所有节点即可。

2、代码

double_list_node * convert(BST * root)
{
    queue<BST*> q;
    inOrderTreeToQueue(root, q);

    root = q.front();
    q.pop();

    // head 为双链表头结点
    double_list_node *head = new double_list_node(), *pre = head;
    pre->val = root->val;
    pre->pre = nullptr;     //头结点往前为空

    while (!q.empty())
    {
        double_list_node *cur = new double_list_node();
        BST *tmp = q.front();
        q.pop();
        cur->val = tmp->val;

        pre->next = cur;    //连接前一节点和当前节点
        cur->pre = pre;

        pre = cur;          //指针后移
    }

    pre->next = nullptr;    //尾结点往后为空
    return head;
}