计算机转专业笔试题目

含负数进行绝对值排序

参考

给你一个整数数组 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;
    }
};

最后

以上就是动人玫瑰最近收集整理的关于计算机转专业笔试题目的全部内容，更多相关计算机转专业笔试题目内容请搜索靠谱客的其他文章。