面试经典代码题

本文旨在整理面试过程中经典的考题

一、字符串操作

1 字符串转数字(atoi/stoi)

int StrToInt(string str) {
     int len = str.length();
     if (len == 0) return 0;
     int i = 0;
     while (i < len && str[i] == ' ')  ++i;  // 排除开头的空格
     if (i == len) return 0;

     if (!isdigit(str[i]) && str[i] != '+' && str[i] != '-') return 0; //判断第一个符号
     bool neg = str[i]=='-' ? true : false;
     i = isdigit(str[i]) ? i : i+1;
     long long ans = 0L;

     while (i < len && isdigit(str[i])) {
         ans = ans * 10 + (str[i++]-'0');
         if (!neg && ans > INT_MAX) {
             ans = INT_MAX;
             break;
         }
         if (neg && ans > 1L + INT_MAX) {
             ans = 1L + INT_MAX;
             break;
         }
     }
     if (i != len) return 0; // 不要此处，就是atoi()库函数的实现
     return !neg ? static_cast<int>(ans) : static_cast<int>(-ans);
}

2 编程实现strcpy函数

#include <stdio.h>

char* strcpy(char* dest_str,const char src_str){
    if(dest_str==NULL||src_str==NULL)
        return NULL;
    char* strdestCopy = dest_str;
    while((*dest_str++=*src_str++)!='\0');
    return strdestCopy;
}

二、排序

2. 求第k大的数的方法及各自的复杂度

1 首先使用快速排序算法将数组按照从大到小排序，然后取第k个，其时间复杂度最快为O(nlogn)

2 使用堆排序，建立最大堆，然后调整堆，知道获得第k个元素，其时间复杂度为O(n+klogn)

3 首先利用哈希表统计数组中个元素出现的次数，然后利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大的数

利用快排思想，从数组中随机选择一个数i，然后将数组分成两部分$D_l$,$D_r$，$D_l$的元素都小于i,Dr的元素都大于i。然后统计Dr元素个数，如果Dr元素个数等于k-1,那么第k大的数即为k，如果Dr元素个数小于k,那么继续求Dl中第k-Dr大的元素；如果Dr元素个数大于k,那么继续求Dr中第k大的元素。

另外追问一下，当有相同元素时，还可以使用什么不同的方法求第k大的元素

当有相同元素的时候，首先利用哈希表统计数组中个元素出现的次数，然后利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大的数，平均情况下时间复杂度为O(n)

3. Top K问题：海量数据

1. 直接全部排序（只适用于内存够的情况）

当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。

这种方法对数据量比较敏感，当数据量较大的情况下，内存不能完全容纳全部数据，这种方法便不适应了。即使内存能够满足要求，该方法将全部数据都排序了，而题目只要求找出top K个数据，所以该方法并不十分高效，不建议使用。

2. 快速排序的变形 （只使用于内存够的情况）

这是一个基于快速排序的变形，因为第一种方法中说到将所有元素都排序并不十分高效，只需要找出前K个最大的就行。

这种方法类似于快速排序，首先选择一个划分元，将比这个划分元大的元素放到它的前面，比划分元小的元素放到它的后面，此时完成了一趟排序。如果此时这个划分元的序号index刚好等于K，那么这个划分元以及它左边的数，刚好就是前K个最大的元素；如果index > K，那么前K大的数据在index的左边，那么就继续递归的从index-1个数中进行一趟排序；如果index < K，那么再从划分元的右边继续进行排序，直到找到序号index刚好等于K为止。再将前K个数进行排序后，返回Top K个元素。这种方法就避免了对除了Top K个元素以外的数据进行排序所带来的不必要的开销。

3. 最小堆法

这是一种局部淘汰法。先读取前K个数，建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较，如果小于或等于堆顶数据，则继续比较下一个；否则，删除堆顶元素，并将新数据插入堆中，重新调整最小堆。当遍历完全部数据后，最小堆中的数据即为最大的K个数。

4. 分治法

将全部数据分成N份，前提是每份的数据都可以读到内存中进行处理，找到每份数据中最大的K个数。此时剩下NK个数据，如果内存不能容纳NK个数据，则再继续分治处理，分成M份，找出每份数据中最大的K个数，如果M*K个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，那么可以对这些数使用快速排序的变形或者归并排序进行处理。

5. Hash法

如果这些数据中有很多重复的数据，可以先通过hash法，把重复的数去掉。这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间。处理后的数据如果能够读入内存，则可以直接排序；否则可以使用分治法或者最小堆法来处理数据。

详细代码：

1. 利用快速排序的思想进行查找

class Finder {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return quickfind(a,0,n-1,K);
    }
    int quickfind(vector<int> &a,int low,int high,int K){
        int pivot = partition(a,low,high);
        if(pivot+1<K) //中轴位置少于K个，在右子数组中继续查找
            return quickfind(a,pivot+1,high,K);
        else if(pivot+1>K) //中轴位置大于K个，在左子数组中继续查找
            return quickfind( a, low, pivot-1,K);
        return a[pivot];
    }
    int partition(vector<int> &a,int low, int high){
        int val = a[low];
        while(low<high){
            while(low<high&&a[high]<=val) high--;    // 从右往左扫描，直到遇到比基准元素大的元素
            a[low] = a[high];
            while(low<high&&a[low]>=val) low++;    //从左往右扫描，直到遇到比基准元素小的元素
            a[high] = a[low];
        }
        a[low] = val;
        return low;
    }
};

三、链表

1. LRU缓存机制

class LRUCache {
    int capacity;
    list<pair<int,int>> ls;
    unordered_map<int,list<pair<int,int>>::iterator> key_add; //获取数据需要用哈希表 // 见与链表中的地址
    
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        //如果要访问的节点不存在
        if(key_add.find(key)==key_add.end())
            return -1;
        // 把访问的节点移动到最前边的一个；
        pair<int,int> kv = *key_add[key];
        ls.erase(key_add[key]);
        ls.push_front(kv);
        key_add[key] = ls.begin();
        return kv.second;
    }
    
    void put(int key, int value) {
        if(key_add.find(key)==key_add.end()){
            ls.push_front({key,value});
            key_add[key] = ls.begin();

            if(ls.size()>capacity){
                int lastkey = ls.back().first;
                key_add.erase(lastkey);
                ls.pop_back();
            }
        }
        else{
            ls.erase(key_add[key]);
            ls.push_front({key,value});
            key_add[key] = ls.begin();
        }   
    }
};

2. 合并n个有序数组

假设你得到了k个排好序的数组，每个都有n个元素，希望将它们整体组合成一个有着kn个元素的有序数组。考虑以下方法：将k个数组分为k/2对，并使用归并排序来合并每对，则你有了k/2个排序好的数组；重复此方法，直到合并结束。那么程序运行的时间复杂度是O(nklog⁡n)

3. 链表翻转

利用哨兵

Void reversal_list(node * head)
{
     node* pre_node = nullptr;
     node* cur_node = head->next;
     node* next_node = cur_node->next;
     if(cur_node == nullptr) return ;
     while(1)
     {
         cur_node->next = forward_node;
         pre_node = cur_node;
         cur_node = next_node;
         if(cur_node == nullptr)
             break;
        next_node = cur_node->next;
     }
     head->next = pre_node;
}

双指针

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* t = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};

简单的递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};

妖魔化的双指针

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) { return NULL; }
        ListNode* cur = head;
        while (head->next != NULL) {
            ListNode* t = head->next->next;
            head->next->next = cur;
            cur = head->next;
            head->next = t;
        }
        return cur;
    }
};

4. 表示数值的字符串

class Solution {
public:
    bool isNumber(string s) {
        int len = s.length();       
        int i = 0;
        while(i<len&&s[i]==' ') i++; //忽略空格
        bool flag = GetSignedIntBaseNumber(s,len,i);
        if(i<len&&s[i]=='.'){
            i++;
            flag = GetUnSignedIntBaseNumber(s,len,i)||flag;
        }
        if(i<len&&i!=0 && (s[i]=='e'||s[i]=='E')){
            i++;
            flag=flag&&GetSignedIntBaseNumber(s,len,i);
        }
        while(i<len&&s[i]==' ') i++; //忽略空格
        return i>=len&&flag;
    }

    bool GetSignedIntBaseNumber(string &str,int len,int &i){
        if(str[i]=='+'||str[i]=='-')
            i++;
        return GetUnSignedIntBaseNumber(str,len,i);
    }
    bool GetUnSignedIntBaseNumber(string &str,int len,int &i){
        int tmp = i;
        while(i<len&&isdigit(str[i]))
            i++;
        return i>tmp; 
    }
};

5. 删除链表的重复元素

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *root = new ListNode(INT_MAX);
        root -> next = head;
        ListNode *pre = root;
        while(pre&&pre->next){
            ListNode *pcur = pre->next;
            if(pcur->next==nullptr||pcur->next&&pcur->val!=pcur->next->val)
                pre = pcur;
            else{
                while(pcur->next&&pcur->next->val==pcur->val) 
                    pcur = pcur->next;
                pre->next = pcur->next;
            }
        }
        return root -> next;
    }
};

四、回溯

1. N皇后问题

class Solution {
unordered_set<int> columns;
unordered_set<int> diagonals1;
unordered_set<int> diagonals2;
vector<vector<string>> solutions;

public:
    vector<vector<string>> solveNQueens(int n) {
        auto queens = vector<int>(n, -1);
        backtrack(queens, n, 0);
        return solutions;
    }

    void backtrack(vector<int> &queens, int n, int row) {
        if (row == n) {
            vector<string> board = generateBoard(queens, n);
            solutions.push_back(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.find(i) != columns.end()) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.find(diagonal1) != diagonals1.end()) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.find(diagonal2) != diagonals2.end()) {
                    continue;
                }
                queens[row] = i;
                columns.insert(i);
                diagonals1.insert(diagonal1);
                diagonals2.insert(diagonal2);
                backtrack(queens, n, row + 1);
                queens[row] = -1;
                columns.erase(i);
                diagonals1.erase(diagonal1);
                diagonals2.erase(diagonal2);
            }
        }
    }

    vector<string> generateBoard(vector<int> &queens, int n) {
        auto board = vector<string>();
        for (int i = 0; i < n; i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};

五、数字游戏

1 求平方和

int sqrt(int x) {
    // write code here
    int sum = 0;
    for(int i = 0;i<=x;i++){
        int odd = 2*i+1;
        sum+=odd;
        if(sum>x){
            return i;
        }
    }
    return 0;        
}

2 判断一个数是不是二的倍数

a % 2 == 0 或者a & 0x0001 == 0。

3 不用+加减乘除做加法

int Add(int num1, int num2)
{
    int sum,carry;
    do{
        sum = num1^num2;
        carry = (num1&num2)<<1;
        num1 = sum;
        num2 = carry;
    }while(num2!=0);
    return num1;
}

高楼扔鸡蛋

887. 鸡蛋掉落

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

六、计算几何

1. 给定三角形ABC和一点P(x,y,z)，判断点P是否在ABC内

根据面积法，如果P在三角形ABC内，那么三角形ABP的面积+三角形BCP的面积+三角形ACP的面积应该等于三角形ABC的面积。算法如下：

计算三角形面积

#include <iostream>
#include <math.h>
using namespace std;
#define ABS_FLOAT_0 0.0001
struct point_float
{
float x;
float y;
};
float GetTriangleSquar(const point_float pt0, const point_float pt1, const point_float pt2)
{
point_float AB,   BC;
AB.x = pt1.x - pt0.x;
AB.y = pt1.y - pt0.y;
BC.x = pt2.x - pt1.x;
BC.y = pt2.y - pt1.y;
return fabs((AB.x * BC.y - AB.y * BC.x)) / 2.0f;
}
bool IsInTriangle(const point_float A, const point_float B, const point_float C, const point_float D)
{
float SABC, SADB, SBDC, SADC;
SABC = GetTriangleSquar(A, B, C);
SADB = GetTriangleSquar(A, D, B);
SBDC = GetTriangleSquar(B, D, C);
SADC = GetTriangleSquar(A, D, C);
float SumSuqar = SADB + SBDC + SADC;
return ((-ABS_FLOAT_0 < (SABC - SumSuqar)) && ((SABC - SumSuqar) < ABS_FLOAT_0))；
}

七、动态规划

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

题解

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(auto str:strs)
        {
            int zero = 0;
            int one = 0;
            for(int i = 0;i<str.length();i++)
            {
                zero += str[i]=='0'?1:0;
                one  += str[i]=='1'?1:0;
            }
            for(int i = m;i>=zero;i--)
                for(int j = n;j>=one;j--)
                {
                    dp[i][j] = max(dp[i-zero][j-one]+1,dp[i][j]);
                }
        }
        return dp[m][n];
    }
};

打赏