当前位置： 代码迷 >> 综合 >> 程序员面试题(C++ 实现) - Day2
  详细解决方案

程序员面试题(C++ 实现) - Day2

热度：103   发布时间：2023-10-14 23:03:47.0

文章目录

    • 说明
    • 今日题目一览
      • 1. 旋转数组中的最小数字
      • 2. 斐波那契数列
      • 3. 跳台阶(变态跳台阶)
      • 4. 矩形覆盖
      • 5. 二进制中 1 的个数
    • 联系博主

说明

  • 以下题目均来自于牛客网
  • 以下代码用 C++11 编写
  • 以下代码均已编译通过(Compile by MINGW)
  • 以下代码均有测试案例(Main function)
  • 以下代码均已进行优化或部分优化(Optimize)
  • 以下代码均有注释(Comment)
  • 部分题目附有解析(Analysis)
  • 如有错误或侵权，请联系博主

今日题目一览

  1. 旋转数组的最小数字
  2. 斐波那契数列
  3. 跳台阶(变态跳台阶)
  4. 矩形覆盖
  5. 二进制中 1 的个数

1. 旋转数组中的最小数字

问题描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解析

该问题是二分搜索的另一种变相形式，设定 low、mid、high，

  • 当 val_mid > val_high 时，说明最小的数字存在于[mid + 1, high]区间(注意不是存在于[mid, high]区间)，然后执行 low = mid + 1;
  • 当 val_mid == val_high 时，说明最小的数字存在于[low, high - 1]区间(注意不是存在于[low, mid]区间)，然后执行 high --;
  • 当 val_mid < val_high 时，说明最小的数字存在于[low, mid]区间(注意不是存在于[low, mid - 1]区间)，然后执行 high = mid;

实现

/* 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。*/#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int minNumberInRotateArray1(vector<int> rotateArray) {
    sort(rotateArray.begin(), rotateArray.end());return rotateArray[0];
}int minNumberInRotateArray2(vector<int> array) {
    int low = 0 ;int high = array.size() - 1;while(low < high) {
    int mid = low + (high - low) / 2;if(array[mid] > array[high]) {
    low = mid + 1;} else if(array[mid] == array[high]) {
      //这步是关键high = high - 1;} else {
    high = mid;}}return array[low];
}int main(int argc, char const *argv[]) {
    //Teststd::vector<int> v;v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(1);v.push_back(2);cout << minNumberInRotateArray1(v) << endl;cout << minNumberInRotateArray2(v) << endl;return 0;
}

输出结果

1
1

2. 斐波那契数列

问题描述

输出斐波那契数列的第 n 项(从0开始，第0项为0)。斐波那契数列：0 1 1 2 3 5 8 13 21 34 …

解析

这个主要是迭代算法的理解与应用，知道 f(n) = f(n - 1) + f(n - 2)即可，更多请参考：

Fibonacci 斐波那契数列的几种写法、时间复杂度对比

实现

/* 输出斐波那契数列的第 n 项(从0开始，第0项为0) 斐波那契数列：0 1 1 2 3 5 8 13 ...*/#include <iostream>using namespace std;// 方法一
int Fibonacci1(int n) {
    if(n == 0)return 0;if(n == 1)return 1;int a = 0, b = 1;int m = 0;int i;for(i = 2; i <= n; i++) {
      // a + b = mm = a + b;a = b;b = m;}return m;
}// 方法二
int Fibonacci2(int n) {
    int result[3] = {
    0, 1, 1};if (n <= 2)return result[n];return Fibonacci2(n - 1) + Fibonacci2(n - 2);
}int main(int argc, char const *argv[]) {
    // Testfor(int i = 0; i < 20; i++)  // 从 1 开始cout << Fibonacci1(i) << " ";cout << "\n-----------------\n";for(int i = 0; i < 20; i++)  // 从 0 开始cout << Fibonacci2(i) << " ";return 0;
}

输出结果

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 
-----------------
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

今天看到一个非常酷的求斐波那契数列的写法：

#include <numeric>
#include <vector>
#include <functional>v = std::vector<int>(10);
v[0] = 1;
std::adjacent_difference(v.begin(), v.end() - 1, v.begin() + 1, std::plus<int>());

3. 跳台阶(变态跳台阶)

问题描述

跳台阶：一只青蛙一次可以跳 1 级台阶，也可以跳 2 级。求该青蛙跳上一个 n 级台阶总共有多少种跳法(先后次序不同算不同的结果)。

变态跳台阶：一只青蛙一次可以跳 1 级台阶，也可以跳上 2 级……它也可以跳 n 级
求该青蛙跳上一个 n 级的台阶总共有多少种跳法？

解析

参考博客：牛客网——跳台阶和变态跳台阶问题

参考博客：程序员面试100题之二：跳台阶问题（变态跳台阶）

跳台阶(2 种思路)：

方法一

这种问题一般是有规律的，跳1级台阶，只有1种方法；跳2级台阶，有2种方法；跳2级台阶，有3种方法；跳4级台阶，有5种方法，依次下去，跳一个n级的台阶的方法数是跳n-1级台阶的方法数与跳n-2阶台阶的方法数的总和。这种思路可以用逆推去想，要跳上一个n级台阶，可以从n-1级台阶跳1级，也可以从n-2级台阶跳2级，这就相当于跳上n-1级台阶的方法加上跳上n-2级台阶的方法。

方法二

这算算法的思路还是和上面的一样，只不过在在写法上显得更为简洁，主要看代码注释。

实现(跳台阶)

/* 一只青蛙一次可以跳 1 级台阶，也可以跳 2 级。 求该青蛙跳上一个 n 级台阶总共有多少种跳法(先后次序不同算不同的结果)。*/#include <iostream>using namespace std;// 方法一
// 和上面的斐波那契数列一样// 方法二
int jumpFloor(int n) {
    int f = 1, g = 2;  // 定义了斐波那契数列的第二项和第三项n--;while(n--) {
     // 这个循环实现了 g 的递加和 f 的重置，细细写写就知道了g += f;f = g - f;  // 先加后减就实现了 f 变为原来 g 的值}return f;
}int main(int argc, char const *argv[]) {
    //Test//eg: 跳三层方法有： 111 - 12 - 21cout << jumpFloor(3) << endl;//eg: 跳五层方法有： 1111 - 121 - 112 - 211 - 22cout << jumpFloor(4) << endl;return 0;
}

输出结果

3
5

变态跳台阶

可以用逆推的思路去想，跳n级台阶，可以从n-1级跳上来，也可以从n-2级跳上来，从n-3级跳上来，依次下去，从第1级跳上去，或直接跳上去，所以，跳n级台阶的方法数相当于其它所有台阶数的方法的总和再加上从0级跳上去，表达式为 f(n) = f(n-1) + f(n-2) +…+ f(2) + f(1) + 1。例如：

当跳1级台阶时，f(1) = 1;
当跳2级台阶时，f(2) = f(1) + 1 = 2;
当跳3级台阶时，f(3) = f(2) + f(1) + 1 = 4;
当跳4级台阶时，f(4) = f(3) + f(2) + f(1) + 1 = 8;
…
f(n) = f(n-1) + f(n-2) +…+ f(2) + f(1) + 1
f(n-1) = f(n-2) +…+ f(2) + f(1) + 1
推：f(n) - f(n-1) = f(n-1)
推：f(n) = 2 * f(n-1)

实现(变态跳台阶)

/* 一只青蛙一次可以跳 1 级台阶，也可以跳上 2 级……它也可以跳 n 级 求该青蛙跳上一个 n 级的台阶总共有多少种跳法*/#include <iostream>using namespace std;int jumpFloorII(int number) {
    if(number == 0)return number;int total = 1;for(int i = 1; i < number; i++)total *= 2;return total;
}int main(int argc, char const *argv[]) {
    //Test//eg: 跳三层方法有： 111 - 12 - 21 - 3cout << jumpFloorII(3) << endl;return 0;
}

输出结果

4

4. 矩形覆盖

问题描述

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。
请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

解析

依旧是斐波那契数列(主要是考察问题的转换能力)

实现

/* 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？*/#include <iostream>using namespace std;int rectCover(int number) {
    if (number <= 0) {
    return number;}int f1 = 1;int f2 = 2;int f3;for (int i = 3; i <= number; i++) {
    f3 = f1 + f2;f1 = f2;f2 = f3;}return f3;
}int main(int argc, char const *argv[]) {
    //Test//...return 0;
}

输出结果

// 没有输出

5. 二进制中 1 的个数

问题描述

输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。

解析

用 & 位运算符的性质

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

实现

/* 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。*/#include <iostream>using namespace std;int NumberOf1(int n) {
    int count = 0;unsigned int flag = 1;while(flag) {
    if (n & flag) {
    count++;}flag = flag << 1;}return count;
}int main(int argc, char const *argv[]) {
    //Testint m = 10;  // 1010cout << NumberOf1(m) << endl;int n = 11;  // 1011cout << NumberOf1(n) << endl;int p = 12;  // 1100cout << NumberOf1(p) << endl;return 0;
}

输出结果

2
3
2

联系博主

邮箱：Neverland_LY@163.com

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.