Leetcode题库练习笔记（Hard）美区国区

题库练习笔记（Hard）美区国区"/>

Leetcode题库练习笔记（Hard）美区国区

Leetcode题库练习笔记（Hard）

• • Median of Two Sorted Arrays
  • • 复杂度O(nlog(n))的解法
    • 最优题解
  • Stone Game IV
  • • 解法1 递归解法 DFS：
    • 解法2 迭代解法 DP：

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O ( l o g ( m + n ) ) O(log (m+n)) O(log(m+n)).

要求返回两个有序数组的中位数，并且时间复杂度控制在 O ( l o g ( m + n ) ) O(log (m+n)) O(log(m+n)).
PS：当然，排序默认都是从小到大
用sort()函数不加参数都是从小到大排序

复杂度O(nlog(n))的解法

这个次优的解法很好想也很好实现，将两个数组合并后排序，再直接输出中位数就行

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {vector<int> nums;int i;for(i=0;i<nums1.size();i++)nums.push_back(nums1[i]);for(i=0;i<nums2.size();i++)nums.push_back(nums2[i]);sort(nums.begin(),nums.end());int n=nums.size();if(n%2==1)//odd elementsreturn nums[(n+1)/2-1];else return (nums[n/2-1]+nums[n/2])/2.;        }
};

最优题解

时间复杂度为O(log(n+m))
分治解法(Devide and Conquer)：

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m=nums1.size();int n=nums2.size();int k1=(m+n+1)/2;int k2=(m+n+2)/2;return (getKth(nums1,nums2,0,0,k1)+getKth(nums1,nums2,0,0,k2))/2.;}#define MAX 0x7FFFFFFFdouble getKth(vector<int>& nums1, vector<int>& nums2,int start1,int start2,int k)//return the kth element of combined vector num1&num2//binary search+recursion{//one of them is vacantif(start1>=nums1.size())return nums2[start2+k-1];if(start2>=nums2.size())return nums1[start1+k-1];if(k==1)return min(nums1[start1],nums2[start2]);int m=nums1.size()-start1;int n=nums2.size()-start2;//get midval, the (k/2)th elementint midVal1,midVal2;if(m<k/2)midVal1=MAX;else midVal1=nums1[start1+k/2-1];if(n<k/2)midVal2=MAX;else midVal2=nums2[start2+k/2-1];//both of them has (k/2)th elementif(midVal1<midVal2)return getKth(nums1,nums2,start1+k/2,start2,k-k/2);elsereturn getKth(nums1,nums2,start1,start2+k/2,k-k/2);            }   
};

解题思路：



分而减枝：依照题目要求找中位数，可以化归于一个更普适的问题：找出两个有序数组合并后的第k个元素
如上所示，可以递归地分而减枝，每次传入两个数组各自的后半段(start1, start2来定位)和元素下标k。
分情况讨论：

• 有数组为空：返回另一个数组的[k-1]元素
• k==1:返回两段段首中较小的那个（因为较小者合并后排在前面，刚好是第一个）
• 非以上两种情况：对比两段中[k/2]元素，抛下[k/2]较小的那一段的前半段，在剩下部分中继续寻找第k-k/2个元素。
  原因：[k/2]较小意味着[k/2]在内的前半段必然在最终合并后排在第k个元素前面，所以可以抛下不管，在剩下的部分中继续寻找
  ~~~    注意：如果某段[k/2]元素不存在，那就将另一段前半段抛下（排在前面），因为用这样减枝方法留下来的段必然是较大的元素，而较小者才应该排到前面。
  程序实现时，将某段前半段抛下 ⇔ ⇔ ⇔将该段start加上k/2后递归调用

Stone Game IV

题目：leetcode Stone Game IV题目

题目要求：Alice 先行，输出Alice赢与否(bool)
每一步玩家可以移走面前石头中的i个（i是完全平方数1,4,9…），无法如此行动则输
重要隐含条件：玩家面前没有石头==输，因为玩家面前的石头数必然是自然数，只要存在石头就可以至少移走1个，从而不在这局输。

解法1 递归解法 DFS：

但是时间复杂度很高，官方解法是python+缓存存储
Python语法糖：@lru_cache(maxsize=none) 启用least-recently-used缓存存储模式，从而提高递归执行速度
这里用到一点计组的知识，cache的页替换策略包含很多种，替换策略汇总
相比传统的FIFO(先进先出)等方式，LRU策略使得代码执行速度更快

class Solution:def winnerSquareGame(self, n: int) -> bool:@lru_cache(maxsize=None)def dfs(remain):if remain == 0:return Falsesqrt_root = int(remain**0.5)for i in range(1, sqrt_root+1):# if there is any chance to make the opponent lose the game in the next round,#  then the current player will win.if not dfs(remain - i*i):return Truereturn Falsereturn dfs(n)

解法2 迭代解法 DP：

上述DFS的等价的迭代版本就是动态规划解法

    bool winnerSquareGame(int n){vector<int>dp(n+1);    //initially all zeros 注意一定是开n+1个空位for(int i=1;i<=n;i++){for(int k=1;k<=sqrt(i);k++)if(dp[i-k*k]==false){dp[i]=true;break;}}return dp[n];}