Leetcode-第160场周赛

发表于 分类于 阅读次数：

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

思路：

签到题的全新版本。

直接暴力遍历就行了，明白这是个在写一个函数接口。

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
/*
 * // 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) {
        int x=1,y=1;
        vector<vector<int>> res;
        for(int i=1;i<=1000;i++)
        {
            for(int j=1;j<=1000;j++)
            {
                if(customfunction.f(i,j)==z)
                {
                    vector<int> temp;
                    temp.push_back(i);
                    temp.push_back(j);
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
};

1238. 循环码排列

解法：位运算

思路：采用位运算，其实这题就是格雷编码的改编，可以看第89题，明白格雷编码的实现，这题也就容易了。

以 2 3 1 0 4 5 7 6 为例 进行分析，转换成二进制得

0 1 0

0 1 1

0 0 1

0 0 0

1 0 0

1 0 1

1 1 1

1 1 0

分析发现，一开始对第1个进行镜像反射，改变最右边一位数，其他不变，便得到了第二位数

然后对1，2进行镜像反射，改变从右起第二位数，其他不变，便得到了3，4数

依次类推，便可得到题目要求的循环码排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> res(1<<n,0);
        res[0]=start;
        for(int i=1;i<=n;i++)
        {
            int k=1<<(i-1);
            for(int j=0;j<k;j++)
            {
                res[(k<<1)-1-j]=res[j]^k;
            }
        }
        return res;
    }
};

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

解法：位压缩

思路：

1.先对字符串进行排序，从大到小，然后将每个字符串都压缩成一个整数进行保存，用32位整数的每一位代表一个字母，例如1表示a，10表示b，100表示c。（1，10，100是二进制表示）。且在保存过程中，若发现一个字符串中存在重复字符则对该字符串直接舍弃。且每次判断符合要求的单个字符串的最大长度保存res。

2.用s来存当前整数，与想要串联的字符串进行&运算若为0可串联，否则查找下一个字符串。找到最大的res。

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
class Solution {
public:
    int maxLength(vector<string>& arr) {
        int res=0;
        int n=arr.size();
        vector<int> temp(n,0);
        sort(arr.begin(),arr.end());
        reverse(arr.begin(),arr.end());
        
        for(int i=0;i<n;i++)
        {
            string str=arr[i];
            int size=str.size();
            for(int j=0;j<size;j++)
            {
                if(temp[i]&(1<<(str[j]-'a')))
                {
                    temp[i]=INT_MAX;
                    arr[i]="";
                    break;
                }
                temp[i]=temp[i]|(1<<(str[j]-'a'));
            }
            //cout<<arr[i]<<" ";
            if(temp[i]!=INT_MAX)
            {
                res=max(res,size);
            }
        }
        for(int i=0;i<n;i++)
        {
            if(temp[i]==INT_MAX)
                continue;
            int s=temp[i];
            int k1=arr[i].size();
            for(int j=0;j<n;j++)
            {
                if(temp[j]==INT_MAX)
                    continue;
                if((s&temp[j])==0)
                {
                    s=s|temp[j];
                    k1=k1+arr[j].size();
                    res=max(res,k1);
                }
            }
        }
        return res;
    }
};

1240. 铺瓷砖

此题参考小白二号，全靠二哥的讲解，才明白这题

解法1：打表

没啥好说的。面向测设用例编程=_=！

解法2：回溯
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
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
    //ret表示当前最小瓷砖数，如果搜索的过程中，瓷砖数比这个数还大，就不用接着搜索了，这是这份代码中唯一的剪枝
    int ret;

    //data表示当前瓷砖铺的情况，总共有n*m个bit，这里把每一行的bit压缩成一个int了，节省空间
    //x表示当前位置的横坐标
    //y表示当前位置的纵坐标
    //now表示当前的瓷砖数
    //n和m就是题目的n和m，因为后面判断需要用到，这里把这俩货也传进来了
    
    //对于dfs来说，状态变量其实只有data，其他变量都是辅助
    void dfs(vector<int>& data, int x, int y, int now, int n, int m) {
        //当行坐标到了n，说明搜索已经结束了，可以保存结果
        if (x == n) {
            ret = min(ret, now);
            return;
        }
        //当纵坐标到了m，说明来到了一行的末尾，直接换下一行的行首继续搜
        if (y == m) {
            dfs(data, x + 1, 0, now, n, m);
            return;
        }
        //如果当前瓷砖数比搜索过的最小瓷砖数还大，直接跳出，这是唯一的剪枝
        if (now >= ret) {
            return;
        }
        //如果坐标(x,y)已经被贴了瓷砖，搜索下一个
        if (data[x] & (1 << y)) {
            dfs(data, x, y + 1, now, n, m);
            return;
        }
        //k表示坐标(x,y)最大可放的瓷砖，如果放下去超过n*m的范围，就不能放了
        int k = 0;
        for (int i = 1;x + i - 1 < n && y + i - 1 < m;i++) {
            k = i;
        }
        //为啥要从最大可放的瓷砖开始搜呢，因为瓷砖越大，最后的瓷砖数会极有可能越少，这样跟剪枝代码结合起来，可以多剪一点
        while (k >= 1) {
            //flag表示是否可以放k\*k的操作，这里应该可以跟上面的循环合并。如果k\*k中正好某个位置已经被贴瓷砖了，就不能放了
            bool flag = true;
            for (int i = 0;i < k;i++) {
                for (int j = 0;j < k;j++) {
                    if (data[x + i] & (1 << (y + j))) {
                        flag = false;
                    }
                }
            }
            //flag为true表示可以放，既然可以放，就放呗
            if (flag) {
                //贴瓷砖的过程
                for (int i = 0;i < k;i++) {
                    for (int j = 0;j < k;j++) {
                        data[x + i] += (1 << (y + j));
                    }
                }
                //继续搜下一个位置
                dfs(data, x, y + 1, now + 1, n, m);
                //回溯的本质，如果搜索完，必须还原现场
                for (int i = 0;i < k;i++) {
                    for (int j = 0;j < k;j++) {
                        data[x + i] -= (1 << (y + j));
                    }
                }
            }
            k--;
        }
    }
    int tilingRectangle(int n, int m) {
        vector<int> data(n, 0);
        ret = n * m;
        dfs(data, 0, 0, 0, n, m);
        return ret;
    }
};

/*作者：小白二号
链接：https://leetcode-cn.com/circle/discuss/LPwegn/view/XeRE60/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/