leetcode1583统计不开心的朋友

港控/mmm° 2022-09-05 00:08 107阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 3]  
思路

1.  所有的朋友都配对了，没有剩下的，所以用的数组都是满的。
2.  整理题目不开心的要求是`对于配对的(x,y)(u,v) : (x,u)>(x,y) and (u,x)>(u,v)`也就是`u`在`x`的好感度序号比`y`小，这样才可能找到`u`，而对于`u`，`x`的好感度序号要小于`v`。
3.  分析根据序号有关，那么`match[x]=y;order[x][y] = k;`一个是配对的序号，一个是`y`在`x`处的好感度排名，而`preference[x][k] = y`

代码

#include<stdio.h>
    #include<string.h>
    int unhappyFriends(int n, int** preferences, int preferencesSize, int* preferencesColSize, int** pairs, int pairsSize, int* pairsColSize){ 
        int i=0,j=0;
        int match[pairsSize];
        memset(match,-1,sizeof(match));
        for(i=0;i<pairsSize;i++){ 
            match[*((int*)pairs+i*(*pairsColSize)+0)] = *((int*)pairs+i*(*pairsColSize)+1); 
            match[*((int*)pairs+i*(*pairsColSize)+1)] = *((int*)pairs+i*(*pairsColSize)+0);
        }
        int order[n][n];
        memset(order,-1,sizeof(order));
        for(i=0;i<preferencesSize;i++){ 
            for(j=0;j<*preferencesColSize;j++){ 
                order[i][*((int*)preferences+i*(*preferencesColSize)+j)] = j; 
            }
        }
    
        int unhappy = 0;
    
        int x,y,u,v;
        for(x=0;x<n;x++){ 
            y = match[x];
            int index = order[x][y];
            for(i=0;i<=index;i++){ //序号排在y之前的都可能是u
                u = preferences[x][i];
                v = match[u];//对于其配对的v
                if(order[u][x]<order[u][v]){ //好感度序号排位x在v之前
                    unhappy++;
                    break;
                }
            }
        }
    
        return unhappy;
        
    }

leetcode代码

int unhappyFriends(int n, int** preferences, int preferencesSize, int* preferencesColSize, int** pairs, int pairsSize, int* pairsColSize){ 
      int i=0,j=0;
        int match[n];
        memset(match,-1,sizeof(match));
        for(i=0;i<pairsSize;i++){ 
            match[pairs[i][0]] = pairs[i][1]; 
            match[pairs[i][1]] = pairs[i][0];
        }
        int order[n][n];
        memset(order,-1,sizeof(order));
        for(i=0;i<preferencesSize;i++){ 
            for(j=0;j<*preferencesColSize;j++){ 
                order[i][preferences[i][j]] = j; 
            }
        }
    
        int unhappy = 0;
    
        int x,y,u,v;
        for(x=0;x<n;x++){ 
            y = match[x];
            int index = order[x][y];
            for(i=0;i<=index;i++){ 
                u = preferences[x][i];
                v = match[u];
                if(order[u][x]<order[u][v]){ 
                    unhappy++;
                    break;
                }
            }
        }
    
        return unhappy;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/10c7969d0a534bb5a9993f6deac30280.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/789b49df8fa343d7aade21358e5e01d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 2]: /images/20220829/9649658f32f34c88a882bbfed9dd1e20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 3]: /images/20220829/eb66f17d3ba246f4bf324bac98d08975.png