文章目錄

861. 翻轉(zhuǎn)矩陣后的得分
題目大意： 只有值為0或1的二維數(shù)組，可以進(jìn)行每行或者每列的01反轉(zhuǎn)，每行中的0全部變成1，與此同時(shí)該行的1全部變成0. 若把每一行看作1個(gè)二進(jìn)制數(shù)，求經(jīng)過翻轉(zhuǎn)后，這個(gè)二維數(shù)組構(gòu)成的最大的數(shù)是多少？用10進(jìn)制表示。

這題的疑問點(diǎn)：

如何將二進(jìn)制轉(zhuǎn)化為十進(jìn)制？

解答： 只需要將數(shù)字1左移多少位，然后累加到res變量中。比如 二進(jìn)制10轉(zhuǎn)化為十進(jìn)制就是 1<<1(1左移1位)得到結(jié)果十進(jìn)制2.

本題的策略：貪心。

要使得值最大，那么需要每行的左邊1越多越好。所以我們可以先翻轉(zhuǎn)行，令每行第一個(gè)元素全為1（原來是0的那么該行需要翻轉(zhuǎn)，該列稱之為第0列），然后從第1列開始按列翻轉(zhuǎn)，使得該列中1最多，這樣，最后得到的就是最大的數(shù)。

由于是計(jì)數(shù)，所以只需要統(tǒng)計(jì)每列的0的個(gè)數(shù)或者1的個(gè)數(shù)，取兩者最大值，乘以權(quán)值即代表該列能提供的最大值。

這里需要注意的是 如果該行反轉(zhuǎn)過，那么統(tǒng)計(jì)0或者1要相反。

ac代碼

class Solution { public:int matrixScore(vector<vector<int>>& A) {int row=A.size(),col= A[0].size();int res=0;//保存最終結(jié)果int num=0; //記錄每一列0或者1最大的個(gè)數(shù)res+=row*(1<<(col-1)); //第一列全1for(int j=1;j<col;j++){//從列開始遍歷for(int i=0;i<row;i++){if(A[i][0]==1){ //該行若未翻轉(zhuǎn)if(A[i][j]) num++; //統(tǒng)計(jì)1的個(gè)數(shù)}else{ //該行已翻轉(zhuǎn)if(!A[i][j]) num++; //統(tǒng)計(jì)0的個(gè)數(shù)（即翻轉(zhuǎn)后1的個(gè)數(shù)）}}num=max(num,row-num); //取每列0或1的最大個(gè)數(shù)res+=num*(1<<(col-1-j)); //計(jì)算十進(jìn)制的數(shù)值num=0; //每經(jīng)過一列需要num置零}return res;} };

總結(jié)

以上是生活随笔為你收集整理的Leetcode861翻转矩阵后的得分(C++题解)：贪心的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。