算法题附件

labuladong的算法小抄官方完整版-已压缩.pdf.zip

1、判断一个单词是否是回文？

回文是指把相同的词汇或句子，在下文中调换位置或颠倒过来，产生首尾回环的情趣，叫做回文，也叫回环。 例如：man,mamam,313

进阶
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
你能不将整数转为字符串来解决这个问题吗？

示例 1: 输入: 121 输出: true

示例 2:

输入: -121

输出: false

解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10

输出: false

解释: 从右向左读, 为 01 。因此它不是一个回文数。

  1. func palindrome( _ num: Int) -> Bool {
  2.     /*
  3.         解题思路
  4.         1.首位与末尾都是相同的数
  5.         2.则后半部分进行反转之后，与前半部分数相同
  6.         3.末尾不能为0
  7.         4.如果是奇数位，需要去除中位数进行比较
  8.      */
  9.     if num < 0 || num % 10 == 0 && num != 0 {
  10.         return false;
  11.     }
  12.     var revNum = 0;
  13.     var vNum = num;
  14.     while vNum > revNum  {
  15.         revNum = revNum * 10 + vNum % 10;
  16.         vNum /= 10;
  17.     }
  18.     // 因为有奇数的情况出现，所以需要考虑去除中位数
  19.     return vNum == revNum || vNum == revNum / 10
  20. }

2、常用缓存淘汰算法

  • LRU
    • 思想
      • 如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）
    • 实现思路
      • 可以用双向链表（LinkedList）+哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找）
    • 优缺点

  • LFU

    • 思想
      • 如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。
    • 实现思路
      • 考虑到 LFU 会淘汰访问频率最小的数据，我们需要一种合适的方法按大小顺序维护数据访问的频率，实现策略为小顶堆+哈希表
    • 优缺点

  • FIFO

    • 思想（先进先出（FIFO，队列））
      • 如果一个数据是最先进入的，那么可以认为在将来它被访问的可能性很小。空间满的时候，最先进入的数据会被最早置换（淘汰）掉

    • 实现思路

      • 维护一个FIFO队列，按照时间顺序将各数据（已分配页面）链接起来组成队列，并将置换指针指向队列的队首。再进行置换时，只需把置换指针所指的数据（页面）顺次换出，并把新加入的数据插到队尾即可。

    • 优点

    • 缺点

      • 判断一个页面置换算法优劣的指标就是缺页率，而FIFO算法的一个显著的缺点是，在某些特定的时刻，缺页率反而会随着分配页面的增加而增加，这称为Belady现象。产生Belady现象现象的原因是，FIFO置换算法与进程访问内存的动态特征是不相容的，被置换的内存页面往往是被频繁访问的，或者没有给进程分配足够的页面，因此FIFO算法会使一些页面频繁地被替换和重新申请内存，从而导致缺页率增加

      • 现在不再使用FIFO算法

3、爬楼梯问题

  • 问题描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  • 解答：

    • 斐波那契数列问题
    • 使用动态规划法

    • 规律：a[n] = a[n-1]+a[n-2]

      • 使用递推调用

  • leetcode 70](https://leetcode-cn.com/problems/climbing-stairs/))

4、整数反转

  • 问题描述：给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果

  • 解答：

    • 较好方案：

      • 弹出/推入数字&溢出检查

        • pop操作 int pop = x % 10; x /= 10;

        • push操作 rev = rev * 10 + pop;

    • 方案二：栈

  • leetcode 7

5、红黄蓝三色球

  • 问题描述：有红、黄、蓝三种颜色的气球。在牛客王国，1个红气球+1个黄气球+1个蓝气球可以兑换一张彩票。

    • 2个红气球+1个黄气球可以兑换1个蓝气球。
    • 2个黄气球+1个蓝气球可以兑换1个红气球。
    • 2个蓝气球+1个红气球可以兑换1个黄气球。
    • 现在牛牛有a个红气球，b个黄气球， c个蓝气球，牛牛想知道自己最多可以兑换多少张彩票。

  • 解答：

    • 取出a,b,c三种中最小的值+其他数量
      • 若a=0，则三个黄气球 + 2蓝气球 得 一张彩票 b c
      • 若b=0，则则三个蓝气球 + 2个红气球 得 一张彩票 c a
      • 若c=0, 则则三个红气球 + 2个黄气球 得 一张彩票a b