ftp空间网站,电子商城网站开发的背景,crm管理系统开发语言,网络售后服务文章目录目录第一题#xff1a;解题思路#xff1a;代码实现#xff1a;c顺序查找二分查找Python第二题#xff1a;解题思路#xff1a;代码实现#xff1a;cpython第三题#xff1a;解题思路#xff1a;代码实现#xff1a;c使用栈辅助反转链表python第四题#xff…
文章目录目录第一题解题思路代码实现c顺序查找二分查找Python第二题解题思路代码实现cpython第三题解题思路代码实现c使用栈辅助反转链表python第四题解题思路代码实现cpython第五题解题思路代码实现cpython第六题解题思路代码实现cpython第七题解题思路代码实现c第一种第二种python第八题解题思路代码实现c递归的方法(该方法的通过率比较低)归纳法100%通过动态规划的方法100%通过python第九题解题思路代码实现递归方法c非递归方法python第十题解题思路代码实现cpython目录
第一题
在一个二维数组中每个一维数组的长度相同每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。
解题思路
这是一个查找问题由于题目特定强调了有序的数组所以我们如果使用直接使用顺序查找肯定是不当的。所以我们可以利用数组的性质进行查找。
1.使用顺序查找但是不从第一个数开始找而是从二位数组的左上角的数开始找如果正好相等则返回如果小于被查找的数则行号加一否则列号减一。2.使用二分查找。可以遍历行或者列先比较该行或者该列的最后一个元素与要查找的元素的大小关系然后针对该行或者列进行二分查找
代码实现
c
顺序查找
#include iostream
#include vectorusing namespace std;//二维数组查找
bool Find(int target , vectorvectorint array){if(array.empty()){return false;}int row array.size();int col array[0].size();int i0 , j col - 1;while(i row j 0){if(target array[i][j]){return true;}else if (target array[i][j]){i ;}else{j --;}}return false;
}int main(){int a1[] { 1, 1, 8, 9, };int a2[] { 2, 4, 9, 12, };int a3[] { 4, 7, 10, 13, };int a4[] { 6, 8, 11, 15, };vectorvectorint myArry;myArry.push_back(vectorint(a1, a1 4));myArry.push_back(vectorint(a2, a2 4));myArry.push_back(vectorint(a3, a3 4));myArry.push_back(vectorint(a4, a4 4));coutthe result is : Find(100,myArry)endl;return 0;
}二分查找
#include iostream
#include vector
#include algorithmusing namespace std;//二维数组查找
bool Find(int target , vectorvectorint array){if(array.empty()){return false;}int row array.size(); //行的数目//每行进行查找for(int i 0;irow;i){if(binary_search(array[i].begin(),array[i].end(),target)){return true;}}//扫描完每行后没有发现则说明没有找到return false;
}int main(){int a1[] { 1, 1, 8, 9, };int a2[] { 2, 4, 9, 12, };int a3[] { 4, 7, 10, 13, };int a4[] { 6, 8, 11, 15, };vectorvectorint myArry;myArry.push_back(vectorint(a1, a1 4));myArry.push_back(vectorint(a2, a2 4));myArry.push_back(vectorint(a3, a3 4));myArry.push_back(vectorint(a4, a4 4));coutthe result is : Find(4,myArry)endl;return 0;
}Python
def Find(target ,array):if array []:return Falserow len(array) - 1col len(array[0])i 0 j col - 1while i row and j 0:if target array[i][j]:return Trueelif target array[i][j]:i 1else:j - 1return FalseFind(1,[[1, 1, 8, 9],[2, 4, 9, 12],[4, 7, 10, 13],[6, 8, 11, 15]])第二题
请实现一个函数将一个字符串中的每个空格替换成“%20”。例如当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路
一般的思维遍历字符串然后找到每个字符串中每个空格的位置然后使用“%20”进行替换但是由于字符串存储的是顺序结构所以插入字符串会导致字符串中字符后移所以可以先统计出字符串中空字符的个数然后首先算出要移动的位置从字符串后面往前逐步替换掉。借助c中的string类的方法首选将字符串转换为string ,然后调用find函数和replace函数将每个空格替换成“%20”最后将string转换为c_string.
代码实现
c
#include stringclass Solution {
public:void replaceSpace(char *str,int length) {string tempStr(str); //将c风格的字符串转换为string//遍历字符串找到每个空格的位置然后替换掉它for(int i0 ; i tempStr.size(); i){int tempIndex tempStr.find( , i); //前面搜过的一定不能重复搜索if(tempIndex!-1){tempStr.replace(tempIndex,1,%20);}}strcpy(str,tempStr.c_str());}};python
## 字符串空格替换
def replaceSpace(s):s s.replace( ,%20)return s
replaceSpace(We Are Happy)第三题
输入一个链表按链表值从尾到头的顺序返回一个ArrayList。
解题思路
借助于栈结构保存数据然后依次出栈即可时间复杂度为O(N),空间复杂度为O(N);借助vector数组反转函数先用vector保存顺序遍历链表的值然后直接对数组进行反转然后输出时间复杂度为O(N),空间复杂度为O(1);先将链表反转然后再依次遍历。
代码实现
c
使用栈辅助
#include functional
#include string
#include cstring
#include stackusing namespace std;struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};vectorint printListFromTailToHead(ListNode *head){stackint dataStack;vectorint arrayList;if(head NULL){return ;}while(head ! NULL){dataStack.push(head-val);head head-next;}while(!dataStack.empty()){arrayList.push_back(dataStack.top());dataStack.pop();}return arrayList;
}
反转链表
#include iostream
#include vector
#include algorithm
#include functionalusing namespace std;struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};vectorint printListFromTailToHead(ListNode *head){ListNode *pCur , *pPre , *pNext;pPre head;pCur pPre-next;while(pCur){pNext pCur-next;pCur-next pPre;pPre pCur;pCur pNext;}head-next NULL;head pPre;vectorint arrayList;while(head){arrayList.push_back(head-val);head head-next;}return arrayList;
}python
## 链表反转输出
def printListFromTailToHead(listNode):tempList []#顺序访问链表并将链表的值保存while listNode ! None:tempList.append(listNode.val)listNode listNode.nextreturn list(reversed(tempList)) #直接输出列表的反转第四题
输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}则重建二叉树并返回。
解题思路
由于是二叉树的构建所以我们应该想到用递归的方法进行构建递归的终止条件就是前序遍历和中序遍历的节点个数为1,递归的过程主要是从pre中把根节点确定然后再从Vin中根据确定的根节点确定该节点的左右子树集合。
代码实现
c
#include iostream
#include vector
#include algorithm
#include functionalusing namespace std;//二叉树节点结构定义
struct TreeNode {int val; //值域TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};
//二叉树重建
class Solution {
public:TreeNode* reConstructBinaryTree(vectorint pre,vectorint vin) {if(pre.size() ! vin.size()){return NULL;}int vinLen vin.size();if(vinLen 0){return NULL;}vectorint left_pre , left_vin , right_pre , right_vin;TreeNode * head new TreeNode(pre[0]);int headIndex 0;for(int i0 ; i vin.size() ; i ){if(vin[i] pre[0]){headIndex i;break;}}for(int i 0; i headIndex ; i){left_vin.push_back(vin[i]);left_pre.push_back(pre[i1]);//前序第一个为根节点}for(int i headIndex 1 ; i vin.size() ; i){right_pre.push_back(pre[i]);right_vin.push_back(vin[i]);}//和shell排序的思想类似取出前序和中序遍历根节点左边和右边的子树//递归再对其进行上述所有步骤即再区分子树的左、右子子数直到叶节点head-left reConstructBinaryTree(left_pre,left_vin);head-right reConstructBinaryTree(right_pre,right_vin);return head;}};python
##重建二叉树#树的节点结构
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right None#重构二叉树
def reConstructBinaryTree(pre , tin):if len(pre)! len(tin):return NonerootNode TreeNode(pre[0])rootTinIndex tin.index(rootNode.val)if rootTinIndex None:return NonerootNode.left reConstructBinaryTree(pre[1:rootTinIndex 1] , tin(:rootTinIndex))rootNode.right reConstructBinaryTree(pre[rootTinIndex1:] , tin(rootTinIndex:))return root第五题
用两个栈来实现一个队列完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路
使用两个栈一个用于实现队头一个用于实现队尾操作。需要注意的是出队操作如果用于实现队头的那个栈没有数据则需要将实现队尾栈中的数据复制到其中。
代码实现
c
#include iostream
#include vector
#include algorithm
#include functional
#include stackusing namespace std;class solution{
private:stackint stack1; //队头stackint stack2; //队尾
public:void push(int node){stack2.push(node);}int pop(){if(stack1.empty() stack2.empty()){ //队列为空return -1;}if(stack1.empty()){ //队列一半为空while(!stack2.empty()){stack1.push(stack2.top());stack2.pop();}}int tempData stack1.top();stack1.pop();return tempData;}
};int main(){solution s;s.push(1);s.push(2);s.push(3);couts.pop()endl;couts.pop()endl;couts.pop()endl;return 0;
}python
## 两个栈实现队列
class Solution:def __init__(self):self.stack1 []self.stack2 []def push(self, node):# write code hereself.stack1.append(node)def pop(self):# return xxif self.stack1 [] and self.stack2 []:return Noneif self.stack2 []:while(len(self.stack1)):self.stack2.append(self.stack1.pop())return self.stack2.pop()if __name__ __main__:s Solution()s.push(1)s.push(2)s.push(0)print s.pop()第六题
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转该数组的最小值为1。 NOTE给出的所有元素都大于0若数组大小为0请返回0。
解题思路
首先肯定是可以通过STL中的算法将旋转后的数组进行排序后然后输出第一个元素的值便可可以利用旋转素组的特性是将一个有序的数组的前一部分搬到数组的末尾所以数组可以分为2块前一块和后一块都是一种升序的数组而转折点就是最小值。
代码实现
c
class Solution {
public:int minNumberInRotateArray(vectorint rotateArray) {if(rotateArray.size() 0){return 0;}for(int i 0 ; i rotateArray.size() ; i ){if(rotateArray[i] rotateArray[0]){ //找到后面第一个比数组第一个元素小的元素return rotateArray[i]; }}return rotateArray[0]; //如果没有找到说明最小的元素在数组的第一个位置}
};python
# -*- coding:utf-8 -*-
class Solution:def minNumberInRotateArray(self, rotateArray):# write code hereif len(rotateArray) 0:return 0for i in range(len(rotateArray)):if rotateArray[i] rotateArray[0]:return rotateArray[i]return rotateArray[0] 第七题
大家都知道斐波那契数列现在要求输入一个整数n请你输出斐波那契数列的第n项从0开始第0项为0。 n39
解题思路
使用for循环遍历使用斐波那契数列推到公式得出每个数然后由一个数组进行保存。由于不需要整个数列只是数列的最后一项想所以可以将存储空间直接取3每次求解迭代的时候更新进行。
代码实现
c
第一种
class Solution {
public:int Fibonacci(int n) {vectorint fibonacciArray(n1);if(n0){return 0; }fibonacciArray[0] 0;fibonacciArray[1] 1;for(int i 2 ; i n1 ; i){fibonacciArray[i] fibonacciArray[i-2] fibonacciArray[i-1];}return fibonacciArray[n];}
};第二种
class Solution {
public:int Fibonacci(int n) {vectorint fibonacciArray(3);if(n0){return 0; }if(n 2){return 1;}fibonacciArray[0] 0;fibonacciArray[1] 1;for(int i 2 ; i n1 ; i){fibonacciArray[2] fibonacciArray[0] fibonacciArray[1];fibonacciArray[0] fibonacciArray[1];fibonacciArray[1] fibonacciArray[2];}return fibonacciArray[2];}
};python
#输出斐波那契数列的第N项
def Fibonacci(n):if n 0 :return -1elif n0:return 0elif n 2:return 1else:pre 0cur 1for i in range(2,n1):last pre curpre curcur lastreturn lastFibonacci(3)第八题
一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法先后次序不同算不同的结果。
解题思路
归纳 把台阶都看成是木板即有n块木板其中最后一块木板是青蛙的目的地是必须存在的所以总共是n-1块木板可以选择。由于青蛙一次可以跳一级也可以一次跳两级所以对于当前这个木板它可以被跳也可以不被跳那么久总共存在2^(n-1)种可能。递归 记跳 n 级台阶有 f(n) 种方法 如果第一次跳 1 级那么之后的 n-1 级有 f(n-1) 种跳法 如果第一次跳 2 级那么之后的 n-2 级有 f(n-2) 种跳法 实际上就是首两项为 1 和 2 的斐波那契数列
代码实现
c
递归的方法(该方法的通过率比较低)
#include iostream
#include vector
using namespace std;
int jumpFloorII(int number) {if(number 0){return -1;}else if(number 1){return 1;}else if(number 2){return 2;}else{return jumpFloorII(number - 1) jumpFloorII(number - 2);}}int main(){coutjumpFloorII(5)endl;return 0;
}归纳法100%通过
#include iostream
#include vector
#include cmathusing namespace std;int jumpFloorII(int number) {if(number 0){return -1;}else{return pow(2,number-1);}}int main(){coutjumpFloorII(6)endl;return 0;
}动态规划的方法100%通过
class Solution {
public:int jumpFloorII(int number) {vectorint dp(number1, 1); //创建动态U规划列表for (int i2; inumber; i) for(int j1; ji; j)dp[i] dp[j];return dp[number];}
};python
##青蛙跳台阶问题
#归纳方法
def jumpFloorII(number):if number 0:return -1else:return 2 ** (number - 1)jumpFloorII(5)第九题
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形总共有多少种方法
解题思路
递归 f(1) 1; f(2) 2; 当n2时画图可知第一块小矩形可横放和竖放。横放后剩余的长度为n-2竖放后剩余的长度为n-1。 所以f(n) f(n-1) f(n-2); (n 2)类比 我们对算法模型做些简化我们知道只可以放置两种类型的小矩形一种是竖着放的21矩形另一种是两块横着放的21矩形上下放置形成的22正方形而题目要放置的是2n的大矩形。 我们将上面模型映射到一维即是我们有一条长度为n的线段现在要么放置长度为1要么放置长度为2的线段请将该线段填满。 这让我想起了走阶梯的题目一个n级阶梯每次要么走一级要么两级请问有多少种方法。 综上分析可知 n 1时 f(n) 1; n 2时 f(n) 2; n 2时f(n) f(n - 1) f(n - 2);
代码实现
递归方法
c
#include iostream
#include vector
#include cmathusing namespace std;int rectCover(int number) {if(number 0 ){return -1;}else if(number 0){return 0;}else if(number 1){return 1;}else if(number 2){return 2;}else{return rectCover(number - 1) rectCover(number - 2);}}int main(){coutrectCover(6)endl;return 0;
}非递归方法
#include iostream
#include vector
#include cmathusing namespace std;int rectCover(int number) {if(number 0 ){return -1;}else if(number 0){return 0;}else if(number 1){return 1;}else if(number 2){return 2;}vectorint tempArry(3);tempArry[0] 1;tempArry[1] 2;for(int i 3 ; i number;i){tempArry[2] tempArry[0] tempArry[1];tempArry[0] tempArry[1];tempArry[1] tempArry[2];}return tempArry[2];
}int main(){coutrectCover(6)endl;return 0;
}python
#矩形覆盖问题
def rectCover(number):if number0:return -1elif number0:return 0elif number1:return 1elif number 2:return 2else:return rectCover(number -1) rectCover(number - 2)rectCover(6)第十题
输入一个整数输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路
通过移位操作每次与1做与求出其中1的个数一定要注意负数的情况比较巧的做法 如果一个整数不为0那么这个整数至少有一位是1。如果我们把这个整数减1那么原来处在整数最右边的1就会变为0原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子一个二进制数1100从右边数起第三位是处于最右边的一个1。减去1后第三位变成0它后面的两位0变成了1而前面的1保持不变因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算从原来整数最右边一个1那一位开始所有位都会变成0。如110010111000.也就是说把一个整数减去1再和原整数做与运算会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1就可以进行多少次这样的操作。
代码实现
c
class Solution {
public:int NumberOf1(int n) {int count 0;while (n ! 0) {count;n (n - 1) n;}return count; }
};class Solution {
public:int NumberOf1(int n) {int count 0;if(n 0){n n 0x7fffffff; //当n为负数的时候只需要将最高位的0置位为1count; }while( n!0 ){if(n 1 1){count;}n n 1;}return count; }
};python
#查找一个数二进制表示中1的个数
def NumberOf1(n):count 0if n 0 :n n 0xfffffffcount 1while n ! 0:if n 1 1:count 1n n 1return countNumberOf1(3)
