LeetCode #160 周赛题解（暴力 + 格雷码 + DFS + 矩阵最小正方形剖分）

LeetCode #160 周赛

---

leetcode 题目不同于其他 oj 是黑盒测试，要提交完整可运行代码，而是完善封装好题目给出的函数即可

1237、找出给定方程的正整数解

题目：给出函数 $f(x,y)$，和整数 $z$。求所有满足 $f(x,y)=z$ 的 $(x,y)$。

分析：由于 $x,y$ 范围 $1e3$ ，直接暴力枚举。

class Solution { public: vector<vector<int>> findSolution(CustomFunction& customfunction, int z) { vector<vector<int>> v; for (int i = 1; i <= 1e3; i++) { for (int j = 1; j <= 1e3; j++) { if (customfunction.f(i, j) == z) { v.push_back({i, j}); } } } return v; } };

1238、循环码排列

题目： 给出 $n,start$，要求输出以 $start$ 开头的 $0到2^{n-1}-1$ 的排列，且排列要满足相邻两数的二进制表示相差一位。

分析：格雷码（循环二进制单位距离码）是任意两个相邻数的代码只有一位二进制数不同的编码，。 ①、通过模拟（上下镜射加新位）：

class Solution { public: vector<int> circularPermutation(int n, int start) { vector<int> v = {0, 1}, res; for (int i = 2; i <= n; i++) { for (int j = v.size() - 1; j >= 0; j--) { v.push_back(v[j] + (1 << (i-1))); } } int pos = find(v.begin(), v.end(), start) - v.begin(); int m = v.size(); while (m--) { res.push_back(v[pos]); pos = (pos + 1) % v.size(); } return res; } };

②、通过分析二进制表示：

class Solution { public: vector<int> circularPermutation(int n, int start) { vector<int> v, res; int pos; for (int i = 0; i < 1 << n; i++) { v.push_back(i ^ (i >> 1)); if (v.back() == start) pos = i; } int m = v.size(); while (m--) { res.push_back(v[pos]); pos = (pos + 1) % v.size(); } return res; } };

1239、串联字符串的最大长度

题目：给一个字符串数组 $arr$，选择数组 $arr$ 的子序列组成新的字符串 $s$，但 $s$ 种不能有重复字符，求 $s$ 最大长度。

分析：暴力 $dfs$ 每一位选或者不选，不过要加上剪枝：对于每一位，只有加上后没有重复字符才会继续。

class Solution { public: int dfs(vector<string>& arr, string str, int pos, int* vis) { if (pos == arr.size()) return str.size(); int ans = dfs(arr, str, pos + 1, vis); // 不选当前位置 int tmp[30]; for (int i = 0; i < 30; i++) tmp[i] = vis[i]; // 递归时会改变指针，所以要备份 for (auto x : arr[pos]) { // 选当前位置，但不能有重复 if (tmp[x - 'a'] == 1) return ans; else tmp[x - 'a'] = 1; } return max(dfs(arr, str + arr[pos], pos + 1, tmp), ans); // 取最大 } int maxLength(vector<string>& arr) { int vis[30] = {0}; return dfs(arr, "", 0, vis); } };

1240、铺瓷砖

题目：给你 $(n,m)$ 矩阵，让你分割成若干正方形，求最小分割数。 $n,m<13$

分析：矩阵最小正方形剖分