剑指offer算法题(11-20)

剑指offer算法题(03-10)

旋转数组中的最小值-11

排序算法

我的排序算法总结

旋转数组最小值

原有序数组：1,2,3,4,5,6,7，旋转一下，把一部分放到后面去：4,5,6,7, 1,2,3。

求：在$O(logn)$内找到数组中最小的元素

leetcode旋转数组

思路

特点：左边序列全部大于等于右边序列。

最小的值在中间，顺序查找肯定不行，那就只能二分查找了。

设两个指针，left从左边向中间靠拢，right从右边向中间靠拢。

循环条件：a[l] >= a[r]

直到l+1==r 为止，那么a[r]就是我们要的最小值。

计算中间值 a[m]

• a[m] >= a[l] ：m在左边序列，l = m， l向右走
• a[m] <= a[r] ： m在右边序列，r == m， r向左走

陷阱

• 可能一个数字都不旋转，即a为有序序列，直接返回a[0]
• 有重复的数字，a[l]==a[m] && a[m]==[r]， 则只能顺序查找了

关键代码

/*
 * 查找旋转数组中的最小值。两个指针指向前后两个递增序列，向中间靠拢
 */
int minum_rotate_array(const vector<int>& a) {
    
    if (a.size() == 0) {
        return 0;
    }

    int l = 0;
    int r = a.size() - 1;

    // 特殊情况，旋转0个，原数组，小于不能等于
    if (a[l] < a[r]) {
        return a[l];
    }
    int res = -1;

    while (a[l] >= a[r]) {
        // 两个指针已经相邻
        if (l + 1 == r) {
            res = a[r];
            break;
        }
        // 中间指针
        int m = (l + r) / 2;

        // 三个数相等，无法确定中间数在前后那个序列
        if (a[l] == a[m] && a[m] == a[r]) {
            res = get_min(a, l, r);
            break;
        }

        if (a[m] >= a[l]) {
            l = m;
        } else if (a[m] <= a[r]) {
            r = m;
        }
    }

    return res;
}

int get_min(const vector<int>&a, int start, int end) {
    int min = a[start];
    for (int i = start + 1; i <= end; i++) 
        if (a[i] < min) {
            min = a[i];
        }
    return min;
}

矩阵中的路径-12

给一个字符数组，手动给行和列进行分割。再给一个字符串，判断该字符串是否在该字符矩阵中。使用回溯法进行搜索。

其实就是遍历所有的点开始，然后依次进行上下左右继续查找。用visited去记录点是否已经走过，用pathlen记录目标字符串的遍历长度。

[关键代码]

/*
 * 判断str在字符矩阵matrix中是否有路径
 *
 * Args:
 *      matrix -- 字符数组，由rows和cols切分为矩阵
 *      rows -- 行
 *      cols -- 列
 *      str -- 字符串
 * Returns:
 *      true -- 包含，false -- 不包含
 */
bool has_path(const char* matrix, int rows, int cols, const char* str) {
    if (matrix== nullptr || rows < 1 || cols < 1 || str == nullptr) {
        return false;
    }

    bool *visited = new bool[rows * cols];
    memset(visited, 0, rows * cols);

    int pathlen = 0;
    // 从每个点开始
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            bool has = go_find(matrix, rows, cols, row, col, str, pathlen, visited);
            if (has) {
                delete[] visited;
                return true;
            }
        }
    }
    delete[] visited;
    return false;
}

/*
 * 上下左右去回溯查询
 * Args:
 *      matrix -- 字符矩阵
 *      rows -- 矩阵的行数
 *      rows -- 矩阵的列数
 *      row -- 当前要判断的行
 *      col -- 当前要判断的列
 *      str -- 原字符串
 *      pathlen -- 判断到第几个字符
 *      visited -- 位置访问与否
 * Returns:
 *      true -- 
 *      false --
 */
bool go_find(const char* matrix, int rows, int cols, int row, int col, 
                    const char* str, int &pathlen, bool *visited) {

    if (str[pathlen] == '\0') {
        return true;
    }

    bool ok = false;
    int cur = row * cols + col;
    if (row >= 0 && row < rows && col >= 0 && col < cols
        && matrix[cur] == str[pathlen] && visited[cur] == false) {
        ++pathlen;
        visited[cur] = true;
        bool left = go_find(matrix, rows, cols, row, col - 1, str, pathlen, visited);
        bool right = go_find(matrix, rows, cols, row, col + 1, str, pathlen, visited);
        bool down = go_find(matrix, rows, cols, row + 1, col, str, pathlen, visited);
        bool up = go_find(matrix, rows, cols, row - 1, col, str, pathlen, visited);
        ok = left || right || down || up;

        if (!ok) {
            --pathlen;
            visited[cur] = false;
        }
    }
    return ok;
}

机器人的运动范围-13

给一个$\mathrm{r}\mathrm{o}\mathrm{w}\mathrm{s}\times \mathrm{c}\mathrm{o}\mathrm{l}\mathrm{s}$的矩阵，和一个阈值$k$。 机器人从$(0,0)$出发，进入矩阵的格子。

能进入格子：(35, 38)，因为3+5+3+8<k

不能进入格子：(35, 56)，因为3+5+5+5>k

思路

回溯法， $\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}=1+\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}+\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}+\mathrm{u}\mathrm{p}+\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}$

[关键代码]

定义Solution

class Solution {
    private:
        // 阈值
        int threshold;
        // 矩阵行
        int rows;
        // 矩阵列
        int cols;
        // 记录格子有没有被走过
        bool *visited;

    public:
        // 外部接口
        int movingCount(int threshold, int rows, int cols);
        // 回溯计算
        int dfs(int row, int col);
        // 检查该点是否可以进入
        bool check_point(int row, int col);
        // 把各个位的数字加起来
        static int resolve_num(int n);
};

movingcount

/*
 * 在这个矩阵和阈值上，从(0, 0)进入统计能进入多少个格子
 *
 * Args:
 *      threshold -- 各个位的阈值
 *      rows -- 矩阵的行数
 *      cols -- 矩阵的列数
 * Returns:
 *      count -- 可以进入的总的格子数量
 */
int Solution::movingCount(int threshold, int rows, int cols) {
    // 参数校验
    if (threshold < 0 || rows < 1 || cols < 1) {
        return 0;
    }
    // 变量初始化
    this->threshold = threshold;
    this->rows = rows;
    this->cols = cols;
    this->visited = new bool[rows * cols];
    memset(this->visited, 0, rows * cols);
    int count = dfs(0, 0);
    delete[] this->visited;
    return count;
}

回溯法上下左右格子累加

/*
 * 回溯查询
 * Args:
 *      row -- 当前行，索引
 *      col -- 当前列，索引
 * Returns:
 *      count -- 从当前点(row,col)开始向上下左右走能走的格子之和
 */
int Solution::dfs(int row, int col) {
  	// 可以进入该点
    if (check_point(row, col) == false) {
        return 0;
    }
    int cur = row * cols + col;
    visited[cur] = true;
    int left = dfs(row, col - 1);
    int right = dfs(row, col + 1);
    int up = dfs(row - 1, col);
    int down = dfs(row + 1, col);
    int count = 1 + left + right + up + down;
    return count;
}

检查点是否可进入和分解数

/*
 * 把n的各个位上的数加起来
 */
int Solution::resolve_num(int n) {
    int sum = 0;

    while (n > 0) {
        sum += n % 10;
        n = n / 10;
    }
    return sum;
}

/*
 * 检查一个点是否可以进入。索引、访问状态、阈值
 */
bool Solution::check_point(int row, int col) {
    int cur = row * cols + col;
    if (row < 0 || row >= rows || col < 0 || col >= cols || visited[cur] == true) {
        return false;
    }
    if (resolve_num(row) + resolve_num(col) > threshold) {
        return false;
    }
    return true;
}

剪绳子-14

动态规划

求最优解（最大值or最小值），大问题分解成若干个小问题。使用动态规划四个特点，如下

• 求最优解
• 整体问题的最优解依赖于各个子问题的最优解
• 若干个子问题，之间有相互重叠的更小的子问题。如f(2)是f(4)和f(6)共同的子问题
• 从上往下分析问题，从下网上求解问题。用数组存下小问题的解嘛。

贪心算法

每一步做一个贪婪的选择，基于这个选择，可以得到最优解。需要数学证明。

剪绳子-动态规划

条件

长度为$n$的绳子，把绳子剪成$m,(m\ge 2)$段， 每段长度为$k[0],k[1],\cdots ,k[m]$。 m和n都是整数，都大于1。

问题

长度连乘积最大是多少？

思路

定义： $f(n)$ 为把绳子切成若干段后，各段长度乘积的最大值

第一刀的时候，在长度为$i$的地方剪，分成$i$和$n-i$两段。 递推公式如下：

$$f(n)=max(f(i)\cdot f(n-i)),0<i<n$$

// 自下而上计算f[i]

// 计算单个f[i]
int max = 0;
for (int j = 1; j <= i / 2; j++) {
  int t = f[j] * f[i - j];
  if (t > max) {
    max = t;
  }
} 
f[i] = max;

关键代码

• 长度在3以内的特殊返回
• 构建f[i]，f[0,1,2,3]手动赋值处理，意义不同
• 自下而上计算f[4, ..., length]
• 单独计算f[i]，找到$max(f_j\cdot f_{i-j})$， 其中$j\in \{1,\cdots ,i/2\}$

int max_product_dp(int length) {
    // 1. 特殊处理，长度在3以内，自动返回
    if (length <= 1) {
        return 0;
    } else if (length == 2) {
        return 1;
    } else if (length == 3) {
        return 2;
    }

    // 2. f[i]=k，长度为i的绳子剪成若干段最大乘积为k，i>=4
    int * f = new int[length + 1];

    // 3. f[i]特殊值处理。比如4切一刀：1-3和2-2，f[1]=1,f[3]=3, f[2]=2。因为2*2>1*3，f[4]=4
    f[0] = 0;
    f[1] = 1;
    f[2] = 2;
    f[3] = 3;

    int max = 0;
    // 4. 自下而上计算
    for (int i = 4; i <= length; i++) {
        max = 0;
        // 找最大的分割
        for (int j = 1; j <= i / 2; j++) {
            int t = f[j] * f[i - j];
            if (t > max) {
                max = t;
            }
        }
        f[i] = max;
    }

    max = f[length];
    delete[] f;

    return max;
}

剪绳子-贪心

贪心策略

• 当$n\ge 5$时， 尽可能多地剪成长度为3的绳子
• 当剩余长度为4的时候，要剪成2*2的绳子

关键代码

1. 特殊处理，长度在3以内，自动返回
2. 计算3的个数
3. 计算2的个数
4. 计算最终结果 pow(3, t3)*pow(2,t2)

int max_product_greedy(int length) {
    // 1. 特殊处理，长度在3以内，自动返回
    if (length <= 1) {
        return 0;
    } else if (length == 2) {
        return 1;
    } else if (length == 3) {
        return 2;
    } else if (length == 4) {
        return 4;
    }

    // 2. 计算3的个数
    int t3 = length / 3;
    // 最后剩1，则补成4
    if (length - t3*3 == 1) {
        t3--;
    }

    // 3. 计算2的个数
    int t2 = (length - t3*3) / 2;

    // 4. 计算最终结果 
    return (int) pow(3, t3) * (int) (pow(2, t2));
}

二进制中1的个数-15

基础知识

位运算

操作	意义
与&	都为1，才为1
或|	有一个为1，就为1
异或^	不同为1，相同为0

移位

操作	意义	注意
左移n位	丢弃左边n位，右边n位补0
右移n位	无符号数&正数：右移n位，左边补n个0	负数：右移n位，左边补n个1

重要结论

操作	意义
n & (n-1)	把n的二进制中，最右边的1变成0
n & 1	检测n的二进制，末尾位是否是1
n & 2	检测n的二进制，倒数第二位是否是1

二进制中1的个数

问题：给一个整数，判断它的二进制中，有多少个1

正数思路

n & 1，n不停右移。每次判断 n & 1，即最末尾位是否是1。

但是负数有问题，负数右移，左边会补1，陷入死循环。

正数负数思路

n不变，n & flag，flag每次向左移。即从右到左依次判断n的各个位是否是1。一共循环n的二进制位数次。

最优思路

n = n & (n - 1)，每次把n的最右边的1变成0。看看能执行多少次这样的操作，就有多少个1。

关键代码

/*
 * flag不断左移
 */
int count_1_by_flag(int n) {
    int count = 0;
    unsigned int flag = 1;
    while (flag != 0) {
        if (n & flag) {
            count++;
        }
        flag = flag << 1;
    }
    return count;
}


/*
 * 把n的最左边1变成0，看看能变几次，则有几个1
 */
int count_1(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

数值的整数次方-16

代码风格

代码的规范性：清晰的书写、清晰的布局、合理的命名

代码的完整性：功能测试、边界测试、负面测试

处理错误的方法

方法	优点	缺点
返回值	和系统API一致	不能方便使用计算结果
全局变量	能够方便使用计算结果	用户可能会忘记检查全局变量
异常	不同错误，抛出不同异常，可自定义。逻辑清晰	有的语言不支持；对性能负面影响

数值的整数次方

要求实现

double power(double base, int exponent);

注意特殊情况条件

• 指数为0
• 指数为负数
• 指数为负数，底数不能为0或者约等于0。用fabs(a-b) < theta

思路1

条件考虑全面，一个一个乘

思路2递归

使用这个公式

$$a^n=\{\begin{array}{lll}& a^{n/2}\cdot a^{n/2}& \text{n为偶数}\\ & a^{(n-1)/2}\cdot a^{(n-1)/2}& \text{n为奇数}\end{array}$$

思路3位运算

例如$a^{13}$， 13的二进制是1101。

从右向左，依次读1，flag & 1, b = b >> 1

遇到1就累乘， res *= a

每读一位，倍数增加， a *= a

关键代码

double power_normal_binary(double base, int exponent) {
    if (exponent == 0) {
        return 1;
    } else if (exponent == 1) {
        return base;
    }
    double res = 1;
    while (exponent != 0) {
        if ((exponent & 1) == 1) {
            res *= base;
        }
        base *= base;
        exponent = exponent >> 1;
    }
    return res;
}


/*
 * 递归计算
 */
double power_normal_recur(double base, int exponent) {
    if (exponent == 0) {
        return 1;
    } else if (exponent == 1) {
        return base;
    }

    double res = power_normal_recur(base, exponent >> 1);
    // 翻次方倍
    res *= res;

    // 奇数
    if ((exponent & 1) == 1) {
        res *= base;
    }
    return res;
}


double power_normal(double base, int exponent) {
    double res = 1;
    for (int i = 0; i < exponent; i++) {
        res *= base;
    }
    return res;
}


double power(double base, int exponent) {
    // 指数为0，返回1
    if (exponent == 0) {
        return 1;
    }
    // 指数为负数，底数不能为0
    if (exponent < 0 && equal(base, 0.0)) {
        cout << "error. exponent < 0, base should != 0" << endl;
        return 0;
    }
    // 分正负计算
    double res = 1;
    if (exponent > 0) {
        res = power_normal_binary(base, exponent);
    } else {
        res = power_normal_binary(base, -exponent);
        res = 1.0 / res;
    }
    return res;
}

打印1到最大的N位数-17

问题：输出打印1-999。但是n不确定，非常大，要注意溢出的问题。

思路

• 开辟n+1位的字符串，来存储数字。末尾位是'\0'
• 字符串模拟数字的自增、进位和溢出
• 长度超过n+1，或者第0位产生进位，则溢出
• 输出的时候，要人性化点。比如0087，要打印87

关键代码

开始的时候，个位加1。要注意进位， 清楚当前数字存在哪些位置上面的。

/*
 * 当前数加1，字符串模拟加法、进位、溢出
 */
void Solution::increment() {
    // 当前位的值
    int now = -1;
    // 前一位的进位
    int take = 0;
    int i = -1;
    // 当前位数是n-1~n-real_len
    for (i = n - 1; i >= n - real_len; i--) {
        int now = num[i] - '0' + take;
        if (i == n - 1) {
            // 实现自增，末尾加1
            now = now + 1;
        }
        if (now >= 10) {
            num[i] = '0' + (now - 10);
            take = 1;
        } else {
            num[i] = '0' + now;
            take = 0;
            break;
        }
    }
    
    // 需要新增一位
    if (take > 0) {
        if (i < 0) {
            cout << "num char* over flow" << endl;
            this->over_flow = true;
            // 注意释放空间
            delete this->num;
            return;
        }
        num[i] = '0' + 1;
        real_len++;
    }
    return;
}

删除链表中的元素-18

删除一个节点

给一个链表和一个节点，删除这个节点i，要求$O(1)$

思路

从头到尾遍历找到i的前驱节点，时间复杂度为$O(n)$， 显然不行。

把i的后继节点的值拷贝到i上，然后删除i的后继节点。

但，要注意：头结点、中间节点、末尾节点（顺序遍历）。

关键代码

void delete_node(ListNode ** phead, ListNode* pdeleted) {
    if (!phead || !pdeleted) {
        return;
    }
    // 只有一个节点，删除头节点/尾节点
    if (*phead == pdeleted && pdeleted->next == nullptr) {
        delete pdeleted;
        pdeleted = nullptr;
        *phead = nullptr;
    }
    // 有多个节点，删除尾节点
    else if (pdeleted->next == nullptr) {
        ListNode* p = *phead;
        while (p->next != pdeleted) {
            p = p->next;
        }
        p->next = nullptr;
        delete pdeleted;
        pdeleted = nullptr;
    }
    // 有多个节点，删除中间的节点
    else {
        // 直接把下一个节点的值赋值到当前节点，再删除下一个节点
        ListNode* pnext = pdeleted->next;
        pdeleted->val = pnext->val;
        pdeleted->next = pnext->next;
        delete pnext;
        pnext = nullptr;
    }
}

删除有序链表中的重复元素

Remove Duplicates from Sorted List 有序的链表。

留下一个

每个重复的元素，留下一个。

思路

从head开始循环，遍历每一个节点。

对于当前节点c，再进行遍历，直到下一个节点不等于它或者为空。中间删除掉重复的节点。

全部删除

把所有重复的元素，都删除，有序链表。

思路

当前节点cur， 需要保留前一个元素的指针pre。

我的思路

循环遍历到cur，head应该为第一个pre。

• cur无重复cur!=next || next==null
  • pre为空，则pre=cur ； pre不为空， 则pre.next=cur ，pre=pre.next 。实际上pre.next指向下一轮的cur
• cur重复 cur=next
  • 遍历删除所有与cur相同的元素
  • 删除cur
  • 但由于原本pre.next指向当前cur，cur又被删除。所以pre.next=nullptr

其实最重要是：当前不重复，则续接到pre后面，pre后移；当前重复，则删除，pre后面设为空。

关键代码

ListNode* del_dups_nosave(ListNode* head) {
    if (head == nullptr) {
        return head;
    }
    ListNode* cur = head;
    ListNode* pre = nullptr;
    ListNode* next = nullptr;
    while (cur) {
        // 1. cur无重复
        if (cur->next == nullptr || cur->val != cur->next->val) {
            if (pre == nullptr) {
                pre = cur;
                head = pre;
            } else {
                pre->next = cur;
                pre = cur;
            }
            cur = cur->next;
        }
        // 2. cur重复，删掉重复的元素
        else {
            next = cur->next;
            // 2.1 删除与cur相同的
            while (next && cur->val == next->val) {
                cur->next = next->next;
                delete next;
                next = cur->next;
            }
            // 2.2 删除cur
            delete cur;
            cur = next;
            // 原本pre->next=cur，但是当前cur已经被删除，所以重新置为空
            if (pre != nullptr)
                pre->next = nullptr;
        }
    }
    if (pre == nullptr) {
        head = nullptr;
    }
    return head;
}

正则表达式匹配-19

问题

正则表达式：普通字符、. 任意字符 、* 前面的字符出现0次或多次。

给定字符串，去判断该字符串是否符合正则表达式。

例如：aaa 与a.a和ab*ac*a匹配， 与aa.a和ab*a不匹配。

思路

递归去判断。用$s_1$和$p_1$去 代表第一个字符和第一个模式。

$s_1$与$p_1$匹配成功： s1==p1 || (p1 == '.' && s1 != '\0')

必须先判断$p2$是否是*

如果，第二个模式$p_2$是*

• $s_1$与$p_1$匹配成功
  • *代表出现1次，go(s2, p3)
  • *代表出现0次，go(s1, p3)
  • *代表出现多次，go(s2, p1)
• $s_1$与$p_1$匹配失败
  • *只能代表出现0次，go(s1, p3)

如果$s_1$与$p_1$匹配成功

• 字符串和模式都向后挪一次，go(s2, p2)

总结

1. p结束，s结束。返回true
2. p结束，s还有。 返回false
3. p未结束，$p_2$ == *。$s_1$与$p_1$匹配成功， p2作为0、1、多次，合并返回。匹配失败，作为0次，返回。
4. p未结束，$p_2$ != *，单独match成功。go(s2, p2)
5. p未结束，$p_2$ != *，单独match失败。返回false

关键代码

/*
 * 单个字符是否能匹配
 */
bool single_char_match(const string &str, int s, const string &pattern, int p) {
    // 超出
    if (s >= str.size() || p >= pattern.size()) {
        return false;
    }
    // 匹配成功
    if (str[s] ==  pattern[p] || (pattern[p] == '.' && s < str.size())) {
        return true;
    }
    // 匹配失败
    return false;
}

/*
 * 递归判断str和pattern是否匹配，从snow和pbgin开始
 * Args:
 *      str -- 字符串
 *      snow -- 从字符串的第几个开始
 *      pattern -- 正则表达式
 *      pnow -- 模式的开始
 * Returns:
 *      true or false
 */
bool match_core(const string &str, int snow, const string &pattern, int pnow) {
    // 1. p结束，s结束
    if (pnow >= pattern.size() && snow >= str.size()) {
        return true;
    }

    // 2. p结束，s还有
    if (pnow >= pattern.size() && snow < str.size()) {
        return false;
    }

    // 3. p未结束，p2 == *
    int p2 = pnow + 1;
    if (p2 < pattern.size() && pattern[p2] == '*') {
        // s1与p1匹配成功
        if (single_char_match(str, snow, pattern, pnow) == true) {
            bool t0 = match_core(str, snow, pattern, pnow + 2);
            bool t1 = match_core(str, snow+1, pattern, pnow + 2);
            bool t_many = match_core(str, snow+1, pattern, pnow);
            return t0 || t1 || t_many;
        }
        // s1与p1匹配失败
        else {
            // *只能代表0
            return match_core(str, snow, pattern, pnow + 2);
        }
    }
    // 4. p未结束，p2 != *，单独match成功
    if (single_char_match(str, snow, pattern, pnow) == true) {
        return match_core(str, snow+1, pattern, pnow+1);
    }

    // 5. p未结束，p2 != *，单独match失败
    return false;
}

表示数值的字符串-20

数值：+100、5e2、-123、3.1416、-1E-16 、1.5e2

非数值：12e、1a3.14、1.2.3、+-5、12e+5.4

判断字符串是否是一个正确的数值。A[.[B]][e|EC]或者.B[e|EC]

（符号）、整数、小数点、（整数）、e、整数

• 小数点前后，必须有一个整数
• e前面是一个数，后面是一个整数

关键代码

bool Solution::isNumeric(const string &str) {
    int start = 0;
    bool pre_int = scan_integer(str, start);
    bool numeric = pre_int;
    // 有小数点
    if (start < str.size() && str[start] == '.') {
        start++;
        bool dot_int = scan_unsigned_integer(str, start);
        // 小数点前面或者后面至少有一个整数
        numeric = pre_int || dot_int;
    } 

    // 有指数符号
    if (start < str.size() && (str[start] == 'E' ||str[start] == 'e')) {
        start++;
        bool e_int = scan_integer(str, start);
        // e前面是一个数值，e后面是一个整数
        numeric = numeric && e_int;
    }
    // 没有走完，还剩余字符
    if (start < str.size()) {
        return false;
    }
    return numeric;
}