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

专题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;}
};