深圳建设网站过程_嘉兴网站建设一薇_seo排名优化软件有用_网络整合营销是什么意思

文章目录

前言
一、找到数组的中间位置
二、有序数组中的单一元素
三、杨辉三角（Ⅱ）
四、超过阈值的最小操作数Ⅰ
五、找出峰值
六、统计已测试设备
七、统计和小于目标的下标对数目
- 1.单向遍历法
- 2.双指针法（时间复杂度小）
八、计算K置位下标元素的和
九、数组能形成多少数对
十、求出现两次数字的XOR值

前言

本文为《C++学习》的第篇文章，今天是顺序表的最后一篇总结，通过leetcode来练习顺序表的枚举。

一、找到数组的中间位置

1991.找到数组的中间位置

class Solution {
public:int findMiddleIndex(vector<int>& nums) {int totalSum = 0;for (int num : nums) {totalSum += num;}int leftSum = 0;for (int i = 0; i < nums.size(); ++i) {int rightSum = totalSum - leftSum - nums[i];if (leftSum == rightSum) {return i;}leftSum += nums[i];}return -1;}
};

二、有序数组中的单一元素

540.有序数组中的单一元素

class Solution {
public:int singleNonDuplicate(vector<int>& nums) {int left = 0; // 初始化左指针为数组的起始位置int right = nums.size() - 1; // 初始化右指针为数组的末尾位置while (left < right) { // 当左指针小于右指针时继续循环int mid = left + (right - left) / 2; // 计算中间位置// 确保 mid 是偶数，以便进行成对比较if (mid % 2 == 1) {mid--; // 如果 mid 是奇数，则将其减 1 变为偶数}if (nums[mid] == nums[mid + 1]) { // 检查 mid 和 mid+1 是否相等left = mid + 2; // 如果相等，说明唯一的元素在右半部分，更新左指针为 mid + 2} else {right = mid; // 如果不相等，说明唯一的元素在左半部分或就是 mid，更新右指针为 mid}}return nums[left]; // 返回左指针指向的元素，即为唯一出现一次的元素}
};

三、杨辉三角（Ⅱ）

119.杨辉三角（Ⅱ）

class Solution {
public:vector<int> getRow(int rowIndex) {vector<int> row(rowIndex + 1, 0); // 初始化结果数组，大小为 rowIndex + 1，初始值为 0row[0] = 1; // 第一行的第一个元素总是 1for (int i = 1; i <= rowIndex; ++i) { // 从第二行开始构建每一行for (int j = i; j > 0; --j) { // 从后向前更新当前行的元素row[j] += row[j - 1]; // 每个元素等于其上方和左上方元素之和}}return row; // 返回构建好的第 rowIndex 行}
};

四、超过阈值的最小操作数Ⅰ

3065.超过阈值的最小操作数Ⅰ

class Solution {
public:int minOperations(vector<int>& nums, int k) {int operations = 0; // 初始化操作次数为 0for (int num : nums) { // 遍历数组中的每个元素if (num < k) { // 如果当前元素小于 koperations++; // 增加操作次数}}return operations; // 返回所需的操作次数}
};

五、找出峰值

2951.找出峰值

class Solution {
public:vector<int> findPeaks(vector<int>& mountain) {vector<int> peaks; // 初始化一个向量来存储峰值的下标for (int i = 1; i < mountain.size() - 1; ++i) { // 从第二个元素到倒数第二个元素遍历if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) { // 检查是否为峰值peaks.push_back(i); // 如果是峰值，记录其下标}}return peaks; // 返回所有峰值的下标}
};

六、统计已测试设备

2960.统计已测试设备

class Solution {
public:int countTestedDevices(vector<int>& batteryPercentages) {int testedDevices = 0; // 初始化已测试设备的计数for (int i = 0; i < batteryPercentages.size(); ++i) {if (batteryPercentages[i] > 0) { // 检查当前设备的电池百分比是否大于 0testedDevices++; // 增加已测试设备的计数// 减少后续所有设备的电池百分比，确保不会低于 0for (int j = i + 1; j < batteryPercentages.size(); ++j) {batteryPercentages[j] = max(0, batteryPercentages[j] - 1);}}}return testedDevices; // 返回已测试设备的数量}
};

七、统计和小于目标的下标对数目

2824.统计和小于目标的下标对数目

1.单向遍历法

class Solution {
public:int countPairs(vector<int>& nums, int target) {int count = 0; // 初始化满足条件的下标对数量for (int i = 0; i < nums.size(); ++i) { // 外层循环遍历每个元素for (int j = i + 1; j < nums.size(); ++j) { // 内层循环遍历后续元素if (nums[i] + nums[j] < target) { // 检查当前两个元素之和是否小于目标值count++; // 如果是，则增加满足条件的下标对数量}}}return count; // 返回满足条件的下标对数量}
};

2.双指针法（时间复杂度小）

class Solution {
public:int countPairs(vector<int>& nums, int target) {sort(nums.begin(), nums.end()); // 对数组进行排序int left = 0; // 初始化左指针int right = nums.size() - 1; // 初始化右指针int count = 0; // 初始化满足条件的下标对数量while (left < right) { // 当左指针小于右指针时继续循环if (nums[left] + nums[right] < target) { // 检查当前左右指针所指元素之和是否小于目标值count += right - left; // 如果是，则增加满足条件的下标对数量left++; // 将左指针右移一位} else {right--; // 否则，将右指针左移一位}}return count; // 返回满足条件的下标对数量}
};

八、计算K置位下标元素的和

2859.计算K置位下标元素的和

class Solution {
public:int sumIndicesWithKSetBits(vector<int>& nums, int k) {int sum = 0; // 初始化结果和为 0for (int i = 0; i < nums.size(); ++i) { // 遍历每个下标if (__builtin_popcount(i) == k) { // 检查下标的二进制表示中是否有恰好 k 个置位sum += nums[i]; // 如果是，则将对应的 nums 元素加到结果和中}}return sum; // 返回结果和}
};

补充： 函数__builtin_popcount(i) == k
是 GCC 编译器提供的一个内置函数，用于计算一个无符号整数的二进制表示中 1 的数量。
手动计算如下：

int popcount(unsigned int x) {int count = 0;while (x) {count += x & 1; // 检查最低位是否为 1x >>= 1; // 右移一位}return count;
}

九、数组能形成多少数对

2341.数组能形成多少数对
哈希表

#include <unordered_map>
class Solution {
public:vector<int> numberOfPairs(vector<int>& nums) {unordered_map<int, int> countMap; // 哈希表用于统计每个整数出现的次数// 统计每个整数出现的次数for (int num : nums) {countMap[num]++;}int pairs = 0; // 形成的数对数目int remaining = 0; // 剩余的整数数目// 遍历哈希表，计算数对和剩余整数的数量for (const auto& entry : countMap) {int count = entry.second;pairs += count / 2; // 可以形成的数对数量remaining += count % 2; // 剩余的整数数量}return {pairs, remaining}; // 返回结果数组}
};

顺序表

#include <algorithm>
class Solution {
public:vector<int> numberOfPairs(vector<int>& nums) {sort(nums.begin(), nums.end()); // 对数组进行排序int pairs = 0; // 形成的数对数目int remaining = 0; // 剩余的整数数目int n = nums.size();for (int i = 0; i < n; ) {if (i + 1 < n && nums[i] == nums[i + 1]) { // 检查相邻元素是否相等pairs++; // 形成一个数对i += 2; // 跳过这两个元素} else {remaining++; // 当前元素计入剩余的整数数量i++;}}return {pairs, remaining}; // 返回结果数组}
};

十、求出现两次数字的XOR值

3158.求出现两次数字的XOR值
哈希表

#include<unordered_map>
class Solution {
public:int duplicateNumbersXOR(vector<int>& nums) {unordered_map<int, int> countMap; // 哈希表用于统计每个整数出现的次数// 统计每个整数出现的次数for (int num : nums) {countMap[num]++;}int xorValue = 0; // 存储出现两次的数字的按位 XOR 值// 遍历哈希表，计算出现两次的数字的按位 XOR 值for (const auto& entry : countMap) {if (entry.second == 2) { // 检查是否出现两次xorValue ^= entry.first; // 计算按位 XOR 值}}return xorValue; // 返回按位 XOR 值}
};