WeeklyConstest160

发表于 分类于

力扣160场周赛[链接][https://leetcode-cn.com/contest/weekly-contest-160/]

菜过三题，终于涨分了，哈哈哈哈哈哈哈哈！！！

第一题：日常签到

5238. 找出给定方程的正整数解

给出一个函数 f(x, y) 和一个目标结果 z，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。

给定函数是严格单调的，也就是说：

  • f(x, y) < f(x + 1, y)
  • f(x, y) < f(x, y + 1)

函数接口定义如下：

1
2
3
4
5
interface CustomFunction {
public:
  // Returns positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};

如果你想自定义测试，你可以输入整数 function_id 和一个目标结果 z 作为输入，其中 function_id 表示一个隐藏函数列表中的一个函数编号，题目只会告诉你列表中的 2 个函数。

你可以将满足条件的 结果数对 按任意顺序返回。

示例 1：

1
2
3
输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 表示 f(x, y) = x + y

示例 2：

1
2
3
输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 表示 f(x, y) = x * y

提示：

  • 1 <= function_id <= 9
  • 1 <= z <= 100
  • 题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
  • 在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。

算法分析

无脑暴力，可以过；快一点的算法可以二分；滑稽

C++代码

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
/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 * public:
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     int f(int x, int y);
 * };
 */

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

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     public int f(int x, int y);
 * };
 */
class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=1;i<=1000;i++){
            for(int j=1;j<=1000;j++){
                if(customfunction.f(i,j)==z)
                    ans.add(Arrays.asList(i,j));
            }
        }
        return ans;
    }
}

第二题：格雷码的应用

5239. 循环码排列

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：

  • p[0] = start
  • p[i] 和 p[i+1] 的二进制表示形式只有一位不同
  • p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

示例 1：

1
2
3
4
输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

示例 2：

1
2
3
输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

提示：

  • 1 <= n <= 16
  • 0 <= start < 2^n

算法描述

有一个特别简便的格雷码的生成函数，直接转换为十进制的那种，比赛的时候不知道，我的做法现将格雷码当作字符串存放，再将二进制的字符串转换成十进制数，最后按要求输出即可。
这一题知道题目的意思后就简单了，如果读不懂题意就难了！！

C++代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
    
    int charToDigit(char c)
    {
        return c-'0';
    }
    
    vector<string> gray_code(int n)
    {
        if(n==1)
        {
            vector<string> v;
            v.push_back("0");
            v.push_back("1");
            return v;
        }
        else
        {
            vector<string> v;
            vector<string> v1;
            v1=gray_code(n-1);

            for(int i=0;i<v1.size();i++)
            {
                v.push_back("0"+v1[i]);
            }
            for(int i=(v1.size()-1);i>-1;i--)
            {
                v.push_back("1"+v1[i]);
            }

            return v;
        }
    }
    int jinzhi2to10(string pre)
    {

        int length=pre.size();
        int result=0;
        for(int i=0; i<length; i++)
        {
            result+=((charToDigit(pre[i]))*pow(2,length-1-i));
        }
        return result;
    }

    vector<int> circularPermutation(int n, int start) {
        vector<int> ans;
        vector<string> s=gray_code(n);
        string str="";
        cout<<"str"<<str<<endl;
        for(int j=0;j<s.size();j++){
            int r = jinzhi2to10(s[j]);
            ans.push_back(r);
        }
        int i;
        for(i=0;i<s.size();i++)
            if(ans[i]==start)break;
        vector<int> tt;
        for(int t=0;t<s.size();t++){
           i=i%s.size();
            tt.push_back(ans[i]);
            i++;
        }
        return tt;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    
    List<Integer> create(int n){
        List<Integer> res = new ArrayList<>();
        res.clear();
        for(int i=0;i<(1<<n);i++)
            res.add(i^(i>>1));
        return res;
    }
    
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> ans = new ArrayList<>();
        List<Integer> res = create(n);
        int i=0;
        for(int t:res){
            if(t==start)break;
            i++;
        }
        for(int j=0;j<res.size();j++){
            ans.add(res.get((i++)%res.size()));
        }
        return ans;
    }
}

第三题：字符串处理

5240. 串联字符串的最大长度

给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。

请返回所有可行解 s 中最长长度。

示例 1：

1
2
3
输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。

示例 2：

1
2
3
输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。

示例 3：

1
2
输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26

提示：

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[i] 中只含有小写英文字母

算法描述

暴力解法，每个字符串都跑一遍所有的字符串，用set来存放当前有的字符，每次添加都需要判断是否有相同字符，有的话直接跳出；这个操作有多处用到：

  • 第一个字符串时遇到相同字符，清空set，跳过本次循环
  • 添加字符串时，遇到相同的字符串，要把之前加入到set中的字符弹出，再继续遍历

这题最容易想到的就是暴力了，代码复杂度还行，就是要注意细节，我是wa了二次；

C++代码

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 maxLength(vector<string>& arr) {
        int ans=0;
        for(int i=0;i<arr.size();i++){
            string s = arr[i];
            unordered_set<char> st;
            int j;
            for(j=0;j<s.length();j++){
                if(!st.count(s[j]))st.insert(s[j]);
                else break;
            }
            if(j!=s.length()){st.clear();continue;}
            int q;
            for(q=0;q<arr.size();q++){
                int t;
                for(t=0;t<arr[q].length();t++)
                    if(st.count(arr[q][t]))break;
                    else st.insert(arr[q][t]);
                if(t==arr[q].length())s+=arr[q];
                else {
                    for(int p=0;p<t;p++){
                        st.erase(arr[q][p]);
                    }
                }
            }
            if(ans<s.size())ans=s.size();
            st.clear();
        }
        return ans;
    }
};

Java代码

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
class Solution {
    public int maxLength(List<String> arr) {
        int ans=0;
        for(int i=0;i<arr.size();i++){
            String s=arr.get(i);
            Set<Character> st = new HashSet<>();
            int j;
            for(j=0;j<s.length();j++){
                if(!st.contains(s.charAt(j)))st.add(s.charAt(j));
                else break;
            }
            if(j!=s.length()){
                st.clear();
                continue;
            }
            int q;
            StringBuffer ss = new StringBuffer(s);
            for(q=0;q<arr.size();q++){
                int t;
                for(t=0;t<arr.get(q).length();t++){
                    if(st.contains(arr.get(q).charAt(t)))break;
                    else st.add(arr.get(q).charAt(t));
                }
                if(t==arr.get(q).length())ss.append(arr.get(q));
                else {
                    for(int p=0;p<t;p++){
                        st.remove(arr.get(q).charAt(p));
                    }
                }
                
            }
            if(ans<ss.length())ans=ss.length();
                st.clear();
        }
        return ans;
    }
}

第四题：论问题（有研究表明）

5241. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

示例 1：

img

1
2
3
4
5
输入：n = 2, m = 3
输出：3
解释：3 块地砖就可以铺满卧室。
     2 块 1x1 地砖
     1 块 2x2 地砖

示例 2：

img

1
2
输入：n = 5, m = 8
输出：5

示例 3：

img

1
2
输入：n = 11, m = 13
输出：6

提示：

  • 1 <= n <= 13
  • 1 <= m <= 13

算法描述

附上生成函数：

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
#include <iostream>
#include <iomanip>
#include<cstring>
using namespace std;
const int maxn=100,inf=0x3f3f3f3f;

int dp[maxn][maxn],ans[maxn][maxn];

int f(int n,int m){
    if(n==m)
        return dp[n][m]=1;
    if(dp[n][m]!=inf) return dp[n][m];
    for(int i=1;i<n;i++)
        dp[n][m]=min(dp[n][m],f(i,m)+f(n-i,m));
    for(int i=1;i<m;i++)
        dp[n][m]=min(dp[n][m],f(n,i)+f(n,m-i));
    for(int x1=2;x1<n;x1++)
        for(int x2=1;x2<x1;x2++)
            for(int y1=2;y1<m;y1++)
                for(int y2=1;y2<y1;y2++)
                    dp[n][m]=min(dp[n][m],f(x2,y1)+f(n-x2,y2)+f(n-x1,m-y2)+f(x1,m-y1)+f(x1-x2,y1-y2));
    return dp[n][m];
}

int main() {
    memset(dp,inf,sizeof(dp));
    for(int i=1;i<=13;i++){
        cout<<"{";
        for(int j=1;j<=13;j++)
            cout << f(i,j) << ',';
        cout << "}"<<endl;
    }
    return 0;
}

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int tilingRectangle(int n, int m) {
        int ans[13][13]={{1,2,3,4,5,6,7,8,9,10,11,12,13},
                    {2,1,3,2,4,3,5,4,6,5,7,6,8},
                    {3,3,1,4,4,2,5,5,3,6,6,4,7},
                    {4,2,4,1,5,3,5,2,6,4,6,3,7},
                    {5,4,4,5,1,5,5,5,6,2,6,6,6},
                    {6,3,2,3,5,1,5,4,3,4,6,2,6},
                    {7,5,5,5,5,5,1,7,6,6,6,6,6},
                    {8,4,5,2,5,4,7,1,7,5,6,3,6},
                    {9,6,3,6,6,3,6,7,1,6,7,4,7},
                    {10,5,6,4,2,4,6,5,6,1,6,5,7},
                    {11,7,6,6,6,6,6,6,7,6,1,7,6},
                    {12,6,4,3,6,2,6,3,4,5,7,1,7},
                    {13,8,7,7,6,6,6,6,7,7,6,7,1}
                    };
        return ans[n-1][m-1];
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int tilingRectangle(int n, int m) {
        int ans[][]={
                    {1,2,3,4,5,6,7,8,9,10,11,12,13},
                    {2,1,3,2,4,3,5,4,6,5,7,6,8},
                    {3,3,1,4,4,2,5,5,3,6,6,4,7},
                    {4,2,4,1,5,3,5,2,6,4,6,3,7},
                    {5,4,4,5,1,5,5,5,6,2,6,6,6},
                    {6,3,2,3,5,1,5,4,3,4,6,2,6},
                    {7,5,5,5,5,5,1,7,6,6,6,6,6},
                    {8,4,5,2,5,4,7,1,7,5,6,3,6},
                    {9,6,3,6,6,3,6,7,1,6,7,4,7},
                    {10,5,6,4,2,4,6,5,6,1,6,5,7},
                    {11,7,6,6,6,6,6,6,7,6,1,7,6},
                    {12,6,4,3,6,2,6,3,4,5,7,1,7},
                    {13,8,7,7,6,6,6,6,7,7,6,7,1}
        };
        return ans[n-1][m-1];
    }
}