刷刷题-logo
职业技能刷题工具
下载APP
活动合作
刷刷题大使
兼职招聘
题集市
发布考试
创建题库
登录
logo - 刷刷题
创建自己的小题库
年VIP赠送3次导题
搜索
算法题库 - 刷刷题
算法题库
题数
2000
考试分类
程序员>面试题>算法
售价
¥0
手机预览
收藏
分享
复制链接
新浪微博
分享QQ
微信扫一扫
微信内点击右上角“…”即可分享
去刷题
简介
算法
...更多
章节目录
题目预览(可预览10题)
【简答题】
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第 `n` 项(从 `0` 开始,第 `0` 项为 `0`)。`n<=39`
参考答案:

解法一:采用递归方式,简洁明了,但效率很低,存在大量的重复计算。

f(10)
/ \
f(9) f(8)
/ \ / \
f(8) f(7) f(7) f(6)
/ \ / \
f(7) f(6) f(6) f(5)

解法二:从下往上计算,递推,时间复杂度 `O(n)`。

参考解析:
【单选题】
不使用递归也可以实现二叉树的先序、中序和后续遍历().
A.
B.
参考答案:
A
参考解析:
【单选题】
#include "stdio.h"void main(){int i,s;for(i=1,s=0;i<=5;i++){s*=i;}printf("%d",s);}以上代码的执行结果是:()
A.
是0
B.
是24
C.
是6
D.
是120
参考答案:
A
参考解析:
【单选题】
关于三种基本控制结构的主要作用描述正确的是()
A.
顺序结构表示程序中的各步操作按出现的先后顺序执行
B.
选择结构表示程序的处理步骤出现了分支,所有分支都要遍历一篇
C.
循环结构表示程序反复执行某个或某些操作,直到判断条件为假(或为真)时才终止循环
D.
选择结构有单选泽、双选择和多选择三种
参考答案:
B
参考解析:
【简答题】
要将一张 100 元的钞票,换成等值的5元、2元、1元一张的钞票共 50 张。其中一种换法如下: 5元: 3张、 2元: 38 张、l 元:9 张,求出所有的换钱方案。
【 算法设计 】
x 表示 5 元的张数: l ≤ x ≤ 20 ;
y 表示 2 元的张数: 1 ≤ y ≤ 50 ;
z 表示 1 元的张数: 1 ≤ z ≤ 100.
【 参考程序 】
Dim x As Integer
Dim y As Integer
Dim z As Integer
For X = 1 to 20
For y = 1 to 50
For z = 1 to 100
If_______Then
Print x ; y ; z 'x y z 之间以分号分隔
End If
Next Z
Next y
Next X
根据上述回答下列问题:
1 、本题采用的算法是_____ (填:解析法/枚举法/排序法/递归法)。
2 、程序代码中空白处应填写的条件是_____(填写字母)。
A 5x + 2y+z=100 Or x+y+z = 50
B 5x + 2y+z=100 And x+y+z = 50
C 5*x + 2*y+z=100 Or x+y+z = 50
D 5*x + 2*y+z=100 And x+y+z = 50
参考答案:
枚举法;D
参考解析:
【单选题】
数据结构中,查询(Searching)特定元素是否在表中,是()的概念。
A.
查找
B.
查看
C.
分页
D.
添加
参考答案:
A
参考解析:
【编程题】

给定一个整数数组 A是元组 (i, j),其中  i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i

找出 A 中的坡的最大宽度,如果不存在,返回 0 。

 

示例 1:

输入:[6,0,8,2,1,5]
输出:4
解释:
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

示例 2:

输入:[9,8,1,0,1,9,4,0,4,1]
输出:7
解释:
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.

 

提示:

  1. 2 <= A.length <= 50000
  2. 0 <= A[i] <= 50000

 

参考答案:

方法一:排序

思路与算法

对于每一个形如 A[i] = v 的元素,我们将其索引 i 按照对应值 v 排序之后的顺序写下。例如, A[0] = 7, A[1] = 2, A[2] = 5, A[3] = 4,我们应该这样顺序写下索引值 i=1, i=3, i=2, i=0

然后,当我们写下一个索引 i 的时候,我们可以得到候选的宽度答案 i - min(indexes_previously_written) (如果这个值是正数的话)。 我们可以用一个变量 m 记录已经写下的最小索引。

class Solution {
    public int maxWidthRamp(int[] A) {
        int N = A.length;
        Integer[] B = new Integer[N];
        for (int i = 0; i < N; ++i)
            B[i] = i;

        Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));

        int ans = 0;
        int m = N;
        for (int i: B) {
            ans = Math.max(ans, i - m);
            m = Math.min(m, i);
        }

        return ans;
    }
}
class Solution(object):
    def maxWidthRamp(self, A):
        ans = 0
        m = float('inf')
        for i in sorted(range(len(A)), key = A.__getitem__):
            ans = max(ans, i - m)
            m = min(m, i)
        return ans

复杂度分析

  • 时间复杂度: $O(N \log N)$,其中 $N$ 是 A 的长度。

  • 空间复杂度: $O(N)$,基于排序的实现方法。


方法二:二分检索候选位置

思路

按照降序考虑 i , 我们希望找到一个最大的 j 满足 A[j] >= A[i](如果存在的话)。

因此,候选的 j 应该是降序的:如果存在 j1 < j2 并且 A[j1] <= A[j2] ,那么我们一定会选择 j2

算法

我们使用列表记录这些候选的 j。举一个例子,当 A = [0,8,2,7,5],对于 i = 0 的候选列表应该是 candidates = [(v=5, j=4), (v=7, j=3), (v=8, j=1)]。我们要时刻维护候选列表 candidates 按照索引值降序,对应值升序。

现在,我们可以使用二分检索的办法找到最大的索引 j 满足 A[j] >= A[i]:也就是列表中第一个满足 v >= A[i] 的那一项。

import java.awt.Point;

class Solution {
    public int maxWidthRamp(int[] A) {
        int N = A.length;

        int ans = 0;
        List<Point> candidates = new ArrayList();
        candidates.add(new Point(A[N-1], N-1));

        // candidates: i's decreasing, by increasing value of A[i]
        for (int i = N-2; i >= 0; --i) {
            // Find largest j in candidates with A[j] >= A[i]
            int lo = 0, hi = candidates.size();
            while (lo < hi) {
                int mi = lo + (hi - lo) / 2;
                if (candidates.get(mi).x < A[i])
                    lo = mi + 1;
                else
                    hi = mi;
            }

            if (lo < candidates.size()) {
                int j = candidates.get(lo).y;
                ans = Math.max(ans, j - i);
            } else {
                candidates.add(new Point(A[i], i));
            }
        }
        return ans;
    }
}
class Solution(object):
    def maxWidthRamp(self, A):
        N = len(A)

        ans = 0
        candidates = [(A[N-1], N-1)]
        # candidates: i's decreasing, by increasing value of A[i]
        for i in xrange(N-2, -1, -1):
            # Find largest j in candidates with A[j] >= A[i]
            jx = bisect.bisect(candidates, (A[i],))
            if jx < len(candidates):
                ans = max(ans, candidates[jx][1] - i)
            else:
                candidates.append((A[i], i))

        return ans

复杂度分析

  • 时间复杂度: $O(N \log N)​$,其中 $N​$ 是数组 A 的长度。

  • 空间复杂度: $O(N)$。

参考解析:
【编程题】

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排,则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排,注意,这里的时间是半开区间,即 [start, end), 实数 x 的范围为,  start <= x < end

当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内),就会产生重复预订。

每次调用 MyCalendar.book方法时,如果可以将日程安排成功添加到日历中而不会导致重复预订,返回 true。否则,返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解释: 
第一个日程安排可以添加到日历中.  第二个日程安排不能添加到日历中,因为时间 15 已经被第一个日程安排预定了。
第三个日程安排可以添加到日历中,因为第一个日程安排并不包含时间 20 。

说明:

  • 每个测试用例,调用 MyCalendar.book 函数最多不超过 100次。
  • 调用函数 MyCalendar.book(start, end)时, start 和 end 的取值范围为 [0, 10^9]
参考答案:

方法一:暴力法

预订新的日程安排 [start, end) 时,检查当前每个日程安排是否与新日程安排冲突。若不冲突,则可以添加新的日程安排。

算法: 我们将维护一个日程安排列表(不一定要排序)。当且仅当其中一个日程安排在另一个日程安排结束后开始时,两个日程安排 [s1,e1)[s2,e2) 不冲突:e1<=s2e2<=s1。这意味着当 s1<e2s2<e1 时,日程安排发生冲突。

class MyCalendar(object):
    def __init__(self):
        self.calendar = []

    def book(self, start, end):
        for s, e in self.calendar:
            if s < end and start < e:
                return False
        self.calendar.append((start, end))
        return True
public class MyCalendar {
    List<int[]> calendar;

    MyCalendar() {
        calendar = new ArrayList();
    }

    public boolean book(int start, int end) {
        for (int[] iv: calendar) {
            if (iv[0] < end && start < iv[1]) return false;
        }
        calendar.add(new int[]{start, end});
        return true;
    }
}

复杂度分析

  • 时间复杂度:$O(N^2)$。$N$ 指的是日常安排的数量,对于每个新的日常安排,我们检查新的日常安排是否发生冲突来决定是否可以预订新的日常安排。所以时间复杂度为 $\sum_k^N O(k) = O(N^2)$。
  • 空间复杂度:$O(n)$,calendar 所使用的空间大小。

方法二:平衡树

如果我们按时间顺序维护日程安排,则可以通过二分查找日程安排的情况来检查新日常安排是否可以预订,时间复杂度为 $O(\log N)$ (其中 $N$ 是已预订的日常安排数),若可以预定则我们还需要在排序结构中插入日常安排。

算法: - 我们需要一个数据结构能够保持元素排序和支持快速插入。在 java 中,TreeMap 是最适合的。在 python 中,我们可以构建自己的二叉树结构。

class Node:
    __slots__ = 'start', 'end', 'left', 'right'
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = self.right = None

    def insert(self, node):
        if node.start >= self.end:
            if not self.right:
                self.right = node
                return True
            return self.right.insert(node)
        elif node.end <= self.start:
            if not self.left:
                self.left = node
                return True
            return self.left.insert(node)
        else:
            return False

class MyCalendar(object):
    def __init__(self):
        self.root = None

    def book(self, start, end):
        if self.root is None:
            self.root = Node(start, end)
            return True
        return self.root.insert(Node(start, end))
class MyCalendar {
    TreeMap<Integer, Integer> calendar;

    MyCalendar() {
        calendar = new TreeMap();
    }

    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start),
                next = calendar.ceilingKey(start);
        if ((prev == null || calendar.get(prev) <= start) &&
                (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度 (Java):$O(N \log N)$。其中 $N$ 是预订的日程安排数。对于每个新日程安排,我们用 $O(\log N)$ 的时间搜索该日程安排是否合法,若合法则将其插入日常安排中需要 $O(1)$ 的时间。
  • 时间复杂度 (Python):最坏的情况 $O(N^2)$,其他情况是 $O(N \log N)$。对于每个新日程安排,若新日程安排合法则将新日程安排插入到二叉树中。由于此树可能不平衡,因此可能需要线性步骤来遍历每个日常安排。
  • 空间复杂度:$O(N)$,数据结构所使用的空间。
参考解析:
【简答题】
一只青蛙一次可以跳上`1`级台阶,也可以跳上`2`级。求该青蛙跳上一个`n`级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
参考答案:

跳上 `n` 级台阶,可以从 `n-1` 级跳 `1` 级上去,也可以从 `n-2` 级跳 `2` 级上去。所以f(n) = f(n-1) + f(n-2)

参考解析:
【单选题】
(2009年上海会考试题)流程图是以图形符号的形式来描述算法,关于流程图的叙述,正确的是_____。
A.
流程图是描述算法的唯一方法
B.
流程图的图形符号可以自行规定
C.
流程图的图形符号要符合一定的规范
D.
计算机可以直接识别和执行流程图
参考答案:
C
参考解析:
刷刷题-刷题-导入试题 - 刷刷题
创建题目
创建题库
创建自己的小题库 - 刷刷题