算法题（五）

本文最后更新于：2021年4月29日 上午

概览：LeetCode刷题。

1
2
3
4
<details>
    <summary>折叠/查看代码</summary>
    
</details>

求数组的幂集 | shopee笔试

3021/04/21

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

示例:

输入： nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/power-set-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归

思路，应当采用递归的方式实现，但是笔试时没做出来。

要求子集不能重复，那就使用一个变量start来标识应该从哪里开始

要求全部的幂集，那就是每加入一个元素，就存储到最终的结果集中。

折叠/查看代码 
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
vector<vector<int>> result;
vector<int> path;

void trackback(vector<int> &nums,int start) {
    result.push_back(path);//先保存结果集合
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        trackback(nums, i + 1);
        path.pop_back();
    }
}

int main() {

    result.clear();
    path.clear();

    vector<int> nums = { 1,2,3 };

    trackback(nums, 0);

    for (auto i : result) {
        for (auto ii : i) {
            cout << ii << " ";
        }
        cout << endl;
    }

    return 0;
}

位运算

换种思路，集合中的数，要么选择，要么不选择.

对于1，2，3，000表示都不选，001表示只选择3。

而一共有2的len次方中情况，遍历即可。

折叠/查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<vector<int>> subsets(vector<int>& nums) {
    int len = nums.size();
    int size = 1 << len;
    vector<vector<int> > result(size,vector<int>());

    for(int i=0;i<size;i++){
        vector<int > path;
        for(int j=0;j<len;j++){
            if(i >> j &1){
                path.push_back(nums[j]);
            }
        }
        result[i] = path;
    }
    return result;
}
  • 不过顺序不太能保证。

45 跳跃游戏2

2021/04/22

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：由于总是可以跳到，那就转换方向，倒着向前寻找距离最远的那个点，不断更新迭代，到达第一个位置时停止。

折叠/查看代码 
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
class Solution {
public:
    //总是可以跳跃到最后一个位置！
    //也就是走的越少越好，每次尽量跳大步
    //转换思路。从最后一个位置向前找距离最远的。
    int jump(vector<int>& nums) {
        int len = nums.size();
        int count = 0;

        int size = len-1;

        while(1){

            if(size == 0){
                return count;
            }

            for(int i=0;i<size;i++){
                if(size - i <= nums[i]){
                    count++;
                    size = i;
                    break;
                }
            }
        }
    }
};

足球队积分问题 - 动态规划|4399 笔试

2021/04/22

A和B两支足球队采用积分制相互进行比赛，初始为0分，赢一场3分，输一场0分，平一场1分。

跟定A和B的比分，使用动态规划求出其比赛的最少场数。

例如：A 3 ，B 3

那么 可以3长平局，或者各赢一场，则比赛最少场数是2.

若不可能，则返回-1

思路：当时没什么思路，那就填表找规律。

0 1 2 3 4 5 6 7 8
0 0 -1 -1 1 -1 -1 2 -1 -1
1 1 -1 -1 2 -1 -1 3 -1
2 2 -1 -1 3 -1 -1 4
3 2 -1 -1 3 -1 -1
4 3 -1 -1 4 -1

可以看到规律了：dp[i][j]用于表示i:j这个比分对应的最少场数。

  • dp[i][i]表示双方的积分相同
    • 若是3的倍数，则场数为(i+i) /3。
    • 若不是3的倍数，优先考虑3分的情况，再考虑1分的情况。(i/3)*2 + (i%3)场数。
  • 而dp[i][j]则表示普通情况下
    • 若(j-i)%3 == 0则，dp[i][j] = dp[i][j-3]+1。
    • 其他情况下，就是默认-1。

代码：

折叠/查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int GetMinRound(int a,int b){
    int len = max(a,b);
    vector<vector<int> > dp(len+1,vector<int>(len+1,-1));//二维数组

    for(int i = 0;i<len;i++){
        if(i % 3 ==0)
            dp[i][i] = (i+i)/3;
        else dp[i][i] = (i/3) *2 + (i%3);
    }

    for(int j=0;i<len;j++){
        for(int i=j+1;i<len;i++){
            if( (j-i) % 3 == 0 ){
                dp[i][j] = dp[i][j-3]+1;//动态规划方程
            }
        }
    }  

    if(a<b) swap(a,b);//引用传值，交换数据
    return dp[a][b];
}

注意事项：

  1. 二维数组要注意长度啊！下标0-a之间，长度应该是a+1！
  2. 填表只填了一半，要保证a >= b，否则访问到的都是-1.

633 平方数之和

2021/04/28

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
示例 2：

输入：c = 3
输出：false
示例 3：

输入：c = 4
输出：true
示例 4：

输入：c = 2
输出：true
示例 5：

输入：c = 1
输出：true

提示：

0 <= c <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-square-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：快速查找–哈希表

通过哈希表可以确定一个元素是否是在哈希表中。O(1)的时间。

所以先建立哈希表，将所有可能用到的平方存入哈希表，然后再去遍历查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
	bool judgeSquareSum(int c) {
		if (c == 0) return true;

		unordered_map <int, int> maps;
		for (int i = 1; i <= sqrt(INT_MAX); i++) {
			maps[i*i] = 1;
		}

		for (int i = 1; i <= sqrt(c); i++) {
			if (i*i == c || maps.count(c - i * i)) return true;
		}
		return false;
	}
};