【字节笔试，算法-简单->困难】leetcode 1529灯泡开关 + POJ 1830开关问题，从搜索到高斯消元法
目录
字节笔试题，原题忘记了，但是稍微有些区别
题目 大致意思就是反转。 实现核心就是利用亮点：
- 开关本身顺序对结果没有影响
- 所有的1都由翻转本身得到。
class Solution {
public:
int minFlips(string target) {
//时序无关性，因此所有的1都是反转得到的
//从头开始枚举1。字符串不翻转，反转自身
int number = 0;
bool flag = true;//true，看1则翻转；false，看0则翻转
for(int i =0;i<target.length();i++){
if(flag && target[i]=='1'){
flag = !flag;
number++;
}else if(!flag && target[i]=='0'){
flag = !flag;
number++;
}
}
return number;
}
};扩展问题是今天碰到的字节笔试的第三题，给定一个长度为n的环状数组，按动一次开关可以改变自己和左右的状态（0->1/1->0）。初始全部为0，问如何得到1。 这个问题比较类似POJ1830，相当于自动加上了开关变化的限制。
题目类型说明：
这道题目居然是道异或方程组的高斯消元问题。
核心原理倒是不难，现在有原状态b0和目标状态b1，就可以得到状态改变量b
例如对于原始例子而言，b_0=[0,0,0,0]，b_1=[1,1,1,1]，则b = b_0^b_1=[1,1,1,1]，其中b[i]表示第i个灯的状态
整个问题可以建模成A*x=b，其中A矩阵为开关i与j之间的影响，A[i][j]=1表示开关j会对开关i产生影响。x向量表示开关i的操作，1表示开，0表示关。
显然，x[i]对应在A矩阵中为第j列，x[i]=1时第j列被激活，以字节拿到题目为例，相当于A[j][j]=A[j-1][j]=A[j+1][j]=1，一旦j列被激活就会对周围和自己产生影响。
将A转化为分块矩阵A=[a1,a2,...,an]，则变为一个异或方程组的消元问题，使用高斯消元法即可求解。
- 线性方程组写成增广矩阵形式
- 找主元，对增广矩阵进行行行变换；对元素，在第i列中及以下选取绝对值最大的元素，将所有元素中最大的所在的行与第i行进行交换.
- 消元，采用高斯消元法使得新得到的第i行以下的元素均为零
- 重复上述过程，直到得到下三角阵
- 对上三角阵回代求解。
具体描述普通高斯消元伪代码
给定N行N+1列的增广矩阵aug
第一步、循环，i从0->N-1，枚举主元
1.1 在循环中，j从i到N-1，寻找第i列的最大主元。设最大主元在第k行
1.2 将最大主元从k行换到i行
1.3 消元，将i行的最大主元消去i+1->N-1的所有对应元素（i列到N-1列）
如此，得到上三角阵
回代求解
从最右下角出发，求解出xn，然后从第N列反向计算回前面全部。
对于方阵N，时间复杂度为O(N^2)
如果行数小于列数，即未知数比方程多，则不可能有解。
如果行数等于列数，即最终未知数等于方程，有唯一解。
如果行数大于列数，方程比未知数多，有无穷解。#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
///高斯消元模板
const int Max_M = 35;
const int Max_N = 35;
int Aug[Max_M][Max_N];
int m,n; ///m个方程,n个未知数
int Gauss()
{
int i,j;
int max_r,row,col;
for(col=0,row=0; row<m && col<n; row++,col++)
{
max_r = row;
for(i = row+1; i < m; i++)
{
if(Aug[i][col] > Aug[max_r][col])
max_r = i;
}
if(max_r != row)
{
for(j = row; j < n+1; j++)
swap(Aug[max_r][j],Aug[row][j]);
}
if(Aug[row][col]==0)
{
row--;
continue;
}
for(i = row+1; i < m; i++)
{
if(Aug[i][col]==0)
continue;
for(j = col; j < n+1; j++)
Aug[i][j] ^= Aug[row][j];
}
}
for(i = row; i < m; i++)
{
if(Aug[i][col] != 0)
return -1;
}
return 1<<(n-row); ///n-row个变元,只有0/1两种取值
}
///end
int main()
{
int i,j;
int t;
int nn;
int start[30],end[30];
scanf("%d",&t);
while(t--)
{
m = n = 0;
memset(Aug,0,sizeof(Aug));
scanf("%d",&nn);
for(i = 0; i < nn; i++)
scanf("%d",&start[i]);
for(i = 0; i < nn; i++)
scanf("%d",&end[i]);
while(true)
{
scanf("%d %d",&i,&j);
if(!i&&!j)
break;
Aug[j-1][i-1] = 1;
}
n = m = nn;
for(i = 0; i < n; i++)
{
Aug[i][i] = 1;
Aug[i][n] = start[i]^end[i];
}
int ret = Gauss();
if(ret==-1)
printf("Oh,it's impossible~!!\n");
else
printf("%d\n",ret);
}
return 0;
}