今天的比赛考固定算法的不多，只有最后一道动态规划的题目稍难一点。其他的题目花些心思，也可以想出来。在面试中如果考察一个人的脑力，前三道题目比较好。都能答出来一些，但是也有优化的空间。
第三题用了很多时间，导致第四题时间都不够了。做比赛和工程还是有差别，应该有思路就敲代码，先把题目过了再说，一些细节不用考虑太多。有些地方不优化也可以过掉。但是在工程上就要考究些，因为代码是在服务器24小时跑，能优化一点点，在海量服务中也能节省很多计算资源。
下面是详细的题解和思考。
比赛的地址 Weekly Contest 139
https://leetcode-cn.com/contest/weekly-contest-139
1. 字符串的最大公因子 题目：
字符串的最大公因子(Greatest Common Divisor of Strings)
地址：
https://leetcode-cn.com/contest/weekly-contest-139/problems/greatest-common-divisor-of-strings/
题意：
对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
思路：
返回的公共字符串X就是经过n1次重复为Str1，经过n2次重复为Str2的最长字符串。
那么X一定是S和T的公共前缀字符串的子串。
先计算出S和T的公共前缀字符串str，然后从str的最长前缀到最短前缀依次判断，是否满足能「除尽」str1和str2。
要求的X的字符串长度，一定是str1和str2长度的公约数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : bool isSubStr (string & str1, string & str) { int len1 = str1. size (); int len2 = str.size (); if (len1%len2!=0 ) return false ; int repeat = len1/len2; string tmp; while (repeat--) { tmp += str; } return tmp == str1; } string gcdOfStrings (string str1, string str2) { string str; int len1 = str1. size (); int len2 = str2. size (); for (int i = 0 ; i < len1 && i < len2; ++i) { if (str1[i] == str2[i]) { str.push_back (str1[i]); } else break ; } int len = str.size (); while (len > 0 ) { bool b1 = isSubStr (str1, str); bool b2 = isSubStr (str2, str); if (b1 && b2) return str; str.pop_back (); len --; } return str; } };
2. 按列翻转得到最大值等行数 题目：
按列翻转得到最大值等行数(Flip Columns For Maximum Number of Equal Rows)
地址：
https://leetcode-cn.com/contest/weekly-contest-139/problems/flip-columns-for-maximum-number-of-equal-rows/
题意：
给定由若干 0 和 1 组成的矩阵 matrix，从中选出任意数量的列并翻转其上的 每个 单元格。翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。
返回经过一些翻转后，行上所有值都相等的最大行数。
思路：
两行数字，经过对一些列的反转，最后都达到这一行的值相同。那么这两行数字的关系有两种情况：
两行数字的值都相同；
两行数字的值都相反；
其他任何情况，一定有一列始终都不满足相等。
所以题目的结果为看满足两种情况的行的集合最多有多少？
只要两两枚举就能算出来，曾经加入过其他集合的可以后面就不比较了。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : int maxEqualRowsAfterFlips (vector<vector<int >>& a) int m = a.size (); int n = a[0 ].size (); int ret = 0 ; for (int i = 0 ; i < m ; ++i) { int tmp = 1 ; for (int j = i+1 ; j < m; ++j) { if (a[i]==a[j]) { tmp++; } else { int k; for (k = 0 ; k < n; ++k) { if (a[i][k]+a[j][k]!=1 ) break ; } if (k==n) tmp++; } } ret = max (ret, tmp); } return ret; } };
3. 负二进制数相加 题目：
负二进制数相加(Adding Two Negabinary Numbers)
地址：
https://leetcode-cn.com/contest/weekly-contest-139/problems/adding-two-negabinary-numbers/
题意：
给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。
数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 的数字也同样不含前导零：以 arr 为例，这意味着要么 arr == [0]，要么 arr[0] == 1。
返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
思路：
-2进制的算法和2进制算法是一样的。都是先模-2得到当前位的值，然后再除-2得到高位的进位值。
但是由于题目中要求每位必须是0或者是1，所以在模-2等于-1时，要进行特殊处理。
如果取模的结果是-1表示当前位的值为-1，要变成正数才能正常表示。要把当前位变为1，要把除数加1。
如果想不明白，请思考下公式 (x*-2)+(-1) = (x-1)*-2 + 1。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution {public : vector<int > addNegabinary (vector<int >& arr1, vector<int >& arr2) { vector<int > res; int i = arr1. size ()-1 ; int j = arr2. size ()-1 ; int carry = 0 ; int divid = -2 ; while (i >= 0 ||j >= 0 ||carry) { if (i>=0 ) carry += arr1[i]; if (j>=0 ) carry += arr2[j]; int mod = carry % divid; carry /= divid; if (mod < 0 ) { mod -= divid; carry += 1 ; } res.push_back (mod); --i; --j; } while (res.size ()>1 ) { if (res.back ()==0 ) res.pop_back (); else break ; } reverse (res.begin (), res.end ()); return res; } };
4. 元素和为目标值的子矩阵数量 题目：
元素和为目标值的子矩阵数量(Number of Submatrices That Sum to Target)
地址：
https://leetcode-cn.com/contest/weekly-contest-139/problems/number-of-submatrices-that-sum-to-target/
题意：
给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同（如：x1 != x1’），那么这两个子矩阵也不同。
思路：
先对每行数据进行处理，求出每行开始到当前位置的和。sum[i][j] = matrix[i][0]+matrix[i][0]+...+matrix[i][j]。
这样一行中j，k两个之间的区间和可以表示为sum[i][j]-sum[i][k-1]，很快能求出。
之后枚举两列c1,c2，对于每一次枚举，行数从上到下扫描。
每扫描到一行r1，先计算出当前行与两列，还有第0行形成的矩阵的和S。
然后查找是否有之前的行r0的和为S-target。
如果有，则r0，r1，c1，c2形成的和为target。
最后再把S存起来，留给后面的行扫描时查找。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution {public : unordered_map<int , int > mp; int numSubmatrixSumTarget (vector<vector<int >>& matrix, int target) int m = matrix.size (); int n = matrix[0 ].size (); for (int i = 0 ; i < m; ++i) { for (int j = 1 ; j < n; ++j) { matrix[i][j] += matrix[i][j-1 ]; } } int ans = 0 ; for (int j = 0 ; j < n; ++j) { for (int k = j; k < n; ++k) { mp.clear (); mp[0 ] = 1 ; int sum = 0 ; for (int i = 0 ; i < m; ++i) { if (j > 0 ) sum += matrix[i][k] - matrix[i][j-1 ]; else sum += matrix[i][k]; if (mp.find (sum-target)!=mp.end ()) ans += mp[sum-target]; mp[sum]++; } } } return ans; } };
