leetcode刷题记录12(2023-07-02)【完全平方数(动态规划) | 移动零(冒泡排序) | 寻找重复数 | 删除无效的括号(暴力搜索+剪枝)】

发布时间:2024年01月04日

279. 完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9

提示:

1 < = n < = 1 0 4 1 <= n <= 10^4 1<=n<=104

这道题采用动态规划进行求解,不能用贪心去做,否则结果是错误的,反例就是示例1,如果用贪心,12=9+1+1+1,需要4个数。

另外一种方法是利用了一个数学定理(四平方和定理),见https://leetcode.cn/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/

#include<math.h>
#include<vector>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                minn = min(minn, dp[i - j * j]);
            }
            dp[i] = minn + 1;
        }
        return dp[n];
    }
};

283. 移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶:你能尽量减少完成的操作次数吗?

这道题目的思路就是冒泡排序,但是不同点是 if 语句里面交换的条件为当前位是否为0且下一位是否不为0。

并设置一个 isFinish 来判断是否需要结束算法。如果当前循环中一次交换都没有发生(已经没有0了),那么算法也就可以结束了。

#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            bool isFinish = true;
            for (int j = 0; j < nums.size() - i - 1; j++) {
                if (nums[j] == 0 && nums[j + 1] != 0) {
                    swap(nums[j], nums[j + 1]);
                    isFinish = false;
                }
            }
            if (isFinish) {
                break;
            }
        }
    }
};

int main() {
    Solution sol;
    vector<int> vec = { 1,0,2,0,3 };
    sol.moveZeroes(vec);
    for (auto it : vec) {
        cout << it << " ";
    }
}

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1:

输入:nums = [1,3,4,2,2]
输出:2
示例 2:

输入:nums = [3,1,3,4,2]
输出:3

提示:

1 < = n < = 1 0 5 1 <= n <= 10^5 1<=n<=105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

进阶:

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?

最初是采用冒泡排序,发现有个很大的测试用例会导致超时,然后发现复杂度搞错了,不应该到 O ( n 2 ) O(n^2) O(n2)级别的,可以用快排搞到 O ( n l o g n + n ) O(nlogn+n) O(nlogn+n),即排序后再遍历一遍。

一种时间复杂度为O(n)的快慢指针的方法,很巧妙:https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

//class Solution {
//public:
//    int findDuplicate(vector<int>& nums) {
//        for (int i = 0; i < nums.size(); i++) {
//            for (int j = 0; j < nums.size() - i - 1; j++) {
//                if (nums[j] > nums[j + 1]) {
//                    swap(nums[j], nums[j + 1]);
//                }
//                else if (nums[j] == nums[j + 1]) {
//                    return nums[j];
//                }
//            }
//        }
//    }
//};

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int i;
        for (i = 0; i < nums.size() - 1; i++) {
            if (nums[i] == nums[i + 1])break;
        }
        return nums[i];
    }
};

int main() {
    vector<int> vec = { 1,3,4,2,2 };
    Solution sol;
    int res = sol.findDuplicate(vec);
    cout << res;
}

301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1:
输入:s = “()())()”
输出:[“(())()”,“()()()”]

示例 2:
输入:s = “(a)())()”
输出:[“(a())()”,“(a)()()”]

示例 3:
输入:s = “)(”
输出:[“”]

提示:

1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

暴力搜索,枚举每一种情况,对于肯定不符合的情况,比如右边括号数量已经大于了左边括号数量(score为负,剪枝),预处理时统计了左括号和右括号的数量(score应该小于他们俩的最小值,如果大于了证明当前情况已经不满足了)。

基于上述两种思想就可以进行剪枝了。

#include<vector>
#include<string>
#include<unordered_set>

using namespace std;

class Solution {
    int maxMaybeResult;
    int strLength;  // 字符串的长度
    int len;        // 当前找到的最长的合法字符串
    unordered_set<string> subStrs; // 用来存储找到的合法字符串,因为不能存在重复的情况,因此采用集合
    string str;

private:
    void dfs(int pos, string cur, int score) {
        // 递归结束条件 -> 中途不符合条件(剪枝)
        if (score<0 || score>maxMaybeResult) {
            return;
        }
        
        // 递归结束条件 -> 符合条件,或者最后不符合条件
        if (pos == strLength) {
            if (score == 0 && cur.length() >= len) {
                // 如果当前的更长,之前的全部作废,同时更新len
                if (cur.length() > len) {
                    subStrs.clear();
                    len = cur.length();
                }
                // 插入到当前集合中来
                subStrs.insert(cur);
            }
            return;
        }

        char ch = str[pos];

        if (ch == '(') {
            dfs(pos + 1, cur + ch, score + 1);
            dfs(pos + 1, cur, score);
        }
        else if (ch == ')') {
            dfs(pos + 1, cur + ch, score - 1);
            dfs(pos + 1, cur, score);
        }
        else {
            dfs(pos + 1, cur + ch, score);
        }

    }
public:
    vector<string> removeInvalidParentheses(string s) {
        len = 0;

        strLength = s.length();

        str = s;

        int leftNum = 0, rightNum = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                leftNum++;
            }
            else if (s[i] == ')') {
                rightNum++;
            }
        }

        maxMaybeResult = min(leftNum, rightNum);
        dfs(0, "", 0);
        vector<string> res;
        for (auto it : subStrs) {
            res.push_back(it);
        }

        return res;
    }
};
文章来源:https://blog.csdn.net/myf_666/article/details/131505162
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。