计算机转专业笔试题目

含负数进行绝对值排序

参考

给你一个整数数组 nums，请你将该数组升序排列

/* //插入排序，o(n2)，超时 //从第二个数开始，将每个数插入到前面已排好序的序列中（所有比当前数大的后移一格） class Solution { public: vector<int> sortArray(vector<int>& nums) { int n = nums.size(); for(int i = 1; i < n; i++) { int temp = nums[i]; int j = i-1; for( ; j >= 0; j--) { if(nums[j] > temp) nums[j+1] = nums[j]; else break; } nums[j+1] = temp; } return nums; } }; */
/* //希尔(shell)排序 //多轮插入排序，使序列逐步有序化 //可以通过所有测试例子 class Solution { public: vector<int> sortArray(vector<int>& nums) { int n = nums.size(); int d = n / 2; for(int d = n / 2; d >= 1; d /= 2 ) { for(int i = 0; i < d; i++) { for(int j = i + d; j < n; j += d) { int temp = nums[j]; int k = j - d; for(; k >= 0; k -= d) { if(nums[k] > temp) nums[k + d] = nums[k]; else break; } nums[k + d] = temp; } } } return nums; } }; */
/* //冒泡排序和快速排序都属于交换排序 //冒泡排序，o(n^2)，超时 //把小数不断地往数组前端换，或者把大数不断地往数组末端换 //如果某一轮没有发生任何交换，说明排好了 class Solution { public: void swap(int & x, int & y) { int temp = x; x = y; y = temp; } vector<int> sortArray(vector<int>& nums) { int n = nums.size(); for(int i = 0; i < n; i++) { bool flag = true; for(int j = n - 1; j > i; j--) { if(nums[j] < nums[j - 1]) { swap(nums[j], nums[j - 1]); flag = false; } } if(flag) break; } return nums; } }; */

/* //快速排序，o(nlogn) //每次随机选一个数，把比它大的数放右边，比它小的数放左边，然后对左右两边重复执行即可 class Solution { public: int partition(vector<int>& nums, int left, int right, int mid) { int temp = nums[mid]; nums[mid] = nums[left]; while(left < right) { while(left < right && nums[right] >= temp) right--; nums[left] = nums[right]; while(left < right && nums[left] <= temp) left++; nums[right] = nums[left]; } nums[right] = temp; return left; } void quick_sort(vector<int>& nums, int left, int right) { if(left < right) { int mid = left + rand() % (right - left + 1); mid = partition(nums, left, right, mid); quick_sort(nums, left, mid - 1); quick_sort(nums, mid + 1, right); } } vector<int> sortArray(vector<int>& nums) { int n = nums.size(); quick_sort(nums, 0, n-1); return nums; } }; */

/* //简单选择排序，每次从未排序部分选出一个最小的，放在数组左端；或每次从未排序部分选出一个最大的，放在数组右端 //简单选择排序不存在最好，或者最坏情况，时间复杂度总是o(n^2) class Solution { public: void swap(int & x, int & y) { int temp = x; x = y; y = temp; } vector<int> sortArray(vector<int>& nums) { for(int i = 0; i < nums.size(); i++) { int min = i; for(int j = i + 1; j < nums.size(); j++) if(nums[j] < nums[min]) min = j; if(min > i) swap(nums[i], nums[min]); } return nums; } }; */

/* //堆排序，o(nlogn) //先建大根堆，然后把根和尾部元素互换，然后重建堆 class Solution { public: void build_heap(vector<int>& nums) { int n = nums.size(); for(int i = n / 2 - 1; i >= 0; i-- ) { adjust_heap(nums, i, n - 1); } } void adjust_heap(vector<int>& nums, int k, int pos) //将k为根的子树调整为大根堆，pos是最后一个 { int temp = nums[k]; for(int i = k * 2 + 1; i <= pos; i = i * 2 + 1) { if(i + 1 <= pos && nums[i] < nums[i+1]) i++; //这里特别注意，是temp >= nums[i]，而不是nums[k] >= nums[i] //目的是找到第一个节点，其子女均不小于temp if(temp >= nums[i]) break; nums[k] = nums[i]; k = i; } nums[k] = temp; } vector<int> sortArray(vector<int>& nums) { int n = nums.size(); build_heap(nums); for(int i = n - 1; i > 0; i--) { swap(nums[i], nums[0]); adjust_heap(nums, 0, i-1); } return nums; } }; */

//归并排序，先将所有的数两两分组，再不断地执行合并两个升序数组的操作即可
//时间复杂度o(nlogn)，空间需要一个额外的与nums等长的数组
class Solution {
   
public:

    void merge(vector<int>& nums, vector<int>& temp, int left, int right, int mid)
    //把两个已经排好序的合并，mid是左序列的尾
    {
   
        for(int i = left; i <= right; i++)
            temp[i] = nums[i];
        int i = left;
        int j = mid + 1;
        int k = left;
        while(i <= mid && j <= right)
        {
   
            if(temp[i] <= temp[j])
                nums[k] = temp[i++];
            else
                nums[k] = temp[j++];
            k++;
        }
        while(i <= mid)
            nums[k++] = temp[i++];
        while(j <= right)
            nums[k++] = temp[j++];
    }

    void merge_sort(vector<int>& nums, vector<int> & temp, int left, int right)
    {
   
        if(right > left)
        {
   
            int mid = (left + right) / 2;
            merge_sort(nums, temp, left, mid);
            merge_sort(nums, temp, mid + 1, right);
            merge(nums, temp, left, right, mid);
        }
    }

    //二路归并
    vector<int> sortArray(vector<int>& nums) {
   
        int n = nums.size();
        vector<int> temp(n, 0);
        merge_sort(nums, temp, 0, n-1);
        return nums;
    }
};

字符串按顺序包含

参考

把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…".

现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。

注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。

class Solution {
   
public:
    bool isContinous(char prev, char curr) {
   
        if (prev == 'z') return curr == 'a';
        return prev + 1 == curr;
    }
    int findSubstringInWraproundString(string p) {
   
        vector<int> dp(26, 0);
        int N = p.size();
        int k = 0;
        for (int i = 0; i < N; ++i) {
   
            if (i > 0 && isContinous(p[i - 1], p[i])) {
   
                ++k;
            } else {
   
                k = 1;
            }
            dp[p[i] - 'a'] = max(dp[p[i] - 'a'], k);
        }
        return accumulate(dp.begin(), dp.end(), 0);
    }
};

给定四坐标点，进行矩形相交面积求取

参考

给你 二维 平面上两个 由直线构成的 矩形，请你计算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 顶点和 右上 顶点坐标表示：
第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

示例1
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45
示例2
输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16
提示
-104 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 104

class Solution {
   
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
   
        //计算第一个长方形的面积
        int area1=(ax2-ax1)*(ay2-ay1);
        //计算第二个长方形的面积
        int area2=(bx2-bx1)*(by2-by1);
        //计算总的长方形的面积
        int allarea=area1+area2;
        //计算相交的部分形成的长方形的高度width
        int widthy1=max(ay1,by1);
        int widthy2=min(ay2,by2);
        //不相交
        if(widthy1>=widthy2){
   
            return allarea;
        }
        //计算相交部分的长方形的宽度length
        int lenthg1=max(ax1,bx1);
        int lenthg2=min(ax2,bx2);
        //不相交
        if(lenthg1>=lenthg2){
   
            return allarea;
        }
        int width=widthy2-widthy1;
        int length=lenthg2-lenthg1;
        //计算相交部分的面积
        int subarea=width*length;
        //减去相交部分的面积即为答案
        int realarea=allarea-subarea;
        return realarea;
    }
};

n被k整除直到为0所得过程的最优求取

参考

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
   
public:
    void DFS(TreeNode *node, int deep, int &max_deep) {
   
        if (node == nullptr) {
   
            return;
        }
        max_deep = max(deep, max_deep);
        DFS(node->left, deep + 1, max_deep);
        DFS(node->right, deep + 1, max_deep);
    }
    int maxDepth(TreeNode* root) {
   
        //DFS
        int deep = 1, max_deep = 0;
        DFS(root, deep, max_deep);
        return max_deep;
    }
};