阅读量:0
文章目录
- 顺序表
- 杭州电子科技大学在线评测
- 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 double struct 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 double struct 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; } }; 