小红划数字
小红拿到了一个正整数 。
对于任意大于 的数而言,她每次操作可以划掉这个数的一个数字,生成一个新的数。
例如,对于正整数 而言,小红经过一次操作可以生成 、 、 、 、 这五种数字。
小红想知道,自己最少操作多少次,可以把 变成一个偶数?
数据范围:
进阶:空间复杂度 ,时间复杂度
输入描述:
一个正整数
输出描述:
小红操作的最少次数。如果小红无论如何也不能生成偶数,则输出-1。
示例1
输入
输出
说明
显然102本身就是偶数,小红不需要进行操作。
示例2
输入
输出
说明
把最后一个1划掉,形成1232,是偶数。可以证明这样操作是最少的。
示例3
输入
输出
说明
无法进行删除得到偶数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #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; } 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,反转该链表后,返回新链表的表头。
数据范围:
要求:空间复杂度 ,时间复杂度 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
代码:
提交时间:2022-09-25 语言:C++ 运行时间: 4 ms 占用内存:564K 状态:答案正确
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
|
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == nullptr) { return nullptr; } ListNode* pNode = pHead; ListNode* pNodeNext = pHead->next; ListNode* pNodeLast = pHead; 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:
思路
优先不断从做左子树遍历到底,杀入树多左边最底部,再通过回溯方式,从底部慢慢向上的右子树遍历。我们只需在遍历左子树节点的时候,push当前值就为前序遍历的结果了。
代码
提交时间:2022-09-25 语言:C++ 运行时间: 4 ms 占用内存:468K 状态:答案正确
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
class Solution { public:
vector<int> preorderTraversal(TreeNode* root) { TreeNode* now = root; TreeNode* subLeft = nullptr; TreeNode* subRight = nullptr; std::stack<TreeNode*> treeStack; std::vector<int> ret; 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,返回它的中序遍历结果。
数据范围:树上节点数满足 ,树上每个节点的值满足
进阶:空间复杂度 ,时间复杂度
思路
与前序遍历方式相同, 只是再回溯的过程进行保存根节点的值就为中序遍历的结果。
代码
提交时间:2022-09-26 语言:C++ 运行时间: 5 ms 占用内存:440K 状态:答案正确
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
class Solution { public:
vector<int> inorderTraversal(TreeNode* root) { 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; } };
|
后序遍历
知识
后序遍历是,先遍历左子树,再遍历右子树,最后再遍历根节点。
描述
给定一个二叉树,返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围:二叉树的节点数量满足 ,二叉树节点的值满足 ,树的各节点的值各不相同
样例图
思路
这个相对比较复杂一点,需要在回溯上进行一步操作,之前的回溯只是简单的移动节点到右子节点上,那么我们的遍历有点类似于横向的遍历方式,只不过横向的深度有限从左边开始遍历的。
代码
提交时间:2022-09-26 语言:C++ 运行时间: 4 ms 占用内存:396K 状态:答案正确
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
class Solution { public:
vector<int> postorderTraversal(TreeNode* root) { 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) { nodeStack.push(now); now = now->left; }
flag = 1; 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; } };
|