1.走瓷砖问题？直接确定中间的8个点坐标，然后用力扣62题的思路来做就可以。这个代码我做了一个镜像，其实从左下到右上，还是从左上到右下，结果都是一样的，因为中间的限制是对称性的，所以我实现的是从左上到右下的代码，这样更加符合直觉。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 正方形广场边长是 2n+1
* @return int整型
*/
int count(int n) {
int len = 2*n+1;
vector<vector<int>> dp(len, vector<int>(len, 0));
dp[0][0] = 1;
set<pair<int,int>> midp = middle_points(len);
for(int j = 1; j < len; j++)
{
if(midp.count({0,j}))
break;
dp[0][j] += dp[0][j-1];
}
for(int i = 1; i < len; i++)
{
if(midp.count({i,0}))
break;
dp[i][0] += dp[i-1][0];
}
for(int i = 1; i < len; i++)
{
for(int j = 1; j < len; j++)
{
if(midp.count({i,j}))
continue;
if(!midp.count({i-1,j}))
dp[i][j] += dp[i-1][j];
if(!midp.count({i,j-1}))
dp[i][j] += dp[i][j-1];
}
}
return dp[len-1][len-1];
}
set<pair<int,int>> middle_points(int n)
{
set<pair<int,int>> res;
pair<int,int> middle {n/2,n/2};
res.insert(middle);
res.insert({middle.first-1,middle.second-1});
res.insert({middle.first-1,middle.second});
res.insert({middle.first-1,middle.second+1});
res.insert({middle.first,middle.second-1});
res.insert({middle.first,middle.second+1});
res.insert({middle.first+1,middle.second-1});
res.insert({middle.first+1,middle.second});
res.insert({middle.first+1,middle.second+1});
return res;
}
};
int main()
{
Solution s1;
cout << s1.count(2) << endl;
return 0;
} 2. 数组可以拼接的最大数字，力扣原题，做个排序就行 #include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return string字符串
*/
string largest(vector<int>& nums) {
int len = nums.size();
if(len < 1)
return "0";
vector<string> snums;
for(auto& e : nums)
{
snums.push_back(to_string(e));
}
sort(snums.begin(), snums.end(), compare);
string res = "";
for(auto& str : snums)
{
res += str;
}
if(res[0] == '0')
return "0";
return res;
}
static bool compare(string& s1, string& s2)
{
return s1+s2 > s2+s1;
}
};
int main()
{
Solution s1;
vector<int> nums{1,20,21,4,8};
cout << s1.largest(nums) << endl;
return 0;
} 
全部评论
(3) 回帖