#每日一题合集#牛客JZ3-JZ12

为了督促自己每天练一练编程
时间：2022年8月1日-2022年8月10日
网站：https://www.nowcoder.com/exam/oj/ta?tpId=13

文章目录

• • 8.1-JZ3.数组中重复的数字
  • 8.2-JZ4.二维数组中的查找
  • 8.3-JZ5.替换空格
  • 8.4-JZ6.从尾到头打印链表
  • 8.5-JZ7.重建二叉树
  • 8.6-JZ8.二叉树的下一个结点
  • 8.7-JZ9.用两个栈实现队列
  • 8.8-JZ10.斐波那契数列
  • 8.9-JZ11.旋转数组的最小数字
  • 8.10-JZ12.矩阵中的路径

8.1-JZ3.数组中重复的数字

很基础的题了，直接数组暴力解就完了

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型vector * @return int整型*/int duplicate(vector<int>& numbers) {// write code hereint i, n;int a[10010]={0};n = numbers.size();for(i = 0; i < n; i++){if(a[numbers[i]] > 0)return numbers[i];elsea[numbers[i]]++;}return -1;}
};

8.2-JZ4.二维数组中的查找

这个也比较简单，由于这个二维数组有序，直接斜着判断即可；

class Solution {
public:bool Find(int target, vector<vector<int> > array) {if(array.size() == 0)return false;if(array[0].size() == 0)return false;int n = array.size(), m = array[0].size();int i, j;for(i = n-1, j = 0; i >= 0 && j < m;){if(array[i][j] == target)return true;else if(array[i][j] < target)j++;elsei--;}return false;}

8.3-JZ5.替换空格

基础字符串操作

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param s string字符串 * @return string字符串*/string replaceSpace(string s) {// write code herestring result;for(int i = 0; i < s.length(); i++){if(s[i] == ' ')result += "%20";elseresult += s[i];}return result;}
};

8.4-JZ6.从尾到头打印链表

这个最直接的方法就是存进容器里，然后直接翻转。但题目本身应该是期望，是使用三个节点，完成链表内部的翻转，然后再存进数组。(感觉用数组返回，就会让人用数组偷懒)

class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> tmp;while(head){tmp.push_back(head->val);head = head->next;}reverse(tmp.begin(), tmp.end());return tmp;}
};

8.5-JZ7.重建二叉树

这个题第一眼看的时候有点懵，看了眼题解，主要是思路要清晰，利用vin.length == pre.length的特性，通过递归分治，获得二叉树

class Solution {
public:TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {if(pre.size() <= 0 || vin.size() <= 0)return NULL;TreeNode *res = new TreeNode(pre[0]);for(int i = 0; i < vin.size(); i++){if(pre[0] == vin[i]){vector<int> leftpre(pre.begin()+1, pre.begin()+i+1);vector<int> leftvin(vin.begin(), vin.begin()+i);res->left = reConstructBinaryTree(leftpre, leftvin);vector<int> rightpre(pre.begin()+i+1, pre.end());vector<int> rightvin(vin.begin()+i+1, vin.end());res->right = reConstructBinaryTree(rightpre, rightvin);break;}}return res;}
};

8.6-JZ8.二叉树的下一个结点

这里需要助理的是，他有指向父节点的指针next

class Solution {
public:vector<TreeLinkNode*> Tree;void InOrder(TreeLinkNode* root){if(root == NULL)return;InOrder(root->left);Tree.push_back(root);InOrder(root->right);}TreeLinkNode* GetNext(TreeLinkNode* pNode) {TreeLinkNode* root = pNode;while(root->next)root = root->next;InOrder(root);int n = Tree.size();for(int i = 0; i < n - 1; i++){if(pNode == Tree[i])return Tree[i + 1];}return NULL;}
};

8.7-JZ9.用两个栈实现队列

使用两个栈实现队列，题目只要求了两个操作。第一个插入整数就直接是入栈操作；第二个删除头部，就需要第一个栈里面的数一个个移到第二个栈，这样最开始入栈的数，在第二站就是最后入栈的。
注意：一定要让栈二全部pop完，栈2一定是比栈1的早的。

class Solution
{
public:void push(int node) {stack1.push(node);}int pop() {if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}}int res = stack2.top();stack2.pop();return res;}private:stack<int> stack1;stack<int> stack2;
};

8.8-JZ10.斐波那契数列

基础题

class Solution {
public:int Fibonacci(int n) {if(n == 1 || n == 2)return 1;elsereturn Fibonacci(n-1) + Fibonacci(n-2);}
};

8.9-JZ11.旋转数组的最小数字

这个上来想到的是暴力，但担心超时，选了最简单的省时间的方法：二分。需要注意的是，中值和最右相等时，是无法判断的，让右指针一个个往左来计算。

class Solution {
public:int minNumberInRotateArray(vector<int> rotateArray) {int left = 0, right = rotateArray.size() - 1;while(left < right){int mid = (left + right) / 2;if(rotateArray[mid] > rotateArray[right])left = mid + 1;else if(rotateArray[mid] < rotateArray[right])right = mid;elseright--;}return rotateArray[left];}
};

8.10-JZ12.矩阵中的路径

最开始有一组样例一直不过，后面尝试吧bool visit初始化成false了以后，就过了。考虑原因应该是，虽然bool值全局变量为false，但在这，估计是随机赋值了？(不太确定，但bool visit[21][21]];就过不了，bool visit[21][21] = {false};就能通过。)

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param matrix char字符型vector> * @param word string字符串 * @return bool布尔型*/bool visit[21][21] = {false};bool dfs(vector<vector<char> >& matrix, int n, int m, int i, int  j, string word, int k){if(i < 0 || j < 0 || i >= n || j >= m || (matrix[i][j] != word[k]) || (visit[i][j]==true))return false;if(k == word.length() - 1)return true;visit[i][j] = true;if(dfs(matrix, n, m, i+1, j, word, k+1)|| dfs(matrix, n, m, i-1, j, word, k+1)|| dfs(matrix, n, m, i, j+1, word, k+1)|| dfs(matrix, n, m, i, j-1, word, k+1))return true;visit[i][j] = false;return false;}bool hasPath(vector<vector<char> >& matrix, string word) {// write code hereif(matrix.size() == 0)return false;int n = matrix.size(), m = matrix[0].size();for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(dfs(matrix, n, m, i, j, word, 0))return true;}}return false;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！