题目1 1237. 找出给定方程的正整数解
题意：
第一次做这类型题，枚举调一个函数，找出符合它的解。
思路：
这题是考阅读理解能力。
代码:
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
vector<vector<int> > ans;
for(int i=1;i<=z;i++){
for(int j=1;j<=z;j++){
if(customfunction.f(i,j) == z){
ans.push_back({i,j});
}
}
}
return ans;
}
};
class Solution:
def findSolution(self
, customfunction
, z
) :
ans
= []
for i
in range(1,z
+1):
for j
in range(1,z
+1):
if customfunction
.f
(i
,j
) == z
:
ans
.append
([i
,j
])
return ans
题目2 1238. 循环码排列
题意：
构造一个循环的序列，相邻两个数的二进制表示，只有一个位置不同。
思路：
一个循环的序列，二进制表示只有一位不同的序列是典型的格雷码的特点。
所以问题就变成利用二进制转格雷码算法，构造一个格雷码序列。
参考二进制转格雷码：保留最高位，对后面每一位与自己前一位做异或操作。
代码:
class Solution {
public:
vector<int> circularPermutation(int n, int start) {
vector<int> ans;
int tmp[(1<<n)+1] ,pos = 0;
for(int i=0; i<(1<<n); i++){
tmp[i] = i^(i>>1);
if(tmp[i] == start) pos = i;
}
for(int i= pos;i<(1<<n);i++){
ans.push_back(tmp[i]);
}
for(int i=0;i<pos;i++){
ans.push_back(tmp[i]);
}
return ans;
}
};
题目3 1239. 串联字符串的最大长度
题意：
给一个字符串数组，不需要连续，问构成所有字母只出现一次最长子串长度是？
思路：
直接枚举每个位置数选或不选， ,开始没想到2^16=65536的暴力能过？太久没做题，复杂度都不会算…这题复习了一下，c++位运算的左移，右移。
代码:
class Solution {
public:
int maxLength(vector<string>& arr) {
int ans = 0,n = arr.size();
for(int i=1; i<(1<<n); i++){
vector<int> vis(30);
bool flag = true;
int len = 0;
for(int j=0;j<n;j++){
if((i>>j)&1){
for(auto c:arr[j]){
vis[c-'a'] +=1;
if(vis[c-'a']>=2){
flag = false;
break;
}
}
if(flag == false) break;
else len += int(arr[j].size());
}
}
if(flag == true) ans=max(ans,len);
}
return ans;
}
};
class Solution:
def maxLength(self
, arr
):
ans
= 0
n
= len(arr
)
for i
in range(1, 1<<n
):
vis
= set()
num
= 0
flag
= True
for j
in range(0,n
):
if (i
>>j
)&1 == 1 :
for c
in arr
[j
]:
if c
in vis
: flag
= False
else : vis
.add
(c
)
if flag
== True: num
+= len(arr
[j
])
else : break
if flag
== True: ans
= max(ans
, num
)
return ans
题目4
题意：
问用最少正方形铺满nxm矩阵个数？
输入：n = 2, m = 3
输出：3
解释：3 块地砖就可以铺满卧室。
2 块 1x1 地砖
1 块 2x2 地砖
输入：n = 5, m = 8
输出：5
输入：n = 11, m = 13
输出：6
思路：
这题可以从两个思路(姿势)去搜索dfs(暴力)， 思路1：我们可以直接枚举每一行最低高度，然后贪心的去从大到小的放正方形，直到所有行被填满。
思路2：首先大矩形划分成小矩形过程，有分治思想在里面。同时观察上面的样例可以看出来，每个大矩形划分成小矩形只有三种情况：
竖着切分横着切分四周加上中心方块的切分（图三）
思路二的分治写法既可以用记忆化搜索，也可以用动态规划递推。 思路二有个细节，最后默认划分中心的方块大小为1。
代码:
思路一：
class Solution {
public:
int ans;
void dfs(vector<int> ht, int moves, int n,int m){
bool flag = true;
for(auto h: ht){
if(h!=n){
flag = false;
break;
}
}
if(flag){
ans = min(ans,moves);
return;
}
if(moves >= ans) return;
int minn =0;
for(int i=1;i<ht.size();i++){
if(ht[i]<ht[minn]) minn = i;
}
for(int i=min(m - minn, n - ht[minn]);i>=0;i--){
vector<int>tmp(ht);
for(int j=0;j<i;j++){
tmp[minn + j] += i;
}
dfs(tmp,moves+1,n,m);
}
}
int tilingRectangle(int n, int m) {
ans = n*m;
vector<int> ht(m,0);
dfs(ht,0,n,m);
return ans;
}
};
思路二：
DFS 分治写法
class Solution {
public:
int ans, dp[15][15];
int dfs(int n,int m){
if(n==m) return 1;
if(n==1) return m;
if(m==1) return n;
if(dp[n][m]>0) return dp[n][m];
int res = n*m;
for(int i=1;i<n;i++){
res = min(res, dfs(i,m) + dfs(n-i,m));
}
for(int i=1;i<m;i++){
res = min(res, dfs(n,i) + dfs(n,m-i));
}
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
res = min(res, dfs(i,j) + dfs(i+1,m-j) + dfs(n-i,j-1) + dfs(n-i-1,m-j+1) + 1);
}
}
dp[n][m] = res;
return res;
}
int tilingRectangle(int n, int m) {
memset(dp,0,sizeof(dp));
return dfs(n,m);
}
};
动态规划，递推
class Solution {
public:
int dp[15][15];
int tilingRectangle(int n, int m) {
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j] = i==j? 1 : n*m;
for(int k =1 ; k<i;k++){
dp[i][j] = min(dp[i][j], dp[k][j] + dp[i-k][j]);
}
for(int k =1 ; k<j;k++){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j-k]);
}
for(int x=1;x<i-1;x++){
for(int y=1;y<j-1;y++){
dp[i][j] = min(dp[i][j], dp[x][y] + dp[i-x][y-1] + dp[x+1][j-y] + dp[i-x-1][j-y+1]+1);
}
}
}
}
return dp[n][m];
}
};
代码中x,y解释如图下：
