头像

我要出去乱说

贵州大学 大数据与信息工程学院




离线:3小时前



笔试面试高频题。力扣上也有道原题:70. 爬楼梯,但是用斐波那契递归会超时,只能用方法一。

滚动数组递推解法:

时间复杂度 :$O(N)$

空间复杂度 :$O(1)$

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; i ++ )
    {
        p = q;      //每次循环中p表示跳到第i-2级台阶的方案数
        q = r;      //q表示跳到第i-1级台阶的方案数
        r = p + q;  //r表示跳到第i级台阶的方案数
    }

    cout << r << endl;

    return 0;
}

斐波那契递归解法:

时间复杂度 :$O(N)$

空间复杂度 :$O(N)$

#include <iostream>

using namespace std;

int ans = 0, n;

int f(int k)    //其实就是斐波那契数列,因为要跳到第n级台阶,必须从n-1或n-2级台阶起跳
                //那么跳到第n级台阶的方案就等于跳到第n-1级台阶的方案加跳到第n-2级台阶的方案,即斐波那契数列
{
    if (k == n) ans ++ ;
    else if (k < n)
    {
        f(k + 1);
        f(k + 2);
    }
}

int main()
{
    cin >> n;

    f(0);

    cout << ans << endl;

    return 0;
}



哈希法:
时间复杂度 : $O(N)$
空间复杂度 : $O(N)$

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        unordered_map <int, bool> hash;

        for (int x : nums)
            if (x < 0 || x >= nums.size())
                return -1;

        for (int x : nums)
        {
            if (hash[x]) return x;
            hash[x] = true;
        }

        return -1;
    }
};

原地交换法:
时间复杂度 : $O(N)$
空间复杂度 : $O(1)$

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();

        for (int x : nums)
            if (x < 0 || x >= n) return -1;

        for (int i = 0; i < n; i ++ )
        {
            while (nums[nums[i]] != nums[i]) swap(nums[nums[i]], nums[i]);
            if (nums[i] != i) return nums[i];
        }

        return -1;
    }
};



思路:从矩阵右上角开始遍历,若每行末尾的值小于target,则该行全小于target,移动到下一行。直到行末元素大于target,则target必在该行或不存在矩阵中。

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.empty() || array[0].empty()) return false;

        int n = array.size(), m = array[0].size();
        int i = 0, j = m - 1;                       //从右上角开始

        while (i < n && j >= 0)
        {
            if (array[i][j] == target) return true; //每行末尾的值小于target,则该行全小于target
            else if (array[i][j] < target) i ++ ;   //该行末尾值大于target,则target只能在该行
            else j -- ;
        }

        return false;
    }
};



题目描述

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
在 $O(nlogn)$ 时间复杂度和常数级空间复杂度下,对链表进行排序。

样例

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

迭代归并排序

时间复杂度 : $O(nlogn)$

空间复杂度 : $O(1)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;

        int len = 0;
        auto node = head;

        while (node) node = node->next, len ++ ;            //遍历得出链表长度

        auto dummy = new ListNode(0, head);
        for (int sublen = 1; sublen < len; sublen <<= 1)    //子链表长度每次翻倍,这层循环复杂度为O(logN)
        {
            auto pre = dummy, cur = dummy->next;
            while (cur)                     //这层循环复杂度为O(N),故总时间复杂度为O(NlogN)
            {
                auto head1 = cur;           //定义第一段头节点
                for (int i = 1; i < sublen && cur->next; i ++ )
                    cur = cur->next;        //得到第一段尾节点

                auto head2 = cur->next;     //定义第二段头节点
                cur->next = NULL;           //切掉第一段

                cur = head2;                //开始找第二段尾节点
                for (int i = 1; i < sublen && cur && cur->next; i ++ )
                    cur = cur->next;

                ListNode* next = NULL;
                if (cur)
                {
                    next = cur->next;       //标记第三段(下一次循环的第一段)的起始节点
                    cur->next = NULL;       //切掉第二段
                }

                ListNode* merged = merge(head1, head2);     //合并当前两段

                pre->next = merged;                         //pre用来连接合并后的段
                while (pre->next) pre = pre->next;          

                cur = next;                                 //开始第三段
            }
        }

        return dummy->next;
    }

    ListNode* merge(ListNode* l1, ListNode* l2)     //两个有序链表合并模板
    {
        auto dummy = new ListNode(-1), p = dummy;

        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                p = p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p = p->next = l2;
                l2 = l2->next;
            }
        }

        if (l1) p->next = l1;
        if (l2) p->next = l2;

        return dummy->next;
    }
};



琢磨了半天,一看题解,我人傻了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void mirror(TreeNode* root) {
        if (!root) return;

        swap(root->left, root->right);  //这里交换的是指针,不是结构体

        mirror(root->left);
        mirror(root->right);
    }
};



堆就是完全二叉树,且根节点的值一定大于或者小于其他所有节点(取决于大根堆或小根堆),完全二叉树上面的节点都是满的,最后一层的节点从左到右排列。

QQ截图20210226182825.png

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m, len;
int heap[N];

void down(int u)
{
    int t = u;

    //左儿子存在且左儿子小于父节点,则父节点下沉
    if (u * 2 <= len && heap[u * 2] < heap[t]) t = 2 * u;
    //右儿子存在且右儿子小于父节点,则父节点下沉
    if (u * 2 + 1 <= len && heap[u * 2 + 1] < heap[t]) t = 2 * u + 1;

    if (u != t)
    {
        swap(heap[u], heap[t]);
        down(t);                    //继续下沉,沉到不能沉为止
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> heap[i];
    len = n;

    //最底部先垫一层,再插入,一边插入一遍排序。最底部一层元素数量为总元素的二分之一
    for (int i = n / 2; i; i -- ) down(i);

    while (m -- )
    {
        cout << heap[1] << ' ';
        heap[1] = heap[len -- ];    //删除堆顶最小值
        down(1);
    }

    return 0;
}



这种题就是找规律

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int a[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> a[i][j];

    for (int j = m - 1; ~j; j -- )      //在输出上做文章
    {
        for (int i = 0; i < n; i ++ )
            cout << a[i][j] << ' ';
        puts("");
    }
}



镜像:左子树左边与右子树右边相等,左子树右边与右子树左边相等。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode* l, TreeNode* r)
    {
        if (!l && !r) return true;          //两节点都为空
        else if (!l || !r) return false;    //其中一节点为空

        if (l->val != r->val) return false; //两节点值不相等

        //镜像,左子树左边与右子树右边比,左子树右边与右子树左边比
        return dfs(l->left, r->right) && dfs(l->right, r->left);
    }

    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return dfs(root, root);
    }
};



这道题面试一定不能用遍历和sort,面试官的本意是考察二分,要二分出旋转的点,那个点即是最小值,同时要有完全单调的特判。

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.empty()) return -1;

        int n = nums.size() - 1;
        while (n > 0 && nums[0] == nums[n]) n -- ;  //去除末尾重复元素

        if (nums[0] <= nums[n]) return nums[0];     //数组完全单调的情况,第一个就是最小元素

        int l = 0, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }

        return nums[l];                             //数组不是完全单调,则分界点是最小元素
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;                        //储存最终结果
    vector<int> path;                               //储存每条路径的结果

    void dfs(TreeNode* root, int sum) {
        if (!root) return;

        sum -= root->val;
        path.push_back(root->val);

        if (!root->left && !root-> right && !sum)   //遍历到叶子节点且和相等时
            res.push_back(path);

        dfs(root->left, sum);       //这里不用判空,因为函数第一行已经判空了
        dfs(root->right, sum);
        path.pop_back();            //恢复现场,因为sum是局部变量,故无须恢复
    }

    vector<vector<int>> findPath(TreeNode* root, int sum) {
        if (!root) return res;
        dfs(root, sum);

        return res;
    }
};