插件素材网站,网站站长seo推广,国外的有名的网站,深圳设计网站培训文章目录目录第11题#xff1a;解题思路#xff1a;代码实现#xff1a;cpython第12题#xff1a;解题思路#xff1a;代码实现#xff1a;cpython第13 题#xff1a;解题思路#xff1a;代码实现#xff1a;cpython第 14题#xff1a;解题思路#xff1a;代码实现解题思路代码实现cpython第12题解题思路代码实现cpython第13 题解题思路代码实现cpython第 14题解题思路代码实现cpython第15 题解题思路代码实现c递归实现python第16 题解题思路代码实现cpython第17题解题思路代码实现c递归实现python第18题解题思路代码实现cpython第19题解题思路代码实现cpython第20 题解题思路代码实现cpython目录
第11题
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解题思路
这道题非常简单但是存在陷阱即当exponent为负数和0的时候要特别考虑其余的没有了
代码实现
c
#include iostream
#include vector
#include cmathusing namespace std;double Power(double base, int exponent) {double temp base;if(exponent 0 ){for(int i 1 ;i-(exponent);i){temp * base;}return 1.0/temp;}else if(exponent 0){return 1;}else{for(int i 1 ; iexponent ; i){temp * base;}return temp;}}int main(){coutPower(2,-3)endl;coutPower(2,0)endl;coutPower(2,2)endl;return 0;
}运行时间5ms
占用内存456k
python
# -*- coding:utf-8 -*-
class Solution:def Power(self, base, exponent):# write code herereturn base**exponent运行时间22ms 占用内存5624k
第12题
输入一个整数数组实现一个函数来调整该数组中数字的顺序使得所有的奇数位于数组的前半部分所有的偶数位于数组的后半部分并保证奇数和奇数偶数和偶数之间的相对位置不变。
解题思路
通过使用2个栈结果来保存奇数项和偶数项,然后对数组从后向前遍历遇到奇数就压奇数栈遇到偶数就压偶数栈然后在依次弹出奇数栈和偶数栈中的内容并保存在原始的数组中先将原始数组清空
代码实现
c
#include stack
class Solution {
public:void reOrderArray(vectorint array) {stackint oddStack;//定义奇数栈stackint evenStack;//定义偶数栈for(int i array.size()-1 ; i 0 ;i--){if(array[i] % 2 0){evenStack.push(array[i]);}else{oddStack.push(array[i]);}}array.clear();while(!oddStack.empty()){array.push_back(oddStack.top());oddStack.pop();}while(!evenStack.empty()){array.push_back(evenStack.top());evenStack.pop();} }
};运行时间5ms
占用内存480k
python
# -*- coding:utf-8 -*-
# -*- coding:utf-8 -*-
class Solution:def reOrderArray(self, array):# write code hereoddList [] #保存奇数evenList [] #保存偶数for i in array:if i % 2 0:evenList.append(i)else:oddList.append(i)array []for i in oddList:array.append(i)for i in evenList:array.append(i)return array运行时间23ms
占用内存5724k
第13 题
输入一个链表输出该链表中倒数第k个结点。
解题思路
首先顺序遍历一遍链表并将值压栈然后在通过栈弹出第K个元素即为链表的倒数第K个元素。时间复杂度为O(n),空间复杂度为O(n);
代码实现
c
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {stackListNode* tempStack;if(pListHead NULL){return NULL;}if(k 0){return NULL;}int dataCount 0;while (pListHead ! NULL){tempStack.push(pListHead);pListHead pListHead-next;dataCount;}if(dataCount k){return NULL;}for(int i 0 ; i k - 1 ; i){tempStack.pop();}return tempStack.top();}
};运行时间4ms
占用内存476k
python
# -*- coding:utf-8 -*-
class Solution:def FindKthToTail(self, head, k):# write code hereres[]while head:res.append(head)headhead.nextif klen(res) or k1:returnreturn res[-k]运行时间26ms 占用内存5732k
第 14题
输入一个链表反转链表后输出新链表的表头。
解题思路
本体的意思应该是输出原始链表的反转链表而不是仅仅只是输出反转后链表的头结点所以通过栈的结构实现不佳。思想是从头到尾遍历链表然后将每两个节点进行反转操作即可最好将原始的头结点的后继置NULL头结点直接取最后一个元素
代码实现
c
class Solution {
public:ListNode* ReverseList(ListNode* pListHead) {if(pListHead NULL)return NULL;ListNode *pCurrent ,*pPre,*pNext;//一、指针的初始化阶段pPre pListHead;pCurrent pPre-next ;while(pCurrent) //二、反转单链表的核心代码{pNext pCurrent-next ; //1. 缓冲pCurrent后面的单链表pCurrent-next pPre ; //2. 反转单链表pPre pCurrent; //3.让pPre指针后移pCurrent pNext ; //4. 让pCurrent指针后移}//三、处理并返回头指针pListHead-next NULL; //把原头结点的next域变成空指针pListHead pPre ; //把头结点指向最后一个结点产生新的头结点也就是把原单链表的尾结点变成头结点return pListHead;}
};运行时间5ms
占用内存464k
python
# -*- coding:utf-8 -*-
第15 题
输入两个单调递增的链表输出两个链表合成后的链表当然我们需要合成后的链表满足单调不减规则。
解题思路
递归的方法依次在链表1和链表2遍历每次取两个链表中较小的那个值插入到新的链表中去。
代码实现
c
递归实现
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){if(pHead1 NULL pHead2 NULL){return NULL;}if(pHead1 NULL){return pHead2;}if(pHead2 NULL){return pHead1;}ListNode* head; //新链表的表头if(pHead1-val pHead2-val){head pHead1;head-next Merge(pHead1-next , pHead2); //递归调用}else{head pHead2;head-next Merge(pHead1, pHead2-next);}return head;}
};运行时间4ms
占用内存492k
python
# -*- coding:utf-8 -*-
第16 题
输入两棵二叉树AB判断B是不是A的子结构。ps我们约定空树不是任意一个树的子结构
解题思路
找一颗树是否为另外一颗树的子树当然是遍历主树先从根节点开始如果根节点相同就比较左右孩子节点如果相同则返回true否则就递归遍历主树的左子树和右子树只要找到一个相同即可。在比较子树和主树之前我们要定义一个函数用于比较两个二叉树是否相同。也是从根节点开始依次对比根节点左孩子右孩子是否相同只有全部节点相同才是相同。
代码实现
c
class Solution {
public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){if(!pRoot1 || !pRoot2) return false;bool resultfalse;if(pRoot1-val pRoot2-val)resultisSubtree(pRoot1,pRoot2); // 找到判断子树if(!result) resultHasSubtree(pRoot1-left,pRoot2); // 未找到匹配的根节点以及匹配的子树则继续向下递归if(!result) resultHasSubtree(pRoot1-right,pRoot2);return result;}//判断2棵树是否相同bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2){if(!pRoot2) return true; // 子树遍历完成关键语句if(!pRoot1) return false; // 主树异常时的输出关键语句提高鲁棒性bool resulttrue;if(pRoot1-val!pRoot2-val) resultfalse; //根节点不同肯定不同if(result) resultisSubtree(pRoot1-left,pRoot2-left); //判断两颗树的左子树是否相同if(result) resultisSubtree(pRoot1-right,pRoot2-right);//判断两颗树的右子树是否相同return result;}
};运行时间3ms
占用内存504k
python
# -*- coding:utf-8 -*-
第17题
操作给定的二叉树将其变换为源二叉树的镜像。
解题思路
从题目中给出的例子可以看出其实就是对树的每一层中双亲的左右孩子交换了一下。我们可以递归的访问树的每一层然后交换每一层的双亲节点的左右孩子就可以。
递归的方法先从根节点开始交换根节点左右孩子节点然后调用递归依次遍历树的左子树和右子树交换子树中的孩子节点。
代码实现
c
递归实现
class Solution {
public:void Mirror(TreeNode *pRoot) {//递归推出条件if(pRootNULL){return;}//交换根节点的两个孩子TreeNode* tempNode;tempNode pRoot-left;pRoot-left pRoot-right;pRoot-right tempNode;Mirror(pRoot-left); //递归左子树Mirror(pRoot-right); //递归右子树}
};运行时间4ms
占用内存468k
python
# -*- coding:utf-8 -*-
class Solution:# 返回镜像树的根节点def Mirror(self, root):# write code hereif root None:return ;tempNode TreeNode(-1)tempNode root.leftroot.left root.rightroot.right tempNodeself.Mirror(root.left)self.Mirror(root.right)运行时间34ms
占用内存5736k
第18题
输入一个矩阵按照从外向里以顺时针的顺序依次打印出每一个数字例如如果输入如下4 X 4矩阵 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解题思路
设定四个变量分别指向行列的起始点和终止点然后将数据遍历分成4个节阶段分别是从左到右从上到下从右向左从下到上每个过程结束后对应的指针都应该变化循环执行直到遍历完全部的数据。
代码实现
c
class Solution {
public:vectorint printMatrix(vectorvectorint matrix) {vectorintres; //用来保存遍历过的数据res.clear(); int rowmatrix.size();//行数int collormatrix[0].size();//列数//计算打印的圈数int circle((rowcollor?row:collor)-1)/21;//圈数for(int i0;icircle;i){//从左向右打印for(int ji;jcollor-i;j)res.push_back(matrix[i][j]); //从上往下的每一列数据for(int ki1;krow-i;k)res.push_back(matrix[k][collor-1-i]);//判断是否会重复打印(从右向左的每行数据)for(int mcollor-i-2;(mi)(row-i-1!i);m--)res.push_back(matrix[row-i-1][m]);//判断是否会重复打印(从下往上的每一列数据)for(int nrow-i-2;(ni)(collor-i-1!i);n--)res.push_back(matrix[n][i]);}return res;}
};运行时间4ms
占用内存468k
python
# -*- coding:utf-8 -*-
第19题
定义栈的数据结构请在该类型中实现一个能够得到栈中所含最小元素的min函数时间复杂度应为O1
解题思路
定义一个辅助栈这个栈顶元素始终是最小值。
代码实现
c
class Solution {
public:stackint stack1,stack2;void push(int value) {stack1.push(value);//两种情况下才将元素压入辅助栈中if(stack2.empty())stack2.push(value);else if(valuestack2.top()){stack2.push(value);}}void pop() {if(stack1.top()stack2.top())stack2.pop();stack1.pop();}int top() {return stack1.top(); }int min() {return stack2.top();}};运行时间2ms
占用内存472k
python
# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.data []self.minData []def push(self, node):# write code hereself.data.append(node)if self.minData [] or node self.minData[-1]:self.minData.append(node)def pop(self):# write code hereif self.data[-1] self.minData[-1]:self.minData.pop()self.data.pop()def top(self):# write code herereturn self.data[-1]def min(self):# write code herereturn self.minData[-1]运行时间31ms
占用内存5624k
第20 题
输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。注意这两个序列的长度是相等的
解题思路
借用一个辅助的栈遍历压栈顺序先讲第一个放入栈中这里是1然后判断栈顶元素是不是出栈顺序的第一个元素这里是4很显然1≠4所以我们继续压栈直到相等以后开始出栈出栈一个元素则将出栈顺序向后移动一位直到不相等这样循环等压栈顺序遍历完成如果辅助栈还不为空说明弹出序列不是该栈的弹出顺序。
举例
入栈1,2,3,4,5
出栈4,5,3,2,1
首先1入辅助栈此时栈顶1≠4继续入栈2
此时栈顶2≠4继续入栈3
此时栈顶3≠4继续入栈4
此时栈顶44出栈4弹出序列向后一位此时为5,辅助栈里面是1,2,3
此时栈顶3≠5继续入栈5
此时栈顶55出栈5,弹出序列向后一位此时为3,辅助栈里面是1,2,3
….
依次执行最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序
代码实现
c
class Solution {
public:bool IsPopOrder(vectorint pushV,vectorint popV) {if(pushV.size() 0) return false; vectorint stack;for(int i 0,j 0 ;i pushV.size();){stack.push_back(pushV[i]);while(j popV.size() stack.back() popV[j]){ //当辅助栈的栈顶元素与弹出栈的相同则将辅助栈的元素弹出同时继续遍历弹出栈stack.pop_back();j;} }return stack.empty();}
};运行时间3ms
占用内存380k
python
# -*- coding:utf-8 -*-
