首页 > 其他分享 >【米〇游仿真题】汇总

【米〇游仿真题】汇总

时间：2023-08-06 18:00:21浏览次数：33  
标签：仿真 return nums int res 汇总 vector ListNode

只出现一次的数II

描述

在动物牛的世界中，有一群牛，它们以整数数组的形式排列。除了其中两个牛只出现一次外，其他牛都恰好出现两次。请你设计一个算法，找出并返回那两个只出现一次的牛的编号。返回顺序按照递增序。

示例1

输入：

[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 0]

返回值：

[0,4]

代码

class Solution {
  public:
    vector<int> findSingleCowsII(vector<int>& nums) {
        // write code here
        unordered_map<int, int> hashmap;//创建一个哈希表记录所有元素个数
        for (int num : nums) {
            hashmap[num]++;
        }

        vector<int> res;
        for (const auto& pair : hashmap) {//遍历map，只将值为1的元素保存到res
            if (pair.second == 1) {
                res.push_back(pair.first);
            }
        }
        sort(res.begin(), res.end()); // 对结果数组进行排序，递增序
        return res;
    }
};

只出现一次的数

描述

在动物牛的世界中，有一群牛，它们以整数数组的形式排列。除了其中某一个牛只出现一次外，其他牛都恰好出现三次。请你设计一个算法，找出并返回那个只出现了一次的牛的编号。

示例1

输入：

[1, 1, 1, 2, 2, 2, 3, 4, 4, 4]

返回值：

3

代码

class Solution {
  public:
    int findSingleCow(vector<int>& nums) {
        // write code here
        unordered_map<int, int> hashmap;//创建一个哈希表记录所有元素个数
        for (int num : nums) {
            hashmap[num]++;
        }

        int res;
        for (const auto& pair : hashmap) {//遍历map，只将值为1的元素保存到res
            if (pair.second == 1) {
                res = pair.first;
            }
        }
        return res;
    }
};

牛牛出入圈

描述

假设有一群牛要依次入圈和出圈，牛的编号是唯一的且不重复。给定两个牛的序列 enter 和 leave，它们分别表示牛的入圈顺序和出圈顺序。判断是否存在一种操作顺序，使得牛按照给定的入圈和出圈顺序依次进入和离开圈子。如果存在这样的操作顺序，则返回 true，否则返回 false。

注：牛圈狭长，只能先进入的牛必须等后进入的牛出圈后才能出圈。

示例1

输入：

[1, 2, 3, 4],[2, 1, 4, 3]

返回值：

true

代码

这题就是检查出入栈的合法性，不同的是，这这里要使用两个指针leaveIndex和enterIndex（从1开始，因为一开始需要先把enter的第一个元素加入栈中）来控制进出栈的顺序

先遍历入栈数组enter，将遍历元素压栈。过程中不断比较栈顶元素与leave中leaveIndex下标元素是否相等

若相等，弹出当前栈顶元素，移动leaveIndex指针；当leaveIndex等于leave数组长度时就返回true

若不相等，继续将enter中元素压栈，直到压完所有元素，循环结束；

此时，如果栈中还剩元素，那么将其依次出栈并与当前leave中leaveIndex下标元素比较，相等就弹出

如果有一个不相等即返回false；

当栈中元素弹空，则返回true

class Solution {
public:
    bool validateCowCircle(vector<int>& enter, vector<int>& leave) {
        // write code here
        stack<int> st;
        int leaveIndex = 0;
        st.push(enter[0]);
        int enterIndex = 1;

        while(true){//一直往栈中添加enter内的元素，并不断判断，如果当前栈顶元素等于leave中leaveIndex下标位置元素，弹出
            if(!st.empty() && st.top() == leave[leaveIndex]){
                st.pop();
                leaveIndex++;
                if(leaveIndex == leave.size()) return true;
            }else{//否则继续往栈里压入enter元素
                st.push(enter[enterIndex]);
                enterIndex++;
                if(enterIndex == enter.size()) break;
            }
        }
        //处理完压栈过程中的相同元素后，将栈中元素全部弹出，看看是否满足leave的顺序
        while(!st.empty()){
            if(st.top() == leave[leaveIndex]) {
                st.pop();
                leaveIndex++;
            }else{
                return false;
            }
        }
        return true;  
    }
};

逆时针吃草

描述

在动物牛的农场中，有一块 m 行 n 列的草地，每个位置长的草数量纪录在矩阵matrix中，牛牛想要按照逆时针螺旋的顺序吃草，现在给你这块草地的状况，请你返回牛牛从左下角出发吃草的顺序。

示例1

输入：

[[1, 2, 3], [4, 5, 6]]

返回值：

[4,1,2,3,6,5]

代码

class Solution {
  public:
    vector<int> eatGrass(vector<vector<int> >& matrix) {
        // write code here
        int m = matrix[0].size();//行
        int n = matrix.size();//列

        int left = 0;
        int right = m - 1;
        int top = 0;
        int down = n - 1;

        vector<int> res;
        while(true){//遍历顺序，左上右下
            for(int i = down; i >= top; --i) res.push_back(matrix[i][left]);//遍历左边界
            left++;
            if(left > right) break;

            for(int i = left; i <= right; ++i) res.push_back(matrix[top][i]);//遍历上边界
            top++;
            if(top > down) break;

            for(int i = top; i <= down; ++i) res.push_back(matrix[i][right]);//遍历右边界
            right--;
            if(right < left) break;

            for(int i = right; i >= left; --i) res.push_back(matrix[down][i]);//遍历下边界
            down--;
            if(down < top) break;
        }
        return res;
    }
};

最长不重复子数组长度问题

描述

在一个动物园中，牛牛是一头聪明的牛，他喜欢解决数字问题。现在给你一个整数数组 nums，请你找出其中不含有重复数字的最长连续子数组的长度。

示例1

输入：

[1, 2, 3, 1, 2, 3, 2, 2]

返回值：

3

代码

class Solution {
public:
    int longestUniqueSubarrayLength(vector<int>& nums) {
        // write code here
        unordered_map<int, int> hash_map;//"遍历元素--元素首次出现位置"
        int left = 0;
        int maxLen = 0;

        for(int right = 0; right < nums.size(); ++right){//判断hash_map是否查得到当前遍历值且该遍历值出现在上次重复点之后
            if(hash_map.find(nums[right]) != hash_map.end() && left <= hash_map[nums[right]]){
                left = hash_map[nums[right]] + 1;
            }
            hash_map[nums[right]] = right;
            if(right - left + 1 > maxLen) maxLen = right - left + 1;
        }
        return maxLen;
    }
};

相反链表的合并

描述

有两条链表，一条链表是升序排列的，另一条链表是降序排列的。现在需要将这两条链表合并为一个新的升序链表，并返回。

示例1

输入：

{1, 2, 3, 4, 5},{10, 9, 8, 7, 6}

返回值：

{1,2,3,4,5,6,7,8,9,10}

代码

class Solution {
  public: 
    ListNode* reverse(ListNode* head){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur){
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    ListNode* mergeLists(ListNode* l1, ListNode* l2) {
        // write code here
        l2 = reverse(l2);
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) { // 修改此处，将l1节点插入新链表
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 != nullptr ? l1 : l2;
        return dummy->next;
    }
};

牛牛的目标特征数

描述

牛牛是一种非常特殊的动物，不同种群的牛有着不同的特征值。现在给定不同种群的牛的特征值 features 和一个目标特征值 target。编写一个函数来计算可以组合出目标特征值所需的最少的动物牛个数。如果无法组合出目标特征值，返回 -1。

示例1

输入：

[1, 2, 5],11

返回值：

3

代码

本题与零钱兑换一致

#include <vector>

class Solution {
  public:
    int minAnimalCount(vector<int>& features, int target) {
        vector<int> dp(target + 1, INT_MAX);

        dp[0] = 0;

        for (int i = 0; i < features.size(); ++i) {
            for (int j = features[i]; j <= target; ++j) {
                if (dp[j - features[i]] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - features[i]] + 1);
                }
            }
        }

        return dp[target] == INT_MAX ? -1 : dp[target];
    }
};

打乱所有情况

描述

牛牛是一群非常特殊的动物，它们有着不同的编号。现在给定一个动物牛编号的数组，设计一个函数来实现打乱这个数组并返回所有可能的打乱结果，要求按照字典序输出。

示例1

输入：

[1, 2, 3]

返回值：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

代码

#include <vector>
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums, vector<bool>& used){
        if(path.size() == nums.size()){
            res.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); ++i){
            if(used[i] == true) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int> > getAllShuffles(vector<int>& original) {
        // write code here
        //因为要用字典序返回，所以先要排序
        sort(original.begin(), original.end());
        vector<bool> used(original.size(), false);
        backtracking(original, used);
        return res;
    }
};

数据流中的第 K 大元素

牛的体重各不相同。现在给定一组牛的体重数组，设计一个类 KthLargest 来找到截止到每一位为止的第 k 大的体重，如果截止当前位不足k个元素，则跳过。

请实现 KthLargest 类：

  • KthLargest(int k, vector<int>& nums) 使用整数 k 和动物牛体重数组 nums 初始化对象。
  • int add(int val) 将新的动物牛体重 val 插入数组 nums 后，返回当前数据流中截止到每一位为止的第 k 大的体重。

示例1

输入：

[4, 5, 8, 2],3

返回值：

[4,4]

代码

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> q;
    int k;
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (auto& x: nums) {
            add(x);
        }
    }
    
    int add(int val) {
        q.push(val);
        if (q.size() > k) {
            q.pop();
        }
        return q.top();
    }
};

牛体重的中位数计算

描述

牛牛被广泛用于农业和牧场。现在，请你设计一个数据结构，实现以下功能：给定一个牛重量的数组，计算截止到每一位为止的中位数，并返回这个中位数数组。

示例1

输入：

[100, 200, 300, 400, 500]

返回值：

[100.00000,150.00000,200.00000,250.00000,300.00000]

代码

中位数是有序序列的中间值，对于奇数个元素的序列，中位数是排序后的中间值；对于偶数个元素的序列，中位数是排序后中间两个值的平均值。

#include <vector>
#include <algorithm>

class Solution {
public:
    vector<double> calculateMedians(vector<int>& weights) {
        vector<double> res;
        sort(weights.begin(), weights.end());

        int n = weights.size();
        for (int i = 0; i < n; ++i) {
            double median;
            if (i % 2 == 0) {
                median = weights[i / 2];
            } else {
                median = (weights[i / 2] + weights[i / 2 + 1]) / 2.0;
            }
            res.push_back(median);
        }
        return res;
    }
};

数据流的中位数

https://leetcode.cn/problems/find-median-from-data-stream/description/

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;

    MedianFinder() {}

    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }

    double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0;
    }
};

字符串转换整数 (atoi)

https://leetcode.cn/problems/string-to-integer-atoi/description/

描述

牛是一种强大的动物，以其力量和耐力而闻名。现在，请你编写一个函数，实现将一个字符串转换为一个32位无符号整数的功能。这个函数将会模拟牛的力量，将字符串中的数字提取出来，并转换为无符号整数。

函数算法：

  1. 读入字符串并丢弃无用的前导空格。
  2. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  3. 将前面步骤读入的这些数字转换为无符号整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为0。
  4. 如果整数超过32位无符号整数范围[0, 231-1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于0的整数应该被固定为0，大于232-1的整数应该被固定为2^31-1。
  5. 返回整数作为最终结果。

注意事项：

  • 本题中的空白字符只包括空格字符' '。
  • 除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

示例1

输入：

"4193 with words"

返回值：

4193

代码

class Solution {
  public:
    int myAtoi(string s) {
        // write code here
        if (s.empty()) return 0;
        int index = 0, n = s.size(), sign = 1, res = 0;
        // 处理前置空格
        while (index < n && s[index] == ' ') {
            ++index;
        }
        // 处理符号
        if (index < n && (s[index] == '+' || s[index] == '-')) {
            sign = s[index++] == '+' ? 1 : -1;
        }
        // 处理数字
        while (index < n && isdigit(s[index])) {
            int digit = s[index] - '0';
            // 判断是否溢出
            if (res > (INT_MAX - digit) / 10) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            res = res * 10 + digit;
            ++index;
        }
        return res * sign;
    }
};

第一只公共的牛

描述

在牛牛的农场里，有三个牛圈，分别装着不同的牛。这三个牛圈中的牛可能存在相同的公共牛，它们在不同的牛圈中有着共同的身份。

牛圈信息存储在三个链表中，每个节点表示牛的独特的编号。

请你实现一个函数，根据牛圈的信息，找出这三个牛圈中第一个公共的牛。

示例1

输入：

{1,2,3,4,5,6},{9,5,6},{7,8,5,6}

返回值：

{5,6}

代码

class Solution {
  public:
    ListNode* findIntersection(ListNode* headA, ListNode* headB, ListNode* headC) {
        // write code here
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        ListNode* p3 = headC;

        while (p1 && p2 && p3) {
            if (p1->val == p2->val && p2->val == p3->val) {
                return p1;
            } else if (p1->val <= p2->val && p1->val <= p3->val) {
                p1 = p1->next;
            } else if (p2->val <= p1->val && p2->val <= p3->val) {
                p2 = p2->next;
            } else {
                p3 = p3->next;
            }
        }
        return nullptr;
    }
};

牛群间的二叉树颠倒

描述

农场里的牛群正在玩一个二叉树翻转游戏。游戏中，每头牛都有一个二叉树。现在，你需要帮助牛群将这个二叉树上下翻转，并返回新的根节点。

你可以按下面的步骤翻转一棵二叉树：

  1. 原来的左子节点变成新的根节点
  2. 原来的根节点变成新的右子节点
  3. 原来的右子节点变成新的左子节点

上面的步骤逐层进行。题目数据保证每个右节点都有一个同级节点（即共享同一父节点的左节点）且不存在子节点。

示例1

输入：

{1,2,3,4,5}

返回值：

{4,5,2,#,#,3,1}

代码

class Solution {
  public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        // write code here
        if (root == nullptr || root->left == nullptr) return root;
        
        TreeNode* newRoot = upsideDownBinaryTree(root->left);
        root->left->left = root->right;
        root->left->right = root;
        root->left = nullptr;
        root->right = nullptr;
        
        return newRoot;
    }
};

标签：仿真,return,nums,int,res,汇总,vector,ListNode
From： https://www.cnblogs.com/DAYceng/p/17609684.html

相关文章

  • 基于位相光栅的四波横向剪切干涉法波前检测算法的matlab仿真
    1.算法理论概述      波前检测技术是现代光学中的重要技术之一，可以用于衡量光学系统的成像质量和研究光学系统的异常现象。随着现代光学技术的不断发展，波前检测技术也在不断地发展和完善。其中，基于位相光栅的四波横向剪切干涉法波前检测算法是一种常用的波前检测算法，本文......
  • tracer ftrace笔记（18）—— 待解问题汇总
    1.长时间卡在MSG_WINDOW_FOCUS_CHANGED条目中publicvoidhandleMessage(Messagemsg)//android/view/ViewRootImpl.javaTrace.traceBegin(Trace.TRACE_TAG_VIEW,getMessageName(msg));//这里打印条目有MSG_WINDOW_FOCUS_CHANGEDhandleMessageImpl(msg);......
  • 总奖金200万的算法赛方案汇总！
    2021DIGIX全球校园AI算法赛方案汇总关于赛事信息地址：https://gitee.com/coggle/competition-baseline/tree/master/competition/DIGIX2021地址在文末阅读原文可直接打开......
  • 《小规模机器学习中的正样本-未标注样本学习》方法教程转载汇总
     《小规模机器学习中的正样本-未标注样本学习》方法教程转载汇总tinyMLTalksPhoenix-1.PositiveUnlabeledLearningforTinyMLPULearningTutorial-2.PULearningdefinitionsPULearningTutorial-3.AssumptionstoenablePULearning......
  • 最短路问题汇总
    最短路单源最短路求从一个点到其他所有点的最短距离所有边权是正数朴素Dijkstra算法O(n^2)用于稠密图m>=n步骤：dist[i]：每个点离起点的距离S：已经确定最短距离的点V：没有确定最短距离的点初始化所有点的距离dist[起点]=0；dist[其他点]=inf循环找V中离起点......
  • 编程精华资源（ITeye优秀专栏）大汇总
    博客是记录学习历程、分享经验的最佳平台，多年以来，各路技术大牛在ITeye网站上产生了大量优质的技术文章，并将系列文章集结成专栏，以便读者能够更便捷、更系统地浏览学习，这些可称之为“编程精华资源”。 为了便于读者更好地查阅，本文将ITeye中的这些精华资源进行了整理分类，你可以通过......
  • SIEMENS PLC介绍、西门子S1200系列接线、编程、下载和仿真
    前言  西门西PLC、台达触摸屏、法兰克机床等等多年以前玩得比较多，改造机床、维修机床、给机床编程等等，没事还能扯个零件啥的，之前也没总结过，有时间就重新整理下。  本章后面以西门1200实物为例，下载一个基本程序。PLC  玩得比较多的就是西门PLC，单个模块就是3K起，一个24V电源......
  • Python爬虫遇到重定向问题解决办法汇总
    在进行Python爬虫任务时，遇到重定向问题是常见的问题之一。重定向是指在发送请求时，服务器会返回一个新的URL，将请求重新定向到该URL。为了帮助您解决这个问题，本文将提供一些实用的解决办法，并给出相关的代码示例，希望能对您的爬虫任务有所帮助。了解重定向问题重定向问题通常是由于网......
  • 【总结】百家稷学！重点汇总有三AI（教育）服务过的那些企业与学校
    近一年多来我们开始服务B端用户，已经陆续和许多企业和学校进行了长短期的合作，2021年年关将至，下面来简单做一个汇总。阿里云阿里云是我们的第一个客户，合作次数最多，历经时间也最长。自从2019年开始以深度学习模型设计为主题在阿里云开启了3次直播之后，我们后面又与阿里云进行了多次合作......
  • 【总结】超1000页有三AI文档资源领取方法汇总！
    这几年我们平台输出了很多内容，有免费的也有付费的，有图文也有视频，本次对我们所有文档类资源领取方法做一个汇总。有三的书相关资料至今有三已经出版了4本书，分别是《深度学习之图像识别》，《深度学习之模型设计》，《深度学习之人脸图像处理》，《深度学习之摄影图像处理》，介绍如下：一些书......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99