Schriefer
张书翌
2021-05-11 00:17
采纳率: 77.8%
浏览 56

为什么这个程序会报错?

#include<vector>
#include<list>
#include<string>
#include<iostream>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<utility>
#include<unordered_map>
#include<unordered_set>
using namespace std;

/*
题目是Leetcode算法题(1655,分配不同整数)
报错表述:can't dereference value-initialized vector iterator 
程序在我标明处崩了,但我不知道为什么?
但暂且我可以确定,if_dte()这个函数是没有问题的
*/

bool if_dte(vector<int> nums, int way, int demend) {
        set<int> st;
        multiset<int> set;

        for (int i = 0; i < nums.size(); i++) {
            if ((1 << i & way) == 0) continue;
            set.insert(nums[i]);
            st.insert(nums[i]);
        }

        vector<int> tmp;
        for (auto it = st.begin(); it != st.end(); it++) {
            tmp.push_back(set.count(*it));
        }

        return (*max_element(tmp.begin(), tmp.end())) >= demend;
    }

    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        int n = nums.size();
        
        vector<vector<bool>> dp(quantity.size(), vector<bool>(1 << n, false));

        system("pause");
        dp[0][0] = if_dte(nums, 3, quantity[0]);
        system("pause");
        //我知道问题就出在这个循环,但不知道为什么真的太奇怪了///////////////////////////////////////////////////
        for (int j = 0; j < (1 << n); j++) {
            dp[0][j] = if_dte(nums, j, quantity[0]);
        }
        system("pause");

        for (int j = 0; j < (1 << n); j++) cout << "dp[0][" << j << "]=" << dp[0][j] << endl;

        for (int i = 0; i < quantity.size(); i++) {
            for (int j = 0; j < (1 << n); j++) {
                dp[i][j] = false;
                for (int s = 0; s <= j; s++) {
                    if ((s | j) != j) continue;
                    dp[i][j] == dp[i][j] || (dp[i - 1][j - s] && if_dte(nums, s, quantity[i]));
                }
            }
        }


        return dp[quantity.size() - 1][1 << n];

    }

int main() {


	vector<int> t1 = { 1,2,2,4,4,4 };
	vector<int> t2 = { 2,1 };
	cout << s.canDistribute(t1, t2);
	return 0;
}



  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

5条回答 默认 最新

  • benbenli
    benbenli 2021-05-11 02:16
    已采纳

     

    问题在函数if_dte里。我加了一些打印语句跟踪,在第二次调用改函数的时候vector tmp是空的,但是函数返回语句求最大值后试图dereference出错。可以先检测是否为空,为空时返回false:  return tmp.size() > 0 && (*max_element(tmp.begin(), tmp.end())) >= demend;。

    另外函数 canDistribute返回语句 return dp[quantity.size() - 1][1 << n] 也会数组越界,应该 return dp[quantity.size() - 1][(1 << n) -1]; 

    #include<vector>
    #include<list>
    #include<string>
    #include<iostream>
    #include<numeric>
    #include<set>
    #include<algorithm>
    #include<map>
    #include<utility>
    #include<unordered_map>
    #include<unordered_set>
    using namespace std;
    /*
    题目是Leetcode算法题(1655,分配不同整数)
    报错表述:can't dereference value-initialized vector iterator 
    程序在我标明处崩了,但我不知道为什么?
    但暂且我可以确定,if_dte()这个函数是没有问题的
    */
    bool if_dte(vector<int> nums, int way, int demend) {
            cout << "if_dte begin: way = " << way << ", demend = " << demend << endl;
            set<int> st;
            multiset<int> set;
            for (int i = 0; i < nums.size(); i++) {
                cout << "if_dte: i = " << i << endl;
                if ((1 << i & way) == 0) continue;
                cout << "inserting nums[" << i <<"] " << nums[i] << " into both set and mulset" << endl;
                set.insert(nums[i]);
                st.insert(nums[i]);
            }
            cout << "if_dte: vector tmp" << endl;
            vector<int> tmp;
            for (auto it = st.begin(); it != st.end(); it++) {
                cout << "*it = " << *it << ", set.count(*it): " << set.count(*it) << endl;
                tmp.push_back(set.count(*it));
            }
            cout << "tmp.size(): " << tmp.size() << endl;
            return (*max_element(tmp.begin(), tmp.end())) >= demend;
        }
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
            int n = nums.size();
            vector<vector<bool>> dp(quantity.size(), vector<bool>(1 << n, false));
            cout << "dp size: " << quantity.size() << ", " << (1 << n) << endl;
            //system("pause");
            dp[0][0] = if_dte(nums, 3, quantity[0]);
            //system("pause");
            //我知道问题就出在这个循环,但不知道为什么真的太奇怪了///////////////////////////////////////////////////
            for (int j = 0; j < (1 << n); j++) {
                cout << "Accessing dp[0][" << j << "]" << endl;
                dp[0][j] = if_dte(nums, j, quantity[0]);
            }
            system("pause");
            for (int j = 0; j < (1 << n); j++) cout << "dp[0][" << j << "]=" << dp[0][j] << endl;
            for (int i = 0; i < quantity.size(); i++) {
                for (int j = 0; j < (1 << n); j++) {
                    cout << "setting dp[" << i << "][" << j << "] as false" << endl;
                    dp[i][j] = false;
                    for (int s = 0; s <= j; s++) {
                        if ((s | j) != j) continue;
                        cout << "setting dp[" << i << "][" << j << "] or" << endl;
                        cout << "reading dp[" << i - 1 << "][" << j - s << "]" << endl;
                        dp[i][j] == dp[i][j] || (dp[i - 1][j - s] && if_dte(nums, s, quantity[i]));
                    }
                }
            }
     
            cout << "returning dp[" << quantity.size() - 1 << "][" << (1 << n) - 1 << "]" << endl;
            return dp[quantity.size() - 1][(1 << n) - 1];
        }
    int main() {
     
    	vector<int> t1 = { 1,2,2,4,4,4 };
    	vector<int> t2 = { 2,1 };
    	cout << canDistribute(t1, t2);
    	return 0;
    }
     
    // Output
    dp size: 2, 64                                                                                                                                                                       
    if_dte begin: way = 3, demend = 2                                                                                                                                                    
    if_dte: i = 0                                                                                                                                                                        
    inserting nums[0] 1 into both set and mulset                                                                                                                                         
    if_dte: i = 1                                                                                                                                                                        
    inserting nums[1] 2 into both set and mulset                                                                                                                                         
    if_dte: i = 2                                                                                                                                                                        
    if_dte: i = 3                                                                                                                                                                        
    if_dte: i = 4                                                                                                                                                                        
    if_dte: i = 5                                                                                                                                                                        
    if_dte: vector tmp                                                                                                                                                                   
    *it = 1, set.count(*it): 1                                                                                                                                                           
    *it = 2, set.count(*it): 1                                                                                                                                                           
    tmp.size(): 2                                                                                                                                                                        
    if_dte finish: max_element(tmp.begin(), tmp.end()) = 1, demend = 2                                                                                                                   
    Accessing dp[0][0]                                                                                                                                                                   
    if_dte begin: way = 0, demend = 2                                                                                                                                                    
    if_dte: i = 0                                                                                                                                                                        
    if_dte: i = 1                                                                                                                                                                        
    if_dte: i = 2                                                                                                                                                                        
    if_dte: i = 3                                                                                                                                                                        
    if_dte: i = 4                                                                                                                                                                        
    if_dte: i = 5                                                                                                                                                                        
    if_dte: vector tmp                                                                                                                                                                   
    tmp.size(): 0                                                                                                                                                                        
    Segmentation fault (core dumped)            
    点赞 评论
  • technologist_32
    CSDN专家-Time 2021-05-11 00:19

    vector指针溢出了。

    点赞 评论
  • Schriefer
    张书翌 2021-05-11 09:30

    而且我已经把所有值初始设定为false

     

    点赞 评论
  • QA_Assistant
    有问必答小助手 2021-05-11 11:51

    您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps:问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632

    点赞 评论
  • QA_Assistant
    有问必答小助手 2021-05-11 17:03

    非常感谢您使用有问必答服务,为了后续更快速的帮您解决问题,现诚邀您参与有问必答体验反馈。您的建议将会运用到我们的产品优化中,希望能得到您的支持与协助!

    速戳参与调研>>>https://t.csdnimg.cn/Kf0y

    点赞 评论

相关推荐