首页Computer-ScienceCoding-Interviews

# 面试题 16：数值的整数次方

# 题目

实现函数 double_power(double base,int exponent) ，求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题。

# 思路

本题的直接思路是通过循环不断计算乘法，直到算出最终的结果。

需要注意的是， exponent 有可能为负数的情况，此时需要先取其绝对值，最后返回计算值的倒数。对于其他的特殊输入，如底数为 00 的情形，也需要特殊考虑。对于无效输入，使用 g_INVALID_INPUT 这个全局变量作为标识。

更高效的做法是使用快速幂的思想，利用如下公式求解 aa 的 nn 次方：

an={an/2⋅an/2,n 为偶数;a(n−1)/2⋅a(n−1)/2⋅a,n 为奇数a^n = \begin{cases} a^{n/2} \cdot a^{n/2}, & n \text{ 为偶数};\\ a^{(n-1)/2} \cdot a^{(n-1)/2} \cdot a, & n \text{ 为奇数} \end{cases}

# 代码

#include <iostream>
#include <cmath>
using namespace std;
double double_power(double base, unsigned int exponent) {
    if (exponent == 0) {
        return 1;
    }
    if (exponent == 1) {
        return base;
    }
    double result = 1;
    while (exponent) {
        if (exponent & 1) { //exponent 的二进制最后一位为 1
            result *= base;
        }
        base *= base;
        exponent >>= 1;
    }
    return result;
}
bool g_INVALID_INPUT = false;
double double_power(double base, int exponent) {
    g_INVALID_INPUT = false;
    if (abs(base - 0.0) <= 1e-6 && exponent < 0) {
        g_INVALID_INPUT = true;
        return 0.0;
    }
    unsigned int abs_exponent = (unsigned int)exponent;
    if (exponent < 0) {
        abs_exponent = (unsigned int)(-exponent);
    }
    double result = power_with_unsigned_exponent(base, abs_exponent);
    if (exponent < 0) {
        result = 1.0 / result;
    }
    return result;
}
# 面试题 17：打印从 11 到最大的 nn 位数


# 题目


输入数字 nn，按顺序打印出从 11 到最大的 nn 位十进制数。比如输入 33，则打印出 11、22、33 一直到最大的 33 位数 999999。


# 思路


对于输入的 nn 较小的情况，可以直接计算 10n10^n，然后通过循环输出。但是对于 nn 较大的情形，会遇到数字溢出的情形。因此需要使用字符或者数组来表示大整数，通过逐次对大整数自增 11 的操作，不断输出整数。


另一种方法是通过全排列的思想，将 nn 位数视作 00~99 的全排列，依次输出每个整数。


# 代码


#include <iostream>
#include <string>
using namespace std;
void print_number(string &number) {
    int begin_index = 0;
    for (int i = 0; i < number.size(); ++i) {
        if (number[i] != '0') {
            begin_index = i;
            break;
        }
    }
    cout << number.substr(begin_index) << endl;
}
bool increment(string &number) {
    bool is_overflow = false;
    int carry = 0;
    for (int i = number.size() - 1; i >= 0; --i) {
        int sum = number[i] - '0' + carry;
        if (i == number.size() - 1) {
            ++sum;
        }
        if (sum >= 10) {
            if (i == 0) {
                is_overflow = true;
            } else {
                sum -= 10;
                carry = 1;
                number[i] = '0' + sum;
            }
        } else {
            number[i] = '0' + sum;
            break;
        }
    }
    return is_overflow;
}
void print_to_max_of_n_digits(int n) {
    if (n <= 0) {
        return;
    }
    string number(n, '0');
    while (!increment(number)) {
        print_number(number);
    }
}
递归解法


#include <iostream>
#include <string>
using namespace std;
void print_number(string &number) {
    int begin_index = 0;
    for (int i = 0; i < number.size(); ++i) {
        if (number[i] != '0') {
            begin_index = i;
            break;
        }
    }
    cout << number.substr(begin_index) << endl;
}
void print_number_recursively(string &number, int index) {
    if (index == number.size()) {
        print_number(number);
        return;
    }
    for (int i = 0; i < 10; ++i) {
        number[index] = '0' + i;
        print_number_recursively(number, index + 1);
    }
}
void print_to_max_of_n_digits(int n) {
    if (n <= 0) {
        return;
    }
    string number(n, '0');
    print_number_recursively(number, 0);
}
# 面试题 18：删除链表的节点


# 题目一：在 O(1)O(1) 时间内删除链表节点


给定单向链表的头指针和一个节点指针，定义一个函数在 O(1)O(1) 时间内删除该节点。链表节点与函数的定义如下：


struct ListNode {
    int m_value;
    ListNode *m_next;
};
# 思路


删除链表中节点的通常做法是遍历链表，找到目标节点后删除。但是本题中要求的时间复杂度是 O(1)O(1)，因此不能通过遍历的方式进行查找。


本题中给定了要被删除的节点，如果我们按照通常的做法，还需要找到该节点的前一个节点，这在单链表中是无法在 O(1)O(1) 时间内做到的。因此通常的删除节点，修改指针的办法在本题中是行不通的。


我们可以换一种做法，对于被删除的节点，我们可以很快的找到它的下一个节点，那么我们可以将下一个节点的内容复制到本节点，然后删除下一个节点，如此一来，便可以在 O(1)O(1) 时间内做到删除链表节点（对于更复杂的结构体，可能无法满足 O(1)O(1) 的时间复杂度要求）。而对于最后的尾节点，则不得不遍历链表，寻找它的前一个节点。


综上，对于 n−1n-1 个非尾节点，可以在 O(1)O(1) 时间内删除，而对于尾节点，时间复杂度是 O(n)O(n)，总的时间复杂度是 1n[(n−1)∗O(1)+(n)]\frac{1}{n}[(n-1)*O(1)+(n)]，仍然满足 O(1)O(1) 的要求。


# 代码


#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
};
void delete_node(ListNode **head, ListNode **to_be_deleted) {
    if (*head == nullptr || *to_be_deleted == nullptr) {
        return;
    }
    ListNode *node_deleted = *to_be_deleted;
    if (node_deleted->m_next != nullptr) { // 非尾节点
        ListNode *next = node_deleted->m_next;
        node_deleted->m_value = next->m_value;
        node_deleted->m_next = next->m_next;
        delete next;
        next = nullptr;
        *to_be_deleted = nullptr;
    } else {
        if (*head == node_deleted) {
            delete node_deleted;
            *head = nullptr;
        } else {
            ListNode *node = *head;
            while (node->m_next != node_deleted) {
                node = node->m_next;
            }
            node->m_next = nullptr;
            delete *to_be_deleted;
            *to_be_deleted = nullptr;
        }
    }
}
#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
};
void delete_node(ListNode *head, ListNode *to_be_deleted) {
    if (head == nullptr || to_be_deleted == nullptr) {
        return;
    }
    if (to_be_deleted->m_next != nullptr) { // 非尾节点
        ListNode *next = to_be_deleted->m_next;
        to_be_deleted->m_value = next->m_value;
        to_be_deleted->m_next = next->m_next;
        delete next;
        next = nullptr;
    } else {
        if (head == to_be_deleted) {
            delete to_be_deleted;
            head = nullptr;
        } else {
            ListNode *node = head;
            while (node->m_next != to_be_deleted) {
                node = node->m_next;
            }
            node->m_next = nullptr;
            delete to_be_deleted;
        }
    }
}
# 题目二：删除链表中重复的节点


删除一个有序链表中值重复的节点。例如，对于链表 {1,2,3,3,5}\{1,2,3,3,5\}，删除重复的节点 33 后，变成了 {1,2,5}\{1,2,5\}。


# 思路


在遍历链表的过程中，应当使用双指针  prev  和  cur ，当  cur  和  cur->m_next  指向的节点值重复时，停止  prev  的移动，让  cur  继续查找相同值，直到找到最后一个重复的节点，将  prev->m_next  到  cur  的节点全部删除。之后继续遍历链表，直到删除所有重复的节点。


# 代码


#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
    ListNode(int val, ListNode *ptr = nullptr): m_value(val), m_next(ptr) {}
};
void delete_duplicate_node(ListNode **head) {
    if (head == nullptr) {
        return;
    }
    ListNode dummy(-1, *head);
    ListNode *prev = &dummy;
    ListNode *cur = *head;
    while (cur != nullptr) {
        while (cur->m_next && cur->m_next->m_value == cur->m_value) {
            cur = cur->m_next;
        }
        if (prev->m_next != cur) {
            ListNode *tmp = prev->m_next;
            prev->m_next = cur->m_next;
            cur->m_next = nullptr;
            cur = prev->m_next;
            // delete nodes from tmp to cur
            while (tmp != nullptr) {
                ListNode *node = tmp;
                tmp = tmp->m_next;
                delete node;
            }
        } else {
            prev = cur;
            cur = cur->m_next;
        }
    }
    *head = dummy.m_next;
}
# 面试题 19：正则表达式匹配


# 题目


请实现一个函数用来匹配包含  .  和  *  的正则表达式。模式中的字符  .  表示任意一个字符，而  *  表示它前面的字符可以出现任意次（含 00 次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串  aaa  与模式  a.a  和  ab*ac*a  匹配，但与  aa.a  和  ab*a  均不匹配。


# 思路


正则表达式最容易理解的解决方法是通过有限状态机来实现。


finite_state_machine


# 代码


#include <iostream>
#include <string>
using namespace std;
bool match_core(const string &str, int str_idx, const string &pattern, int pattern_idx) {
    int str_len = str.size();
    int pattern_len = pattern.size();
    if (str_idx == str_len && pattern_idx == pattern_len) {
        return true;
    }
    if (str_idx != str_len && pattern_idx == pattern_len) {
        return false;
    }
    if (pattern_idx + 1 < pattern_len && pattern[pattern_idx + 1] == '*') {
        if (pattern[pattern_idx] == str[str_idx] || pattern[pattern_idx] == '.') {
            return match_core(str, str_idx + 1, pattern, pattern_idx + 2) ||    // move to next state
                   match_core(str, str_idx + 1, pattern, pattern_idx) ||    // stay on current state
                   match_core(str, str_idx, pattern, pattern_idx + 2);  // ignore a '*'
        } else {
            return match_core(str, str_idx, pattern, pattern_idx + 2);  // ignore a '*'
        }
    }
    if (str[str_idx] == pattern[pattern_idx] || pattern[pattern_idx] == '.') {
        return match_core(str, str_idx + 1, pattern, pattern_idx + 1);
    }
    return false;
}
bool match(const string &str, const string &pattern) {
    if (str.empty() || pattern.empty()) {
        return false;
    }
    return match_core(str, 0, pattern, 0);
}
# 面试题 20：表示数值的字符串


# 题目


请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串  "+100" 、 "5e2" 、 "-123" 、 "3.1416"  及  "-1E-16"  都表示数值，但  "12e" 、 "1a3.14" 、 "1.2.3" 、 "+-5"  及  "12e+5.4"  都不是。


# 思路


表示数值的字符串遵循  A[.[B]][e|EC]  或者  .B[e|EC]  的模式，其中  A  为数值的整数部分， B  为紧跟着小数点的小数部分， C  为紧跟着  e  或者  E  的指数部分。当整数部分为 00 时，小数可能会省略掉其整数部分，如 0.1230.123 写成 .123.123，即  A  在某些时候是不必要的。


其中  A  和  C  可能以  +  或者  -  开头， B  的前面不能有正负号。


# 代码


#include <iostream>
#include <string>
using namespace std;
bool scan_unsigned_integer(const string &str, int &index) {
    int original_index = index;
    while (index < str.size() && str[index] >= '0' && str[index] <= '9') {
        ++index;
    }
    return index > original_index;
}
bool scan_integer(const string &str, int &index) {
    if (index < str.size() && (str[index] == '+' || str[index] == '-')) {
        ++index;
    }
    return scan_unsigned_integer(str, index);
}
bool is_numeric(const string &str) {
    if (str.empty()) {
        return false;
    }
    int index = 0;
    bool numeric = scan_integer(str, index);
    if (index < str.size() && str[index] == '.') { // 包含小数部分
        ++index;
        // 使用 || 的原因
        // 1. 小数可以没有整数部分
        // 2. 小数点后面可以没有数字
        // 3. 小数点前面和后面可以都有数字
        numeric = scan_unsigned_integer(str, index) || numeric;
    }
    if (index < str.size() && (str[index] == 'e' || str[index] == 'E')) {
        ++index;
        // 使用 && 的原因
        // 1. 当 e 或者 E 前面没有数字时，整个字符串不能表示数字
        // 2. 当 e 或者 E 后面没有数字时，整个字符串不能表示数字
        numeric = numeric && scan_integer(str, index);
    }
    return numeric && index == str.size();
}
# 面试题：调整数组顺序使奇数位于偶数前面


# 题目


输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。


# 思路


利用双指针  left  和  right ， left  先正向遍历，当发现指向的数字不是奇数时，和  right  指针指向的内容进行交换，此时换为  right  指针反向遍历。当  right  指针指向的数字不是偶数时，和  left  指针指向的内容进行交换，换为  left  指针继续正向遍历。重复上述过程直到  left  和  right  指针指向相同的内容。


# 代码


#include <iostream>
#include <vector>
using namespace std;
bool is_even(int n) {
    return (n & 1) == 0;
}
void reorder(vector<int> &data, bool (*func)(int)) {
    if (data.empty()) {
        return;
    }
    int left = 0, right = data.size() - 1;
    while (left < right) {
        while (left < right && (func(data[left]) == false)) {
            ++left;
        }
        while (left < right && func(data[right])) {
            --right;
        }
        if (left < right) {
            swap(data[left], data[right]);
        }
    }
}