changgyhub / notes Goto Github PK
View Code? Open in Web Editor NEWPersonal Notes
Personal Notes
首先非常感谢笔记的整理!对我帮助很大!
在algorithms-and-data-structures里优先队列一节,用数组表示堆时,应该将0号位空着,即top函数应返回heap[1],pop时也应该将末尾元素放入heap[1],然后sink(1)
动态规划416题在leetcode上会有一个点过不去,个人认为原因是在于j只是从nums[i-1]开始,nums[i-1]之前的没有照抄上一行。修改后的代码如下。
class Solution {
public:
bool canPartition(vector& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % 2 == 1){
return false;
}
int target = sum/2;
int n = (int)nums.size();
vector<vector> dp(n+1, vector(target+1, false));
for(int i = 0; i<=n; i++){
dp[i][0] = true;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= target; j++){
if(j < nums[i-1]){
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
}
};
感谢作者无私分享~
编号215 书中代码可能存在超时(含较多相等数字的时候)
参考leetcode题解,修改如下:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int mid;
int target_k = nums.size()-k;
int l=0,r=nums.size()-1;
while(l<r){
mid = quickselect(nums,l,r);
//cout<<"mid:"<<mid<<endl;
if(mid<target_k) l=mid+1;
else if(mid>target_k) r=mid-1;
else return nums[mid];
}
return nums[l];
}
int quickselect(vector<int> &nums,int l,int r){
//cout<<"l:"<<l<<" r:"<<r<<endl;
int i=l,j=r+1;
while(i<j){
do {i++;
//cout<<"while_i:"<<i<<endl;
} while(i<=r&&nums[i]<nums[l]);
do {j--;
//cout<<"while_j:"<<j<<endl;
} while(j>=0&&nums[j]>nums[l]);
if(i<j) swap(nums[i],nums[j]);
}
//cout<<i<<" "<<j<<endl;
swap(nums[l],nums[j]);
// show_nums(nums);
return j;
}
};
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.