怎么做展示网站,保定网站制作哪家好建设,网站新闻发布后前台不显示,品牌官方网站专题16#xff1a;分治
题目169#xff1a;多数元素#xff08;YES#xff09;
解题思路#xff1a;使用哈希表可以统计出现次数的性质#xff0c;直接统计就行。
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊…专题16分治
题目169多数元素YES
解题思路使用哈希表可以统计出现次数的性质直接统计就行。
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
class Solution {
public:int majorityElement(vectorint nums) {//使用哈希表显然是最容易的,用哈希表可以计数的功能unordered_mapint,intmap;for(int i0;inums.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(vectorintstock){for(int i0;istock.size()-1;i){for(int j0;jstock.size()-i-1;j){if(stock[j]stock[j1]){int tempstock[j];stock[j]stock[j1];stock[j1]temp;}}}}vectorint inventoryManagement(vectorint stock, int cnt) {//排序boblle_sort(stock);vectorintans;for(int i0;icnt;i){ans.push_back(stock[i]);}return ans;}
};题目161连续天数的最高销售额NO
解题思路就是连续的扫描每次再原来的基础上叠加出最大值
某公司每日销售额记于整数数组 sales请返回所有 连续 一或多天销售额总和的最大值。
要求实现时间复杂度为 O(n) 的算法。
class Solution {
public:int maxSales(vectorint 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(vectorint stock) {//哈希表unordered_mapint,intmap;for(int i0;istock.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*headnew ListNode();ListNode*temphead;//开始遍历操作while(l1!nullptrl2!nullptr){if(l1-vall2-val){temp-nextl1;l1l1-next;temptemp-next;}else if(l2-vall1-val){temp-nextl2;l2l2-next;temptemp-next;}}if(l1!nullptr){temp-nextl1;}else{temp-nextl2;}return head-next;}
};
专题17:位运算
题目136只出现一次的数字YES
解题思路哈希表
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。
class Solution {
public:int singleNumber(vectorint nums) {//使用哈希表unordered_mapint,intmap;for(int i0;inums.size();i){map[nums[i]];}for(int i0;inums.size();i){if(map[nums[i]]1){return nums[i];}}return 0;}
};
方法二使用异或运算切记异或可以找出出现一次的数字
class Solution {
public:int singleNumber(vectorint nums) {//使用异或运算int ansnums[0];for(int i1;inums.size();i){ans^nums[i];}return ans;}
};题目191位1的个数NO
使用与运算和左移运算
编写一个函数获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数也被称为汉明重量。
class Solution {
public:int hammingWeight(int n) {int ans0;for(int i0;i32;i){//这里1i就会生成第i位为1的二进制数if(n(1i)){ans;}}return ans;}
};代码解释
这段代码是一个C的类Solution其中包含一个公有方法hammingWeight用于计算一个32位无符号整数中有多少个位是1即汉明重量。该方法的实现如下
首先定义了一个整数ret来存储最终的结果即汉明重量并初始化为0。然后使用一个for循环遍历0到31共32位32位无符号整数的位数。在循环中通过将1左移i位1 i来生成一个只有第i位为1的数然后与输入的n进行按位与运算n (1 i)。如果按位与的结果不为0即第i位为1则将ret递增1。最后返回ret作为结果即32位无符号整数n中为1的位的个数。
这段代码利用位运算的特性逐位检查n的每一位是否为1从而计算出n的汉明重量。
为何1i就可生成第i位是1的二进制
在C中 是左移位运算符其功能是将一个数的二进制表示向左移动指定的位数。当我们使用 1 i 时表示将数字1的二进制表示向左移动i位其效果是生成一个只有第i位为1的二进制数。
举个例子当i0时1 0 就是将二进制数1向左移动0位结果为1二进制表示为00000001当i1时1 1 就是将二进制数1向左移动1位结果为2二进制表示为00000010依此类推当i2时结果为4二进制表示为00000100依此类推。
因此通过1 i我们可以生成一个只有第i位为1的二进制数其余位为0用于与原始数字进行按位与运算以判断原始数字的第i位是否为1。
拓展打印二进制数的方法
#include iostream
#include bitset // 需要包含头文件 bitset 来使用 bitset 类void printBinary(int n) {std::bitset32 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(vectorint nums) {//先排序sort(nums.begin(),nums.end());int ans0;for(int i0;inums.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;}
};
