leetcode秋招冲刺 （专题16--18）

  • 开发
  • 21

专题16：分治

题目169：多数元素（YES）

  • 解题思路：使用哈希表可以统计出现次数的性质，直接统计就行。

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //使用哈希表显然是最容易的,用哈希表可以计数的功能
        unordered_map<int,int>map;

        for(int i=0;i<nums.size();i++)
        {
            map[nums[i]]++;
            if(map[nums[i]]>(nums.size()/2))
            {
                return nums[i];
            }
        }

        return 0;
    }
};

题目159：库存管理|||（YES）

  • 使用冒泡排序算法

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

class Solution {
public:
    //冒泡排序
    void boblle_sort(vector<int>&stock)
    {
        for(int i=0;i<stock.size()-1;i++)
        {
            for(int j=0;j<stock.size()-i-1;j++)
            {
                if(stock[j]>stock[j+1])
                {
                    int temp=stock[j];
                    stock[j]=stock[j+1];
                    stock[j+1]=temp;
                }
            }
        }
    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {

        //排序
        boblle_sort(stock);

        vector<int>ans;

        for(int i=0;i<cnt;i++)
        {
            ans.push_back(stock[i]);
        }

        return ans;
    }
};

题目161：连续天数的最高销售额（NO）

  • 解题思路：就是连续的扫描每次再原来的基础上叠加出最大值

某公司每日销售额记于整数数组 sales，请返回所有 连续 一或多天销售额总和的最大值。

要求实现时间复杂度为 O(n) 的算法。

class Solution {
public:
    int maxSales(vector<int>& sales) {
        int pre = 0, maxAns = sales[0];

        //就是连续的扫描每次再原来的基础上叠加出最大值
        for (const auto &x: sales) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);//记录最大值
        }
        return maxAns;
    }
};

题目158：库存管理||（YES）

  • 解题思路：哈希表

仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id。

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        //哈希表
        unordered_map<int,int>map;

        for(int i=0;i<stock.size();i++)
        {
            map[stock[i]]++;
            if(map[stock[i]]>(stock.size()/2))
            {
                return stock[i];
            }
        }

        return 0;
    }
};

题目142：训练计划（YES）

  • 解题思路：这题依旧非常熟悉了，使用一个新的head作为新链表，然后循环比较l1和l2就行了。

给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 升序 记录于链表并返回。

注意：新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * 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* trainningPlan(ListNode* l1, ListNode* l2) {
        //这题原来做过，需要使用一个head指针代码返回的新的链表头结点
        ListNode*head=new ListNode();
        ListNode*temp=head;

        //开始遍历操作
        while(l1!=nullptr&&l2!=nullptr)
        {
            if(l1->val<=l2->val)
            {
                temp->next=l1;
                l1=l1->next;
                temp=temp->next;
            }else if(l2->val<l1->val)
            {
                temp->next=l2;
                l2=l2->next;
                temp=temp->next;
            }
        }

        if(l1!=nullptr)
        {
            temp->next=l1;
        }else
        {
            temp->next=l2;
        }

        return head->next;

    }
};

专题17:位运算

题目136：只出现一次的数字（YES）

  • 解题思路：哈希表

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //使用哈希表
        unordered_map<int,int>map;
        for(int i=0;i<nums.size();i++)
        {
            map[nums[i]]++;
        }

        for(int i=0;i<nums.size();i++)
        {
            if(map[nums[i]]==1)
            {
                return nums[i];
            }
        }
        return 0;
    }
};
  • 方法二：使用异或运算，切记异或可以找出出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //使用异或运算
        int ans=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            ans^=nums[i];
        }

        return ans;
    }
};

题目191：位1的个数（NO）

  • 使用&与运算和<<左移运算

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中
设置位
的个数（也被称为汉明重量）。

class Solution {
public:
    int hammingWeight(int n) {
        int ans=0;

        for(int i=0;i<32;i++)
        {
            //这里1<<i就会生成第i位为1的二进制数
            if(n&(1<<i))
            {
                ans++;
            }
        }

        return ans;
    }
};
  • 代码解释

这段代码是一个C++的类Solution，其中包含一个公有方法hammingWeight，用于计算一个32位无符号整数中有多少个位是1（即汉明重量）。该方法的实现如下：

  1. 首先定义了一个整数ret来存储最终的结果（即汉明重量），并初始化为0。
  2. 然后使用一个for循环遍历0到31共32位（32位无符号整数的位数）。
  3. 在循环中，通过将1左移i位（1 << i）来生成一个只有第i位为1的数，然后与输入的n进行按位与运算（n & (1 << i)）。
  4. 如果按位与的结果不为0（即第i位为1），则将ret递增1。
  5. 最后返回ret作为结果，即32位无符号整数n中为1的位的个数。

这段代码利用位运算的特性，逐位检查n的每一位是否为1，从而计算出n的汉明重量。

  • 为何1<<i就可生成第i位是1的二进制

在C++中，<< 是左移位运算符，其功能是将一个数的二进制表示向左移动指定的位数。当我们使用 1 << i 时，表示将数字1的二进制表示向左移动i位，其效果是生成一个只有第i位为1的二进制数。

举个例子，当i=0时，1 << 0 就是将二进制数1向左移动0位，结果为1，二进制表示为00000001；当i=1时，1 << 1 就是将二进制数1向左移动1位，结果为2，二进制表示为00000010；依此类推，当i=2时，结果为4，二进制表示为00000100，依此类推。

因此，通过1 << i，我们可以生成一个只有第i位为1的二进制数（其余位为0），用于与原始数字进行按位与运算，以判断原始数字的第i位是否为1。

  • 拓展：打印二进制数的方法
#include <iostream>
#include <bitset> // 需要包含头文件 <bitset> 来使用 bitset 类

void printBinary(int n) {
    std::bitset<32> bs(n); // 使用 bitset 类来表示32位二进制
    std::cout << "Binary representation of " << n << " is: " << bs << std::endl;
}

int main() {
    int num = 10; // 需要打印的整数
    printBinary(num); // 调用打印方法
    return 0;
}

题目268：丢失的数字（YES）

  • 先排序，再遍历查找哪个丢失了。

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //先排序
        sort(nums.begin(),nums.end());

        int ans=0;
        for(int i=0;i<nums.size();i++)
        {
            if(ans!=nums[i])
            {
                return ans;
            }
            ans++;
        }
        return ans;
    }
};

题目405：数字转换为十六进制（NO）

  • 解题思路：位运算

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

  • 官方题解
class Solution {
public:
    string toHex(int num) {
        if (num == 0) {
            return "0";
        }
        string sb;
        for (int i = 7; i >= 0; i --) {
            int val = (num >> (4 * i)) & 0xf;
            if (sb.length() > 0 || val > 0) {
                char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
                sb.push_back(digit);
            }
        }
        return sb;
    }
};

专题18：链表

题目141：环形链表（YES）

  • 解题思路：使用哈希表或者快慢指针都行

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

  • 哈希表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //使用哈希表
        ListNode*temp=head;
        unordered_map<ListNode*,int>map;
        while(temp!=NULL)
        {
            if(map[temp]>1)
            {
                return true;
            }
            map[temp]++;
            temp=temp->next;
        }

        return false;

    }
};
  • 快慢指针
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL)
        {
            return false;
        }
        ListNode*temp=head;

        ListNode*slow=head;
        ListNode*fast=head->next;

        while(slow!=fast)
        {
            if(fast==NULL||fast->next==NULL)
            {
                return false;
            }
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }
};

题目160：相交链表（YES）

  • 解题思路：使用哈希表即可

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //使用哈希表先存储一个链表
        unordered_map<ListNode*,int>map;
        ListNode*tempA=headA;

        while(tempA!=NULL)
        {
            map[tempA]++;
            tempA=tempA->next;
        }
        //扫描headB
        ListNode*tempB=headB;
        while(tempB!=NULL)
        {
            map[tempB]++;
            if(map[tempB]>1)
            {
                return tempB;
            }
            tempB=tempB->next;
        }
        return NULL;
    }
};

题目140：训练计划||（YES）

  • 解题思路：先计算链表长度，在计算要移动的步数

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

 
 /**
 * 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* trainingPlan(ListNode* head, int cnt) {
        //先计算链表的长度
        int len=0;
        ListNode*temp=head;
        while(temp!=nullptr)
        {
            len++;
            temp=temp->next;
        }
        int move=len-cnt;//要移动的步数
        temp=head;
        for(int i=0;i<move;i++)
        {
            temp=temp->next;
        }
        return temp;
    }
};

题目83：删除排序链表的重复元素（NO）

  • 解题思路：一次遍历，难点在于你要把控好什么使用移动。

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

/**
 * 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* deleteDuplicates(ListNode* head) {
        if (!head) 
        {
            return head;
        }

        ListNode* cur = head;
        while (cur->next) 
        {
            if (cur->val == cur->next->val)
            {
                //如果两个相同，前面结点无需移动
                cur->next = cur->next->next;
            }
            else 
            {
                cur = cur->next;
            }
        }

        return head;
    }
};
阅读全部

相关推荐

  1. leetcode秋招冲刺 （专题16--18）

    2024-07-12 02:02:01       22 阅读

  5. 【冲刺秋招，许愿offer】第 二 天

    2024-07-12 02:02:01       29 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-12 02:02:01       67 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-12 02:02:01       72 阅读

  9. 在Django里面运行非项目文件

    2024-07-12 02:02:01       58 阅读

  19. Python语言-面向对象

    2024-07-12 02:02:01       69 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-12 02:02:01       64 阅读

热门阅读

  2. 日常的网络杂记

    2024-07-12 02:02:01       20 阅读

  3. 软考高级第四版备考--第13天（控制质量）Perform Quanlity Control

    2024-07-12 02:02:01       22 阅读

  4. 设计模式之单例模式

    2024-07-12 02:02:01       23 阅读

  5. 软件架构之测评方法

    2024-07-12 02:02:01       16 阅读

  7. Webpack打包生产环境进行优化处理

    2024-07-12 02:02:01       21 阅读

  8. 【深度学习】关于模型加速

    2024-07-12 02:02:01       23 阅读

  10. k8s 部署RuoYi-Vue-Plus之mysql搭建

    2024-07-12 02:02:01       23 阅读

  11. 大数据面试题之Hudi(1)

    2024-07-12 02:02:01       19 阅读

  13. ES6 Iterator 与 for...of 循环（五）

    2024-07-12 02:02:01       24 阅读

  15. AcWing 3587：连通图 ← dfs（邻接矩阵 or 链式前向星）

    2024-07-12 02:02:01       26 阅读

  17. 对素数的一种新理解

    2024-07-12 02:02:01       22 阅读

  18. 力扣 454四数相加

    2024-07-12 02:02:01       21 阅读

  20. 十大排序算法（慢慢更新）

    2024-07-12 02:02:01       23 阅读

  22. 简谈设计模式之建造者模式

    2024-07-12 02:02:01       18 阅读

  28. 力扣题解（乘积最大子数组）

    2024-07-12 02:02:01       24 阅读

  30. synchronized (userAccount.intern())知识点

    2024-07-12 02:02:01       23 阅读