C++数据结构学习（顺序表）
文章目录
- 顺序表
- 杭州电子科技大学在线评测
- 2008 数值统计
- 使用顺序表实现
- 2014 青年歌手大奖赛_评委会打分
- Leetcode题目
- [LCP 01. 猜数字](https://leetcode.cn/problems/guess-numbers/description/)
- [LCP 06. 拿硬币](https://leetcode.cn/problems/na-ying-bi/description/)
- [2057. 值相等的最小索引](https://leetcode.cn/problems/smallest-index-with-equal-value/description/)
- [485. 最大连续 1 的个数](https://leetcode.cn/problems/max-consecutive-ones/description/)
- 2006.差的绝对值为K的数对题目
- [1464. 数组中两元素的最大乘积](https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/description/)
- [2535. 数组元素和与数字和的绝对差](https://leetcode.cn/problems/difference-between-element-sum-and-digit-sum-of-an-array/description/)
- [2656. K 个元素的最大和](https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/description/)
- [2367. 算术三元组的数目](https://leetcode.cn/problems/number-of-arithmetic-triplets/description/)
- [27. 移除元素](https://leetcode.cn/problems/remove-element/description/)
- [1920. 基于排列构建数组](https://leetcode.cn/problems/build-array-from-permutation/description/)
- [1929. 数组串联](https://leetcode.cn/problems/concatenation-of-array/description/)
- [1431. 拥有最多糖果的孩子](https://leetcode.cn/problems/kids-with-the-greatest-number-of-candies/description/)
- [1991. 找到数组的中间位置](https://leetcode.cn/problems/find-the-middle-index-in-array/description/)
- [540. 有序数组中的单一元素](https://leetcode.cn/problems/single-element-in-a-sorted-array/description/)
- [119. 杨辉三角 II](https://leetcode.cn/problems/pascals-triangle-ii/description/)
- [3065. 超过阈值的最少操作数 I](https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-i/description/)
- [2951. 找出峰值](https://leetcode.cn/problems/find-the-peaks/description/)
- [2960. 统计已测试设备](https://leetcode.cn/problems/count-tested-devices-after-test-operations/description/)
- [2824. 统计和小于目标的下标对数目](https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/description/)
- [2859. 计算 K 置位下标对应元素的和](https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/description/)
- [2341. 数组能形成多少数对](https://leetcode.cn/problems/maximum-number-of-pairs-in-array/description/)
- [3158. 求出出现两次数字的 XOR 值](https://leetcode.cn/problems/find-the-xor-of-numbers-which-appear-twice/description/)
顺序表
杭州电子科技大学在线评测
杭州电子科技大学在线评测官网
2008 数值统计
#include <iostream>
using namespace std;int main()
{int n;while (cin >> n) {if (n == 0) {break;}int negative = 0;int zero = 0;int positive = 0;for (int i = 1; i <= n; i++) {double num;cin >> num;if (num < 0) {negative++;}if (num == 0) {zero++;}if (num > 0) {positive++;}}cout << negative << ' ' << zero << ' ' << positive << endl;}
}
使用顺序表实现
#include <iostream>
using namespace std;// 顺序表模板
#define eleType doublestruct SequentialList {eleType *elements;int size;int capacity;
};// 初始化顺序表
void initializeList(SequentialList* list, int capacity) {list->elements = new eleType[capacity];list->size = 0;list->capacity = capacity;
}// 销毁顺序表
void destroyList(SequentialList* list) {delete[] list->elements;
}// 获取顺序表的大小
eleType size(SequentialList* list) {return list->size;
}// 判断顺序表是否为空
eleType isEmpty(SequentialList* list) {return list->size == 0;
}// 顺序表的元素插入
eleType insert(SequentialList* list, int index, eleType element) {if (index < 0 || index > list->size) {throw std::invalid_argument("Invalid index");}if (list->size == list->capacity) {int newCapacity = list->capacity * 2;eleType* newElements = new eleType[newCapacity];for (int i = 0; i < list->size; ++i) {newElements[i] = list->elements[i];}delete[] list->elements;list->elements = newElements;list->capacity = newCapacity;}for (int i = list->size; i > index; i--) {list->elements[i] = list->elements[i - 1];}list->elements[index] = element;list->size++;
}// 顺序表的元素删除
void deleteElement(SequentialList* list, int index) {if (index < 0 || index >= list->size) {throw std::invalid_argument("Invalid index");}for (int i = index; i < list->size - 1; ++i) {list->elements[i] = list->elements[i + 1];}list->size--;
}// 顺序表寻找元素是否存在
eleType findElement(SequentialList* list, eleType element) {for (int i = 0; i < list->size; ++i) {if (list->elements[i] == element) {return i;}}return -1;
}// 获取元素
eleType getElement(SequentialList* list, int index) {if (index < 0 || index >= list->size) {throw std::invalid_argument("Invalid index");}return list->elements[index];
}// 修改元素
void updateElement(SequentialList* list, int index, eleType value) {if (index < 0 || index >= list->size) {throw std::invalid_argument("Invalid index");}list->elements[index] = value;
}int main()
{int n;while (cin >> n && n) {SequentialList s;initializeList(&s, 1);for (int i = 0; i < n; i++) {eleType x;cin >> x;insert(&s, i, x);}int pcnt = 0, zcnt = 0, ncnt = 0;for (int i = 0; i < size(&s); i++) {eleType element = getElement(&s, i);if (element > 1e-8) {pcnt++;}else if (element < -1e-8) {ncnt++;}else {zcnt++;}}cout << ncnt << ' ' << zcnt << ' ' << pcnt << endl;}
}
2014 青年歌手大奖赛_评委会打分
#include <iostream>
using namespace std;// 顺序表模板
#define eleType doublestruct SequentialList {eleType* elements;int size;int capacity;
};// 初始化顺序表
void initializeList(SequentialList* list, int capacity) {list->elements = new eleType[capacity];list->size = 0;list->capacity = capacity;
}// 销毁顺序表
void destroyList(SequentialList* list) {delete[] list->elements;
}// 获取顺序表的大小
int size(SequentialList* list) {return list->size;
}// 判断顺序表是否为空
eleType isEmpty(SequentialList* list) {return list->size == 0;
}// 顺序表的元素插入
void insert(SequentialList* list, int index, eleType element) {if (index < 0 || index > list->size) {throw std::invalid_argument("Invalid index");}if (list->size == list->capacity) {int newCapacity = list->capacity * 2;eleType* newElements = new eleType[newCapacity];for (int i = 0; i < list->size; ++i) {newElements[i] = list->elements[i];}delete[] list->elements;list->elements = newElements;list->capacity = newCapacity;}for (int i = list->size; i > index; i--) {list->elements[i] = list->elements[i - 1];}list->elements[index] = element;list->size++;
}// 顺序表的元素删除
void deleteElement(SequentialList* list, int index) {if (index < 0 || index >= list->size) {throw std::invalid_argument("Invalid index");}for (int i = index; i < list->size - 1; ++i) {list->elements[i] = list->elements[i + 1];}list->size--;
}// 顺序表寻找元素是否存在
eleType findElement(SequentialList* list, eleType element) {for (int i = 0; i < list->size; ++i) {if (list->elements[i] == element) {return i;}}return -1;
}// 获取元素
eleType getElement(SequentialList* list, int index) {if (index < 0 || index >= list->size) {throw std::invalid_argument("Invalid index");}return list->elements[index];
}// 修改元素
void updateElement(SequentialList* list, int index, eleType value) {if (index < 0 || index >= list->size) {throw std::invalid_argument("Invalid index");}list->elements[index] = value;
}int main()
{int n;while (cin >> n) {SequentialList s;initializeList(&s, n);eleType max_score = -100000000;eleType min_score = 100000000;eleType sum = 0;for (int i = 0; i < n; i++) {eleType num;cin >> num;insert(&s, i, num);}for (int i = 0; i < size(&s); i++) {if (getElement(&s, i) > max_score) {max_score = getElement(&s, i);}if (getElement(&s, i) < min_score) {min_score = getElement(&s, i);}sum += getElement(&s, i);}sum -= max_score;sum -= min_score;printf("%.2f\n", sum / (n - 2));}
}
Leetcode题目
LCP 01. 猜数字
class Solution {
public:int game(vector<int>& guess, vector<int>& answer) {int count = 0;for(int i = 0; i < 3; i++) {if(guess[i] == answer[i]) {count++;}}return count;}
};
LCP 06. 拿硬币
class Solution {
public:int minCount(vector<int>& coins) {int count = 0;for(int i = 0; i < coins.size(); i++) {count += (coins[i] + 1)/2;}return count;}
};
2057. 值相等的最小索引
class Solution {
public:int smallestEqual(vector<int>& nums) {for(int i = 0; i < nums.size(); i++) {if(i % 10 == nums[i]) {return i;}}return -1;}
};
485. 最大连续 1 的个数
class Solution {
public:int findMaxConsecutiveOnes(vector<int>& nums) {int count = 0;int end = 0;for(int i = 0; i < nums.size(); i++) {if(nums[i] == 1) {count = count + 1;if(count > end) {end = count;}} else {count = 0;}}return end;}
};
2006.差的绝对值为K的数对题目
class Solution {
public:int countKDifference(vector<int>& nums, int k) {int count = 0;for(int i = 0; i < nums.size(); i++) {for(int j = i + 1; j < nums.size(); j++) {if(abs(nums[i] - nums[j]) == k) {count++;}}}return count;}
};
1464. 数组中两元素的最大乘积
class Solution {
public:int maxProduct(vector<int>& nums) {int maxIndex = 0;for(int i = 0; i < nums.size(); i++) {if(nums[i] > nums[maxIndex]) {maxIndex = i;}}int secMaxIndex = -1;for(int i = 0; i < nums.size(); i++) {if(i != maxIndex) {if(secMaxIndex == -1 || nums[i] > nums[secMaxIndex]) {secMaxIndex = i;}}}return (nums[maxIndex] - 1) * (nums[secMaxIndex] - 1);}
};
2535. 数组元素和与数字和的绝对差
class Solution {
public:int differenceOfSum(vector<int>& nums) {int x = 0, y = 0;for(int i = 0; i < nums.size(); i++) {x += nums[i];while(nums[i]) {y += nums[i] % 10;nums[i] = nums[i] / 10;}}return abs(x - y);}
};
2656. K 个元素的最大和
class Solution {
public:int maximizeSum(vector<int>& nums, int k) {int count = 0;while(k--) {int maxIndex = 0;for(int i = 0; i < nums.size(); i++) {if(nums[i] > nums[maxIndex]) {maxIndex = i;}}count += nums[maxIndex];nums[maxIndex] += 1;}return count;}
};
2367. 算术三元组的数目
class Solution {
public:int arithmeticTriplets(vector<int>& nums, int diff) {int count = 0;for(int i = 0; i < nums.size(); i++) {for(int j = i + 1; j < nums.size(); j++) {if(nums[j] - nums[i] == diff) {for(int k = j + 1; k < nums.size(); k++) {if(nums[k] - nums[j] == diff) {count++;}}}}}return count;}
};
27. 移除元素
class Solution {
public:int removeElement(vector<int>& nums, int val) {int l = 0;int r = nums.size() - 1;while(l <= r) {if (nums[l] == val) {int temp = nums[l];nums[l] = nums[r];nums[r] = temp;r--;} else {l++;}}return r + 1;}
};
1920. 基于排列构建数组
class Solution {
public:vector<int> buildArray(vector<int>& nums) {vector<int> result;for(int i = 0; i < nums.size(); i++) {int ans = nums[nums[i]];result.push_back(ans);}return result;}
};
1929. 数组串联
class Solution {
public:vector<int> getConcatenation(vector<int>& nums) {vector<int> result;for(int i = 0; i < nums.size(); i++) {result.push_back(nums[i]);}for(int i = 0; i < nums.size(); i++) {result.push_back(nums[i]);}return result;}
};
1431. 拥有最多糖果的孩子
class Solution {
public:vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {vector<bool> result;for(int i = 0; i < candies.size(); i++) {int maxIndex = 0;candies[i] += extraCandies;for(int j = 0; j < candies.size(); j++) {if(candies[j] > candies[maxIndex]) {maxIndex = j;}}if(candies[i] == candies[maxIndex]) {result.push_back(true);} else {result.push_back(false);}candies[i] -= extraCandies;}return result;}
};
1991. 找到数组的中间位置
class Solution {
public:int findMiddleIndex(vector<int>& nums) {for(int i = 0; i < nums.size(); i++) {int l = 0;int r = 0;for(int j = 0; j < i; j++) {l += nums[j];}for(int j = i + 1; j < nums.size(); j++) {r += nums[j];}if (l == r) {return i;}}return -1;}
};
540. 有序数组中的单一元素
class Solution {
public:int singleNonDuplicate(vector<int>& nums) {for(int i = 0; i < nums.size(); i++) {if(i == 0) {if(nums.size() == 1 || nums[i] != nums[i + 1]) {return nums[i];}} else if(i == nums.size() - 1) {if(nums[i] != nums[i - 1]) {return nums[i];}} else {if(nums[i - 1] != nums[i] && nums[i] != nums[i + 1]) {return nums[i];}}}return 0;}
};
119. 杨辉三角 II
class Solution {
public:vector<int> getRow(int rowIndex) {int nums[34][34];for(int i = 0; i <= rowIndex; i++) {for(int j = 0; j <= i; j++) {if(j == 0 || i == j) {nums[i][j] = 1;} else {nums[i][j] = nums[i-1][j] + nums[i-1][j-1];}}}vector<int> result;for(int j = 0; j <= rowIndex; j++) {result.push_back(nums[rowIndex][j]);}return result;}
};
3065. 超过阈值的最少操作数 I
class Solution {
public:int minOperations(vector<int>& nums, int k) {int count = 0;for(int i = 0; i < nums.size(); i++) {if(nums[i] < k) {count++;}}return count;}
};
2951. 找出峰值
class Solution {
public:vector<int> findPeaks(vector<int>& mountain) {vector<int> result;for(int i = 1; i < mountain.size() - 1; i++) {if((mountain[i] > mountain[i - 1]) && (mountain[i] > mountain[i + 1])) {result.push_back(i);}}return result;}
};
2960. 统计已测试设备
class Solution {
public:int countTestedDevices(vector<int>& batteryPercentages) {int count = 0;for(int i = 0; i < batteryPercentages.size(); i++) {if(batteryPercentages[i] > 0) {count++;for(int j = i + 1; j < batteryPercentages.size(); j++) {batteryPercentages[j] = max(0, batteryPercentages[j] - 1);}}}return count;}
};
2824. 统计和小于目标的下标对数目
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;}
};
2859. 计算 K 置位下标对应元素的和
class Solution {
public:int sumIndicesWithKSetBits(vector<int>& nums, int k) {int sum = 0;for(int i = 0; i < nums.size(); i++) {int num = i;int count = 0;while(num) {if(num & 1) {count++;}num >>= 1;}if(count == k) {sum += nums[i];}}return sum;}
};
2341. 数组能形成多少数对
class Solution {
public:vector<int> numberOfPairs(vector<int>& nums) {int count = 0;bool judge[100] = {0};for(int i = 0; i < nums.size(); i++) {for(int j = 0; j < i; j++) {if(judge[j] == true) {continue;}if(nums[i] == nums[j]) {judge[i] = judge[j] = true;count++;break;}}}return {count, (int)nums.size() - 2 * count};}
};
3158. 求出出现两次数字的 XOR 值
class Solution {
public:int duplicateNumbersXOR(vector<int>& nums) {int count = 0;long visited = 0;for(int i = 0; i < nums.size(); i++) {int x = nums[i];if(visited & ((long)1<<x)) {count ^= x;} else {visited |= ((long)1<<x);}}return count;}
};