leetcode解题思路分析（五十七）483 - 493 题

雨点打透心脏的1/2处 2023-01-02 12:28 156阅读 0赞

1.  最小的好进制  
    对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。

**本质上是一道数学题，通过数学公式推导可以得到，设 n可以表示成位数为 s+1，进制为 k 的数，则k<n^ 1/s<k+1。另外由于限制了n的范围，因此可以知道s不可能大于59。由此可得解**

#define LL long long
    
    class Solution { 
    public:
        string smallestGoodBase(string N) { 
            // (11...11)k = k^{s} + k^{s-1} + ... + k^1 + k^0 = n
            // k^s < n < (k+1)^s
            // k < n^{1/s} < k+1
            
            LL n = stol(N);
            LL ans = n - 1;   // 将答案置为 s=1 的情况
            for (int s = 59; s >= 2; --s) { 
                int k = pow(n, 1.0 / s);   // k 为 n^{1/s} 的整数部分
                if (k > 1) {     // 判断 k 是否是一个合法的进制
                    LL sum = 1, mul = 1;   // 计算 (11...11)k 对应的十进制值
                    for (int i = 1; i <= s; ++i) { 
                        mul *= k;
                        sum += mul;
                    }
                    if (sum == n) { 
                        ans = k;
                        break;
                    }
                }
            }
            return to_string(ans);
        }
    };

1.  最大连续1的个数  
    给定一个二进制数组， 计算其中最大连续1的个数。

**很简单的题，遍历一遍即可**

class Solution { 
    public:
        int findMaxConsecutiveOnes(vector<int>& nums) { 
            int cnt = 0, ret = 0;
            for (auto n : nums)
            { 
                if (n)
                { 
                    cnt++;
                }
                else
                { 
                    ret = max(cnt, ret);
                    cnt = 0;
                }
            }
            ret = max(cnt, ret);
            return ret;
        }
    };

1.  预测赢家  
    给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

**本题实际是0和博弈，换言之，自己的优势即对手的劣势，反之亦然。因此每一步都会尽可能选择有利自己的举动。这里我们可以设对手的选择为负值，最终结果为正则获胜，负则失败。由于每一回合都是一样的考虑，这其实就是动态规划的最优子结构了。用dp\[i\]\[j\]表示从i到j的数组最大的值，i == j则直接为nums\[i\]，否则为nums\[i\] - dp\[i + 1\]\[j\]和nums\[j\] - dp\[i\]\[j+1\]中的较大值。最后对dp降维。这里每次仅需要用到dp第i行最新的值即可，因此可以用一维数组代替**

class Solution { 
    public:
        bool PredictTheWinner(vector<int>& nums) { 
            int length = nums.size();
            auto dp = vector<int>(length);
            for (int i = 0; i < length; i++) { 
                dp[i] = nums[i];
            }
            for (int i = length - 2; i >= 0; i--) { 
                for (int j = i + 1; j < length; j++) { 
                    dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
                }
            }
            return dp[length - 1] >= 0;
        }
    };

1.  递增子序列  
    给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

**采用DFS或者BFS均可以**

class Solution { 
    public:
        vector<int> temp; 
        vector<vector<int>> ans;
    
        void dfs(int cur, int last, vector<int>& nums) { 
            if (cur == nums.size()) { 
                if (temp.size() >= 2) { 
                    ans.push_back(temp);
                }
                return;
            }
            if (nums[cur] >= last) { 
                temp.push_back(nums[cur]);
                dfs(cur + 1, nums[cur], nums);
                temp.pop_back();
            }
            if (nums[cur] != last) { 
                dfs(cur + 1, last, nums);
            }
        }
    
        vector<vector<int>> findSubsequences(vector<int>& nums) { 
            dfs(0, INT_MIN, nums);
            return ans;
        }
    };

1.  构造矩形  
    作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：  
    你设计的矩形页面必须等于给定的目标面积。  
    宽度 W 不应大于长度 L，换言之，要求 L >= W 。  
    长度 L 和宽度 W 之间的差距应当尽可能小。  
    你需要按顺序输出你设计的页面的长度 L 和宽度 W。

**求平方根然后递减/增即可**

class Solution { 
    public:
        vector<int> constructRectangle(int area) { 
            int mid = sqrt(area);
            while (area % mid)
            { 
                mid--;
            }
            return { area / mid, mid};
        }
    };

1.  翻转对  
    给定一个数组 nums ，如果 i < j 且 nums\[i\] > 2\*nums\[j\] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。

**分解：将待求解数组\[left, right\]由mid分为两部分，此时重要翻转对(ij)有三种情况：  
ij都在左子数组；ij都在右子数组；i在左半j在右半。合并：假设这两个子问题已经解决，那么原问题的解就等于两个子问题的解之和再加上情况3。也即 ret = l + r + case3。情况1和2通过递归可解，3的话需要考虑子数组如果有序，则找到第一个不满足条件的，后面就不需要继续看了**

class Solution { 
    public:
        // 合并前[left, mid]有序,[mid+1, right]有序
        // 合并后[left, right]有序
        void merge(vector<int>& nums, int left, int right) { 
            int mid = (left + right) / 2;
            int sorted[right - left + 1];
            int p1 = left, p2 = mid + 1;
            int cur = 0;
            while (p1 <= mid && p2 <= right) { 
                if (nums[p1] <= nums[p2]) { 
                    sorted[cur++] = nums[p1++];
                } else { 
                    sorted[cur++] = nums[p2++];
                }
            }
            for (; p1 <= mid; p1++)
                sorted[cur++] = nums[p1];
            for (; p2 <= right; p2++)
                sorted[cur++] = nums[p2];
            for (int i = left; i <= right; i++) { 
                nums[i] = sorted[i-left];
            }
        }
        
        int find_rPairs(vector<int>& nums, int left, int right) { 
            // 递归边界
            if (left == right)
                return 0;
            // 子问题的解 = l + r + case3;
            int mid = (left + right) / 2;
            int l = find_rPairs(nums, left, mid);
            int r = find_rPairs(nums, mid+1, right);
            int ret = l + r;
    
            // 求解情况3
            int i = left;
            int j = mid + 1; // j不回溯，利用排序：时间n^2-->nlogn
            while (i <= mid) { 
                    while (j <= right && (long long)nums[i] > 2 * (long long)nums[j]) 
                        j++;
                    ret += (j - mid - 1);
                    i++;
            }
            // 维持数组的有序，以后后续的计算
            merge(nums, left, right);
            return ret;
        }
        int reversePairs(vector<int>& nums) { 
            if (nums.size() == 0)
                return 0;
            return find_rPairs(nums, 0, nums.size()-1);
        }
    };