牛客

First Post:

2022-09-26

Last Update:

2023-03-15

Word Count:

1.8k

Read Time:

7 min

小红划数字

小红拿到了一个正整数。
对于任意大于的数而言，她每次操作可以划掉这个数的一个数字，生成一个新的数。
例如，对于正整数而言，小红经过一次操作可以生成、、、、这五种数字。
小红想知道，自己最少操作多少次，可以把变成一个偶数？

数据范围：
进阶：空间复杂度，时间复杂度

输入描述:
一个正整数

输出描述:
小红操作的最少次数。如果小红无论如何也不能生成偶数，则输出-1。
示例1
输入

输出

说明
显然102本身就是偶数，小红不需要进行操作。
示例2
输入

输出

说明
把最后一个1划掉，形成1232，是偶数。可以证明这样操作是最少的。
示例3
输入

输出

-1

说明

无法进行删除得到偶数。

#include <iostream>
using namespace std;
int solve(int n) {
    if(n % 2 == 0) return 0;
    if(n < 9) return -1;
    int i = 0, l = 0;
    while(n > 0) {
        l++;
        n -= n % 10;
        n /= 10;
        if(n % 2 != 0)
            i ++;
        else break;
    }
    //cout << "i: " << i << endl;
    //cout << "l: " << l << endl;
    if((l - 1) == i && n == 0) {
        return -1;
    }
    return i + 1;
}
int main(void) {
    int n = 0;
    cin >> n;
    cout << solve(n);
}

反转链表

链接：https://www.nowcoder.com/profile/842917744/codeBookDetail?submissionId=400949732

描述：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： $0\leq n\leq1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

代码：

提交时间：2022-09-25 语言：C++ 运行时间： 4 ms 占用内存：564K 状态：答案正确

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == nullptr) {
            return nullptr;
        }
         
        ListNode* pNode = pHead; 
        ListNode* pNodeNext = pHead->next; // 记录当前node 的下一个
        ListNode* pNodeLast = pHead; // 记录上一个node，也可以为空，但后面需要做一下判断是否为第一个节点，是的话，在做反转的时候，需要将第一个节点设置为空。
        ListNode* pNodeTmp = nullptr;
 
        while (pNode) {
            if(pNodeNext) {
                pNodeTmp = pNodeNext->next;
                pNodeNext->next = pNode;
            }
            pNodeLast = pNode;
 
            pNode = pNodeNext; // 往下移动
            pNodeNext = pNodeTmp;
            if(pNodeLast == pHead) { //判断是否为第一个节点
                pNodeLast->next = nullptr;
            }
        }
        return pNodeLast;
 
 
    }
};

二叉树的三种遍历

链接：https://www.nowcoder.com/profile/842917744/codeBookDetail?submissionId=400949732

前序遍历

知识

前序遍历是，先遍历根节点，再遍历左子树，最后遍历右子树。

描述

给你二叉树的根节点 root ，返回它节点值的前序遍历。

数据范围：二叉树的节点数量满足 $1 \le n \le 100 \$ ，二叉树节点的值满足 $1 \le val \le 100 \$ ，树的各节点的值各不相同

示例 1：

思路

优先不断从做左子树遍历到底，杀入树多左边最底部，再通过回溯方式，从底部慢慢向上的右子树遍历。我们只需在遍历左子树节点的时候，push当前值就为前序遍历的结果了。

代码

提交时间：2022-09-25 语言：C++ 运行时间： 4 ms 占用内存：468K 状态：答案正确

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        TreeNode* now = root;
        TreeNode* subLeft = nullptr;
        TreeNode* subRight = nullptr;
        std::stack<TreeNode*> treeStack;
        std::vector<int> ret;
        //treeStack.push(root);
        // 遍历左节点
 
        while (now || treeStack.size()) {
            while(now) {
                treeStack.push(now);
                ret.push_back(now->val);
                now = now->left;
            }
             
            if(treeStack.size()) {
                now = treeStack.top();
                treeStack.pop();
                now = now->right;
            }
             
        }
 
        return ret;
 
 
    }
};

中序遍历

知识

前序遍历是，先遍历左子树，再遍历根节点，最后遍历右子树。

描述

给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足 $0 \le n \le 1000$ ，树上每个节点的值满足 $-1000 \le val \le 1000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

思路

与前序遍历方式相同，只是再回溯的过程进行保存根节点的值就为中序遍历的结果。

代码

提交时间：2022-09-26 语言：C++ 运行时间： 5 ms 占用内存：440K 状态：答案正确

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        TreeNode *now = root;
        std::stack<TreeNode *>treeStack;
        std::vector<int>ret; 
        while(now || treeStack.size()) {
            while(now) {
                treeStack.push(now);
                
                now = now->left;
            }

            if(treeStack.size()) {
                now = treeStack.top();
                treeStack.pop();

                ret.push_back(now->val);
                now = now->right;
            }
        }
        return ret;
    }
};

后序遍历

知识

后序遍历是，先遍历左子树，再遍历右子树，最后再遍历根节点。

描述

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照左节点->右节点->根节点的顺序的遍历。

数据范围：二叉树的节点数量满足 $1 \le n \le 100 \$ ，二叉树节点的值满足 $1 \le val \le 100 \$ ，树的各节点的值各不相同

样例图

思路

这个相对比较复杂一点，需要在回溯上进行一步操作，之前的回溯只是简单的移动节点到右子节点上，那么我们的遍历有点类似于横向的遍历方式，只不过横向的深度有限从左边开始遍历的。

代码

提交时间：2022-09-26 语言：C++ 运行时间： 4 ms 占用内存：396K 状态：答案正确

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        stack<TreeNode *> nodeStack;
        vector<int> ret;
        TreeNode *now = root;
        TreeNode *p = nullptr;
        int flag = 1;
        bool isExit = false;
        while((now || nodeStack.size()) && !isExit) {
            while(now) { //让当前node杀入左子树底部
                nodeStack.push(now);
                now = now->left;
            }

            flag = 1; // 用一个flag代表当前节点是否可以访问，每次回溯的时候都至少可以回溯一次。
            p = nullptr; // 记录先前的右子节点，每次回溯的时候默认为空。
            
            while(nodeStack.size() && flag) {
                now = nodeStack.top();
                if(now->right == p) { //判断一下当前右子节点是否为先前保存的右子节点
                    ret.push_back(now->val);
                    nodeStack.pop();
                    if(now == root) { // 检测到时根的时候，退出
                        isExit = true;
                        break;
                    }
                    p = now;
                }else {
                    // 向右横向移动，且不弹栈
                    now = now->right;
                    flag = 0; // 直接跳出有先去遍历左子树
                }

            }
        }

        return ret;
    }
};

打赏点小钱

支付宝 | Alipay

微信 | WeChat

≡