changgyhub/notes

Personal Notes

notes's Issues

优先队列中堆的使用

首先非常感谢笔记的整理！对我帮助很大！
在algorithms-and-data-structures里优先队列一节，用数组表示堆时，应该将0号位空着，即top函数应返回heap[1]，pop时也应该将末尾元素放入heap[1]，然后sink(1)

动态规划416题第一个解答有一点问题

动态规划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 第k大的数

感谢作者无私分享~
编号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; 
    
    
}

};