小程序制作软件有哪些,优化关键词具体要怎么做,网站开发整套资料,网站开发案列1--数据流中的中位数#xff08;41#xff09; 主要思路#xff1a; 维护两个优先队列#xff0c;Q1大数优先#xff0c;存储比中位数小的数#xff1b;Q2小数优先#xff0c;存储比中位数大的数#xff1b; 当存储的数为偶数时#xff0c;Q1.size() Q2.size(), 中位…1--数据流中的中位数41 主要思路 维护两个优先队列Q1大数优先存储比中位数小的数Q2小数优先存储比中位数大的数 当存储的数为偶数时Q1.size() Q2.size(), 中位数为(Q1.top() Q2.top()) / 2.0 当存储的数为奇数时Q2.size() Q1.size() 1, 中位数为 Q2 的队头元素 因此插入元素要确保Q2.size() Q1.size(); 同时插入新元素时要先插入到另一个队列中确保有序取队头元素再插入到目的元素中 #include iostream
#include queue
#include algorithmclass MedianFinder {
public:MedianFinder() {}void addNum(int num) {// Q1大数优先存储比中位数小的数// Q2小数优先存储比中位数大的数// 当存储的数为偶数时Q1.size() Q2.size(), 中位数为(Q1.top() Q2.top()) / 2.0// 当存储的数为奇数时Q2.size() Q1.size() 1, 中位数为 Q2 的队头元素// 因此插入元素要确保Q2.size() Q1.size(); // 同时插入新元素时要先插入到另一个队列中确保有序取队头元素再插入到目的元素中if(Q1.size() Q2.size()){Q1.push(num);int top Q1.top();Q1.pop();Q2.push(top);}else{Q2.push(num);int top Q2.top();Q2.pop();Q1.push(top);}}double findMedian() {if(Q1.size() Q2.size()){return (Q1.top() Q2.top()) / 2.0;}else{return Q2.top()*1.0;}}
private:std::priority_queueint, std::vectorint, std::lessint Q1; // 大数优先级高队头std::priority_queueint, std::vectorint, std::greaterint Q2; // 小数优先级高队头
};int main(int argc, char *argv[]){MedianFinder S1;S1.addNum(1);S1.addNum(4);S1.addNum(2);S1.addNum(3);double Res S1.findMedian();std::cout Res std::endl;return 0;
}2--连续子数组的最大和42 主要思路 使用动态规划解决 #include iostream
#include vectorclass Solution {
public:int maxSubArray(std::vectorint nums) {int len nums.size();if(len 0) return 0;std::vectorint dp;dp.push_back(nums[0]);int max nums[0];for(int i 1; i len; i){if(dp[i - 1] 0){dp.push_back(dp[i-1] nums[i]);}else{dp.push_back(nums[i]);}if (dp[i] max) max dp[i];}return max;}
};int main(int argc, char *argv[]){Solution S1;std::vectorint test {-2, 1, -3, 4, -1, 2, 1, -5, 4};int Res S1.maxSubArray(test);std::cout Res std::endl;return 0;
}3--1~n中整数中 1 出现的次数43 主要思路视频讲解和题解 规律题当固定住其中 1 位时计算其出现1的次数分别统计个位、百位、千位等数字出现1的个数并求和相加即可 #include iostream
#include vectorclass Solution {
public:int countDigitOne(int n) {long long bit 1;long long sum 0;while(bit n){long long cur n / bit % 10;long long low n % bit;long long high n / bit / 10;if(cur 0){sum high * bit;}else if(cur 1){sum high*bit low 1;}else{sum (high1)*bit;}bit bit*10;}return (int)sum;}
};int main(int argc, char *argv[]){Solution S1;int test 12;int sum S1.countDigitOne(test);std::cout sum std::endl;return 0;
}4--数字序列中某一位的数字44 主要思路视频讲解 规律题先判断 n 属于哪个范围的数个位、百位、千位等再计算 n 具体属于哪一个数最后计算 n 属于某一个数的具体哪一位返回即可 #include iostream
#include vector
#include cmathclass Solution {
public:int findNthDigit(int n) {if(n 0) return 0;long bit 1; // 1 10 100int i 1; // 1 2 3long count 9; // 9 180 2700 // 范围内字符的个数 // 确定属于哪一个范围while(count n){n n - count;i i 1;bit bit * 10;count bit * i * 9;}// 确定属于哪一个数long num bit (n-1) / i;// 确定具体哪一位int index (n - 1) % i 1;int res (int)(num / pow(10, i - index)) % 10;return res;}
};int main(int argc, char *argv[]){Solution S1;int test 19;int res S1.findNthDigit(test);std::cout res std::endl;return 0;
}5--把数组排成最小的数45 主要思路 拼接字符串 xy yx, 则 xy 拼接字符串 xy yx, 则 xy 使用快排对字符串数组进行排序要确保由字符串数组组成的数最小即strs[0]strs[1]strs[2]...最小必须连续满足strs[0] strs[1], strs[1] strs[2]; #include iostream
#include vector
#include stringclass Solution {
public:std::string minNumber(std::vectorint nums) {std::string Res;if (nums.size() 0) return Res; std::vectorstd::string strs;// 数字 - stringfor(int item : nums){strs.push_back(std::to_string(item));}quickSort(strs, 0, nums.size()-1);for(std::string str : strs){Res.append(str);}return Res;}void quickSort(std::vectorstd::string strs, int left, int right){if (left right) return;std::string pivot strs[left];int i left, j right;while(i j){while(i j strs[j] pivot pivot strs[j]) j--; // 拼接字符串 xy yx, 则 xystrs[i] strs[j];while(i j strs[i] pivot pivot strs[i]) i; // 拼接字符串 xy yx, 则 xystrs[j] strs[i]; }strs[i] pivot;quickSort(strs, left, i-1);quickSort(strs, i1, right);}
};int main(int argc, char *argv[]){Solution S1;std::vectorint test {3, 30, 34, 5, 9};std::string Res S1.minNumber(test);std::cout Res std::endl;return 0;
}
6--把数字翻译成字符串46 主要思路 基于动态规划定义状态和转移方程dp[i] 代表以 x_i 为结尾的数字的翻译方案数量 #include iostreamclass Solution {
public:int translateNum(int num) {if(num 10) return 1;int dp_1 1;int dp_2 1;int dp;while(num ! 0){int tmp ((num/10) % 10) * 10 (num % 10);if(9 tmp tmp 26){dp dp_1 dp_2;}else{dp dp_1;}dp_2 dp_1;dp_1 dp;num num / 10;}return dp;}
};int main(int argc, char *argv[]){Solution S1;int num 12258;int Res S1.translateNum(num);std::cout Res std::endl;return 0;
}
7--礼物的最大价值47
