資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中查詢使兩個矩陣相等的變換次數
在這個問題中，我們得到了兩個相同大小的矩陣mat1[][]和mat2[][]。我們的任務是找到使兩個矩陣相等的變換次數。
矩陣變換如下：
選擇兩個矩陣中的任意一個矩陣。
從矩陣中選擇一行或一列。
將所選行或列的所有元素加1。
讓我們舉個例子來理解這個問題：
輸入
mat1[][] = {{1 2}
{2 1}}
mat1[][] = {{2 3}
{4 3}}輸出
3
解釋
1 2 => 2 2 => 2 3 => 2 3 2 1 => 3 1 => 3 2 => 4 3
解決方案方法
解決這個問題的一個簡單方法是找出變換是否可行。為此，我們需要檢查：
if( mat[i][j] - mat[i][0] - mat[0][j] + mat[0][0] != 0 )
如果沒有，則不存在解決方案。
現在，如果變換是可能的，我們將計算行和列的變換次數。
程式說明了我們解決方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int countTransformationReq(int mat1[][MAX], int mat2[][MAX],
int m, int n) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
mat1[i][j] -= mat2[i][j];
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
if (mat1[i][j] - mat1[i][0] - mat1[0][j] +
mat1[0][0] != 0)
return -1;
int trxCount = 0;
for (int i = 0; i < n; i++)
trxCount += abs(mat1[i][0]);
for (int j = 0; j < m; j++)
trxCount += abs(mat1[0][j] - mat1[0][0]);
return (trxCount);
}
int main() {
int mat1[MAX][MAX] = { {1, 2}, {2, 1}};
int mat2[MAX][MAX] = { {2, 3}, {4, 3}};
cout<<"The number of transformation to make the teo
maxtrces equal are "<<countTransformationReq(mat1, mat2, 2,
2) ;
return 0;
}輸出
The number of transformation to make the teo maxtrces equal are 3
高效方法
解決這個問題的一個更有效的方法是使用握手定理。
我們將建立一個temp[]陣列來計算陣列模數中0和1的出現次數。然後返回計數值。
程式說明了我們解決方案的工作原理：
示例
#include<iostream>
using namespace std;
int countEvenSumSubArray(int arr[], int n){
int temp[2] = {1, 0};
int count = 0, sum = 0;
for (int i=0; i<=n-1; i++){
sum = ( (sum + arr[i]) % 2 + 2) % 2;
temp[sum]++;
}
count += (temp[0]*(temp[0]-1)/2);
count += (temp[1]*(temp[1]-1)/2);
return (count);
}
int main(){
int arr[] = {2, 1, 4, 2};
int n = sizeof (arr) / sizeof (arr[0]);
cout<<"The count of Subarrays with even sum is "<<countEvenSumSubArray(arr, n);
return (0);
}輸出
The count of Subarrays with even sum is 4
更新於：2021年3月15日
瀏覽量：158
廣告