type
date
status
slug
summary
tags
category
password
icon
😀
 

二分查找

写一个简单的二分算法

好像也没有想象的那么难,之前就是在写二分查找的时候被其中左右两个索引的取值给难倒了,产生了心理阴影哈哈哈:
  • 考虑问题可以先取简单的,特殊的情况,这样能够提前排除很多bug;
 

二维数组二分查找

例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。
notion image

快速幂算法

快速幂基本思想:
  1. 若幂指数为0,则返回结果为1;
  1. 若指数为基数,则返回结果为power(n-1)*base;
  1. 若指数为偶数,则返回结果为power(n/2)^2;
非递归代码如下:

数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第 5 位(从 0 开始计数)是 5,第 13 位是 1,第 19 位是 4,等等。
请写一个函数求任意位对应的数字。

基本思路:

  1. 输入为一个索引index,指向该序列中的某一位
  1. 首先找到index所指位所在数字的位数digit、以digit为位数的数字群的第一个数字start以及index所指位相对该数字群的第一位的偏移量offset;
  1. 根据start以及digit,得到index所指位所在的数字num;
  1. 根据offset和digit,得到index所指位是num的第几位数字;
当然,以上几点都是建立在该问题的内在规律之上的,即所有需要的参量都能够通过一定的逻辑递推得到,规律如下:
数字群
数字的位数(digit)
数字群的开始数字(start)
数字群的总位数(count)
0
1
0
1
1-9
1
1
9
10-99
2
10
9 * 10 * 2
100-999
3
100
9 * 100 * 3
1000-9999
4
1000
9 * 1000 * 4
因此,我们可以总结一下上述的规律,如果不考虑index = 0的情况:
digit = digit + 1 ; start = start * 10 ; count = 9 * start * digit;

把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串:
0 翻译成 a,1 翻译成 b,……,11 翻译成 l,……,25 翻译成 z
一个数字可能有多个翻译。
例如 12258 有 5 种不同的翻译,它们分别是 bccfibwfibczimcfi 和 mzi
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

经典回溯解法

递归解法

我的想法是,如果给我编号为0~i-1的一个字符串,我们可以考虑如下递归算法:
很显然,上述算法是存在重复计算的,因此我们可以使用动态规划的思想;

动态规划

我们可以定义dp[i]为翻译前i个字符的方案总数,显然有如下状态转换:
  1. 如果s[i - 1]满足一起翻译的条件,则状态转移为:dp[i] = dp[i - 2] + dp[i - 1];
  1. 否则,状态转移为:dp[i] = dp[i - 1];
  1. 初始条件:dp[0]为前0个字符的方案总数,我们定义其为1,因为如果前两个字符为12则dp[2] = dp[1] + dp[0],这个值应该为2;

把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如输入数组 [3,32,321],则打印出这 3 个数字能排成的最小数字 321323。

排序

说到排序,我们不得不提的就是全序关系:
若集合X上存在全序关系,那么对任意两个元素a、b,有如下论断:
  • 反对称性:若a ≤ b,b ≥ a,则a == b;
  • 传递性:若a ≤ b,b ≤ c,则a ≤ c;
  • 完全性:要么a ≤ b,要么b ≤ a;
因此一种关系满足≤关系,那么它就可以进行排序。对于该题,我们定义a ≤ b,如果ab ≤ ba(这里后者是小于等于号):
  • 反对称:显然如果ab ≤ ba 且, ba ≤ ab,那么一定有ab == ba;
  • 完全性:显然的;
  • 传递性:若ab ≤ ba,且bc ≤ cb,则一定有:abbc ≤ cbba,即ac ≤ ca
因此,如果我们利用这一关系来对整个序列进行排序,就可以得到一个字典序最小的字符串:

正则表达式匹配

对该问题进行分析:
该问题要求判断,字符串p所表示的正则表达式能否匹配字符串s,能否对这个问题进行划分,划分为更小的子问题进行解决。
其实完全可以给这个正则表达式构造一个自动机来对字符串进行匹配,那么我们就很容易就确定了问题的状态其实就是自动机的状态。但是由于该正则的规则较简单,没有必要小题大做,只要把握住关键的部分就可以了。
我们可以分析一下这个问题的特点,该正则只有*、和.两种元字符,遇到*的时候,其前一个字符可以重复出现,也可以没有,遇到.的时候,可以代替任意的字符。将这个问题一步步划分为更小的问题,如果s的某一前缀能够被p的某一前缀所匹配,那么只需要判断s中所剩后缀能否被p中所剩后缀所匹配就可以了。
所以我们定义两个指针i_si_p分别指向sp,来作为问题的状态,代表i_s到最后的s串能否被i_p到最后的p串所匹配。
在进行状态转换的时候,需要判断当前两个指针所指向的字符的内容:
  • i_p指向一个非*字符,那么比较两个指针内容是否相等;
  • i_p指向一个*字符:
    • i_s指向内容不是i_p - 1处的字符,那么直接跳过*
    • i_s指向内容是i_p - 1处的字符,那么有两种尝试:
      • 认为当前i_s所指内容需要使用该*进行匹配;
      • 认为当前i_s所指内容无需使用该*进行匹配;
  • i_si_p都恰巧等于自身字符串长度的时候,认为匹配成功。
ysyx-learning-notes最后一次学git