100字范文 > python数据结构与算法分析第2版_题库 | 百度数据结构 / 算法面试题型介绍及解析第 2 期...

python数据结构与算法分析第2版_题库 | 百度数据结构 / 算法面试题型介绍及解析第 2 期...

时间：2022-10-12 16:58:01

题目1：分解成质因数 (如 435234=251*17*17*3*2)

void prim(int m, int n){if(m>n){while(m%n != 0) n++;m /= n;prim(m, n);printf("%d*", n);}}int main(int argc, char* argv[]){int n = 435234;printf("%d=", n);prim(n, 2);return getchar();}

题目2：寻找迷宫的一条出路(o：通路；X 障碍)

#define MAX_SIZE 8int H[4] = {0, 1, 0, -1};int V[4] = {-1, 0, 1, 0};char Maze[MAX_SIZE][MAX_SIZE] = {{'X','X','X','X','X','X','X','X'},{'o','o','o','o','o','X','X','X'},{'X','o','X','X','o','o','o','X'},{'X','o','X','X','o','X','X','o'},{'X','o','X','X','X','X','X','X'},{'X','o','X','X','o','o','o','X'},{'X','o','o','o','o','X','o','o'},{'X','X','X','X','X','X','X','X'}};void FindPath(int X, int Y){if(X == MAX_SIZE || Y == MAX_SIZE){for(int i = 0; i < MAX_SIZE; i++)for(int j = 0; j < MAX_SIZE; j++)printf("%c%c", Maze[i][j], j < MAX_SIZE-1 ? ' ' : '\n');}else for(int k = 0; k < 4; k++)if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X < MAX_SIZE && 'o' == Maze[X][Y]){Maze[X][Y] = ' ';FindPath(X+V[k], Y+H[k]);Maze[X][Y] ='o';}}int main(int argc, char* argv[]){FindPath(1,0);return getchar();}

题目3：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1，10，11 和 12，1 一共出现了 5 次。简单的方法就是按照给位进行分析在个位出现 1 的个数 = n/10+(个位 = 0,0；个位> 1,1; 个位 = 1，低 0 位 + 1)；十位位出现 1 的个数 = n/100*10+(十位 = 0,0；十位> 1,10,；十位 = 1，低一位 + 1)；百位出现 1 的个数 = n/1000*100+(百位 = 0,0；百位> 1,100; 百位 = 1，低两位 + 1)；等等算法的复杂度仅仅和位数有关算法描述：(1)求出所给正整数 a 的位数，假设为 N,num 保存 1 的个数(2)另 p=a,num+=p/10i*10i-1;(i=1...N-1);(3)令 p=a/10i-1;p=p%10,if(p==1) num+=a%10i-1+1;if(p>1) num+=10i-1;(i=1....N)(4)printf(num);手工求解：125个位 = 12+1十位 = 10+10百位 = 0+2659 个 1

1 #include2 int test(int a){3int i;4int num=1;5if(a==0)6 return 1;7for(i=1;i<=a;i++)8 num*=10;9return num;10 }11 int function(int a){12int p=a;13int num=0;14int N=0;15int temp;16int i;17while(p!=0)18{19 p=p/10;20 N++;21}22p=a;23for(i=1;i<=N;i++){24 num+=p/test(i)*test(i-1);25 temp=a/test(i-1)%10;26 if(temp==1)27 num+=a%test(i-1)+1;28 if(temp>1)29 num+=test(i-1);30}31return num;32 }3334 void main(){35printf("%d\n",function(88888));36 }

结果输出 45679题目4：输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。如果一个整数不为 0，那么这个整数至少有一位是 1。如果我们把这个整数减 1，那么原来处在整数最右边的 1 就会变为 0，原来在 1 后面的所有的 0 都会变成 1 (如果最右边的 1 后面还有 0 的话)。其余所有位将不会受到影响。举个例子：一个二进制数 1100，从右边数起第三位是处于最右边的一个 1。减去 1 后，第三位变成 0，它后面的两位 0 变成了 1，而前面的 1 保持不变，因此得到的结果是 1011. 我们发现减 1 的结果是把最右边的一个 1 开始的所有位都取反了。这个时候如果我们再把原来的整数和减去 1 之后的结果做与运算，从原来整数最右边一个 1 那一位开始所有位都会变成 0。如 1100&1011=1000. 也就是说，把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0. 那么一个整数的二进制有多少个 1，就可以进行多少次这样的操作。C++

class Solution {public:int NumberOf1(int n) {int count = 0;while(n){++count;n = (n - 1) & n;}return count;}};

Python在 Python 中，由于负数使用补码表示的，对于负数，最高位为 1，而负数在计算机是以补码存在的，往右移，符号位不变，符号位 1 往右移，最终可能会出现全 1 的情况，导致死循环。与 0xffffffff 相与，就可以消除负数的影响。

# -*- coding:utf-8 -*-class Solution:def NumberOf1(self, n):# write code herecount = 0if n<0:n = n & 0xffffffffwhile n:count += 1n = n & (n-1)return count

或者可以使用一个更直观的方法，直接位移即可，代码如下：

# -*- coding:utf-8 -*-class Solution:def NumberOf1(self, n):# write code herereturn sum([(n >> i & 1) for i in range(0,32)])

题目5：输入一个整型数组，数组里有正数也有负数。数组中一个或者连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O (n)首先需要考虑的条件：数组里有正数也有负数，根据这个条件，从数组第一个元素开始，temp 累计相加，当 temp 增加时，我们就将 temp 赋值给 sum。当 temp 为小于 0 ，我们就将 temp 归为 0，但是此时 sum 还是保存之前的最大值。temp 接下来继续这样累加。

#include "stdafx.h"#includeusing namespace std;int FindMaxSum(int pData[],int length){if (pData == NULL || length <= 0)return 0;int sum = 0;int temp = 0;for (int i = 0; i < length; ++i){temp += pData[i];if (temp>sum)sum = temp;if (temp <= 0)temp = 0;}return sum;}int _tmain(int argc, _TCHAR* argv[]){int data[] = { 1,-7,4,3,-2,5 };cout << FindMaxSum(data, 6) << endl;return 0;}

题目6：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 {3，32，321}，则打印出这三个数字能排成的最小数字为 321323。遇到这个题，全排列当然可以做，但是时间复杂度为 O (n!)。在这里我们自己定义一个规则，对拼接后的字符串进行比较。排序规则如下：若 ab > ba 则 a 大于 b，若 ab < ba 则 a 小于 b，若 ab = ba 则 a 等于 b；根据上述规则，我们需要先将数字转换成字符串再进行比较，因为需要串起来进行比较。比较完之后，按顺序输出即可。C++

class Solution {public:string PrintMinNumber(vector<int> numbers) {int length = numbers.size();if(length == 0){return "";}sort(numbers.begin(), numbers.end(), cmp);string res;for(int i = 0; ires += to_string(numbers[i]);}return res;}private:// 升序排序static bool cmp(int a, int b){string A = to_string(a) + to_string(b);string B = to_string(b) + to_string(a);return A < B;}};

Python

# -*- coding:utf-8 -*-class Solution:def PrintMinNumber(self, numbers):# write code hereif len(numbers) == 0:return ''compare = lambda a, b:cmp(str(a) + str(b), str(b) + str(a))min_string = sorted(numbers, cmp = compare)return ''.join(str(s) for s in min_string)

题目7：显示一个序列中和等于 10 的所有组合这个题的扩展应用很多，虽然下面运算的复杂度很高，但是其思想非常巧妙，借助位运算实现了所有可能的组合，关键是该思想值得借鉴，在没有比较好的方法的情况下，我们就需要一个个来试，但是要一个不漏的把所有情况都考虑到一般的方法很麻烦下面就详细介绍一下该算法的思想：(1)首先根据序列的长度确定组合数，如长度为 8 则最大的组合只可能是 8(2)从 1 到 1<<8 中每一个数的等于 1 的位就代表一种组合，我们把这种组合对应的数相加，看其是否等于所求的值，如何是就输出对应位的值该算法显然可以再进行优化，但是其依然很难在大数据面前有效首先就是循环的次数上，如果序列的长度是 n, 则需要查找的次数为 2n-1，指数倍的增加显然性能会指数倍的下降如何降低查找的次数，可以对序列先排序，找出序列中最小的 x 个数使得他们的和是最小的不小于 m 的序列，这意味着组合数就由 n 变为了 x，查找上限 2x-1, 上限找到后就找下限，我们从最大的开始相加，直到 y 个数使得他们是最大的不大于 m 位置，这意味着至少需要 y 位是 1 的二进制，那么下限就变成了 2y-1 了。这一点在和较大的情况下有作用，比如序列长度是 100，每个数都是 1，让你找和为 100 的序列，x=100,y=100，这表示最大的组合数是 100，这些组合数对应的二进制数有 100 个是 1，那就一种情况了，如何统计二进制数中 1 的个数，这个用位运算比较快，同时为了进一步提高效率，可以结合 y 的值，统计 1 和 0 的个数同时统计，当 1 的个数 > y 的时候就查看，当 0 的个数大于 n-100 时表示该组合不行，就换下一个。

1 #include2 #include3 using namespace std;4 void main()5 {67int arry[]={1,5,3,4,2,10,6,7},num=0;8int n=sizeof(arry)/sizeof(int);9bitset<32> x;//由于[]取数的是倒着来的，所以可以设成32位，前面的0位，完全不被取到。10for(int i=0;i<1<11{12 x=i;13 num=0;//记住这的清0.。这是这个程序唯一易错的地方。在多次循环都要用到同一个计数器的时候，一定要记得在开始的时候清0；1415 for(int j=0;j16 {17 if(x[j])18 num+=arry[j];19 }20 if(num==10)21 {22 cout<endl;23 for(int j=0;j24 if(x[j])25 cout<" ";2627 cout<<endl;2829 }30}31cout<endl;3233 }

题目8：求数组中和为给定值的所有子序列大致意思是满足组合攻击技能，必须是所选择时技能的和为 m(m>0)，且所选的这些技能的乘积最大：分解后主解决两个问题：其一：求数组中和为 m 的所有子数组；其二：在满足一的条件下，求所有子数组的最大值；主要考察的还是如何求数组中和为 m 的所有子数组：如：数组 [1,2,3,4,5,6]，m=7 时，满足条件的子数组有 [1,2,4],[3,4],[2,5],[1,6];主要使用回溯法解决该问题，思路之后补上：

package com.didi;import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;public class Main1 { /*** @param args*/ public static void main(String[] args) {// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);while(scanner.hasNext()){ int n = scanner.nextInt(); int sum = scanner.nextInt(); int[] arr = new int[n]; for(int i=0;iarr[i] = scanner.nextInt(); } Arrays.sort(arr);//必须先排序 ArrayList> lists = new ArrayList>(); boolean[] visited = new boolean[n]; backTrack(arr, visited, 0, 0, sum, lists);//求和为sum的所有组合数 System.out.println(lists); System.out.println(lists.size());//求和为sum的所有组合数 System.out.println(maxFighting(lists));//求最大组合攻击力 } } //求非降序序列中和为定值的所有组合，必须为非降序序列，否则会重复，如{2 4 2 5 4 1 6}-->[[2, 4, 4], [2, 2, 5, 1], [4, 2, 4], [4, 5, 1], [5, 4, 1]],统计有重复只是顺序不一样 public static void backTrack(int[] input, boolean[] visited, int n, int sum, int key, ArrayList> lists){if(sum>key) return;if(sum==key){ArrayList list = new ArrayList(); for(int j=0; j<=n; j++){ if(visited[j]){list.add(input[j]);} } lists.add(list); return; }if(n>=input.length) return;for(int i=n;i-1;i++){ if(!visited[i]){sum += input[i];visited[i] = true;backTrack(input, visited, i+1, sum, key, lists);visited[i] = false;sum -= input[i]; while(i-1&&input[i]==input[i+i++; } } } public static int maxFighting(ArrayList> lists){int size = lists.size();if(lists==null||size==0) return -1;int maxMultipy = Integer.MIN_VALUE;int multipy = 1;for(int i=0;i ArrayList list = lists.get(i); for(int j=0;jmultipy *=list.get(j); } if(multipy>maxMultipy){maxMultipy = multipy; } multipy = 1; } return maxMultipy; }}

题目9：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数如数组 {7,5,6,4}，逆序对总共有 5 对，{7,5}，{7,6}，{7,4}，{5,4}，{6,4}；思路 1：暴力解法，顺序扫描整个数组，每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成一个逆序对。假设数组中含有 n 个数字，由于每个数字都要和 O (n) 个数字作比较，因此这个算法的时间复杂度是 O (n^2)。思路 2：分治思想，采用归并排序的思路来处理，如下图，先分后治：先把数组分解成两个长度为 2 的子数组，再把这两个子数组分解成两个长度为 1 的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为 1 的子数组 {7}、{5} 中 7>5，因此(7,5)组成一个逆序对。同样在第二对长度为 1 的子数组 {6}，{4} 中也有逆序对(6,4)，由于已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组进行排序，避免在之后的统计过程中重复统计。逆序对的总数= 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量总结统计数组逆序对的过程：先把数组分隔成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序，其实这个排序过程就是归并排序的思路。C++：注意：InversePairsCore 形参的顺序是 (data,copy)，而递归调用时实参是 (copy,data)。要明白递归函数 InversePairsCore 的作用就行了，它是对 data 的左右半段进行合并，复制到辅助数组 copy 中有序。

class Solution {public:int InversePairs(vector<int> data) {if(data.size() == 0){return 0;}// 排序的辅助数组vector<int> copy;for(int i = 0; i < data.size(); ++i){copy.push_back(data[i]);}return InversePairsCore(data, copy, 0, data.size() - 1) % 1000000007;}long InversePairsCore(vector<int> &data, vector<int> &copy, int begin, int end){// 如果指向相同位置，则没有逆序对。if(begin == end){copy[begin] = data[end];return 0;}// 求中点int mid = (end + begin) >> 1;// 使 data 左半段有序，并返回左半段逆序对的数目long leftCount = InversePairsCore(copy, data, begin, mid);// 使 data 右半段有序，并返回右半段逆序对的数目long rightCount = InversePairsCore(copy, data, mid + 1, end);int i = mid; //i 初始化为前半段最后一个数字的下标int j = end; //j 初始化为后半段最后一个数字的下标int indexcopy = end; // 辅助数组复制的数组的最后一个数字的下标long count = 0; // 计数，逆序对的个数，注意类型while(i >= begin && j >= mid + 1){if(data[i] > data[j]){copy[indexcopy--] = data[i--];count += j - mid;}else{copy[indexcopy--] = data[j--];}}for(;i >= begin; --i){copy[indexcopy--] = data[i];}for(;j >= mid + 1; --j){copy[indexcopy--] = data[j];}return leftCount + rightCount + count;}};

Python：

# -*- coding:utf-8 -*-class Solution:def InversePairs(self, data):# write code hereif not data:return 0temp = [i for i in data]return self.mergeSort(temp, data, 0, len(data)-1) % 1000000007def mergeSort(self, temp, data, low, high):if low >= high:temp[low] = data[low]return 0mid = (low + high) / 2left = self.mergeSort(data, temp, low, mid)right = self.mergeSort(data, temp, mid+1, high)count = 0i = lowj = mid+1index = lowwhile i <= mid and j <= high:if data[i] <= data[j]:temp[index] = data[i]i += 1else:temp[index] = data[j]count += mid-i+1j += 1index += 1while i <= mid:temp[index] = data[i]i += 1index += 1while j <= high:temp[index] = data[j]j += 1index += 1return count + left + right

题目10：给定一个十进制数 M，将其转化为 N 进制数，其中 2<=N<=16，其中 N 为 32 为整型数；输入：M N，如 7 2输出转化结果：111注意点：考虑负数的情况，记得添加负号(其实直接添加负号这个办法，我觉得有点不靠谱，但是系统竟然 A 了，有知道这个怎么处理的，可以评论下，这样处理为什么能过，还有还可以怎么处理，谢谢大家！！)；思路：使用一个辅助栈来存放 M 对 N 取余的结果(M% N)；处理余数 <=9 和> 9 两种情况，因为按照 16 进制，>9 的数用 ABCDEF 取代再更新取余后 M 的取值：M=M/N；循环处理 2,3 两个步骤，直到 M=0；处理最终结果，出栈，直到栈为空；

package com.didi;import java.util.Scanner;import java.util.Stack;public class Main {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);while(scanner.hasNext()){int M = scanner.nextInt();int N = scanner.nextInt();if(M>=0){convert(M, N);}}}public static void convert(int m, int n){if(n==10){System.out.println(m);return;}boolean flag = true;Stackstack = new Stack();StringBuilder str = new StringBuilder();char[] ch = {'A','B','C','D','E','F'};while(m!=0){if(m%n<10){stack.push(m%n+'0');}else{stack.push(m%n-10+'A');}m = m/n;}while(!stack.isEmpty()){if(m<0&&flag){str.append("-");flag = false;} if(stack.peek()-'0'<10){str.append(stack.pop()-'0');}else{str.append(ch[stack.pop()-'A']);}}System.out.println(str.toString());}}