Leetcode高频算法思路——起步

只出现一次的数字

题目条件为数组中除了某个元素出现一次以外，其余元素出现了两次，且为线性复杂度根据异或的特性a ^ a = 0可以对数组进行遍历进行异或，就可以找出答案了[time:O(n) space:1]

多数元素

以数为key以出现的次数为value保存到哈希表中，遍历时找出次数大于n/2的数[time:O(n) space:O(k)(k<n/2)]
剔除元素法：将第一个元素设置为多数元素候选c,以及计数器count = 1，将数组后面的数与c比较，若相等count+1，不相等count-1，若count减到0，便表示该元素出现次数太少，将其和后面一个不相等的元素剔除，再次重置c和count，继续此操作，直到比较到最后count都不为0，则c就为多数元素。伪代码：

MAJORITY(n):
  c←candidate(1)
  count←0
  for j←1 to n
      if a[j] = c then count←count+1
  end for
  if count > n/2(取下线) then return c
  else return none

candidate(m):
  j←m; c←a[m]; count←1
  while j<n and count>0
      j←j+1
      if a[j] = c then count←count+1
      else count←count-1
  end while
  if j=n then return c
  else return candidate(j+1)

搜索二维矩阵 II

链接：搜索二维矩阵 II

从右上角开始找，判断当前元素，大了往左走，小了往下走time:O(m+n)
二维数组的二分查找time:O(logm+logn)

合并两个有序数组

链接：合并两个有序数组

开个数组缓存，三个循环写数据进去，最后copy到nums1time:O(n) space:O(n)
从后往前合并time:O(n)

鸡蛋掉落

链接：鸡蛋掉落

教训与经验：刚开始打算用二分法，只能应对鸡蛋足够的情况，对于鸡蛋不足的情况无法再用二分法。本来打算分情况讨论，发现这个思路难以走通。

正常思路
动态规划(状态：鸡蛋是否破碎，变量：鸡蛋数,楼层)
f(i,j) = min{max{f(i-1,k-1),f(i,j-k)} + 1 | 1<=k<=N}，i是待确认的扔下的楼层。

class Solution {
public:
    int superEggDrop(int K, int N)
    {
        int dp[110][10010];
        for (int i = 0; i <= K; ++i) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= N; ++i) {
            dp[0][i] = 0;
            dp[1][i] = i;
        }
        
        // 楼层从1开始增大
        for (int j = 1; j <= N; ++j) {
            // 从2开始，鸡蛋为1的时候下扔次数已经被定义，不依赖子结果
            for (int i = 2; i <= K; ++i) {
                int min_inner = j;
                // 寻找下落点
                for (int k = 1; k <= j; ++k) {
                    int t = max(dp[i-1][k-1],dp[i][j-k]) + 1;
                    min_inner = min(t, min_inner);
                }
                dp[i][j] = min_inner;
            }
        }
        return dp[K][N];
    }
};

时间复杂度为：O(KN^2)，对于这道题会超时

转变思路
将原本K个鸡蛋，测试N层楼最少需要T次，转变为：K个鸡蛋T次机会最多可以测出N层楼，其中状态仍是鸡蛋是否破碎。我们还是以某个楼层数为基准，向下移动的时候，测出的层数为f(K-1,T-1)，向上移动的时候，测出的层数为f(K,T-1)，将向上移动的层数和向下移动的层数总和加1则是总层数。因此状态转移方程为N层楼 = f(鸡蛋数,机会) = f(鸡蛋数-1,机会-1) + f(鸡蛋数 ,机会-1) + 一层楼即f(K,T) = f(K-1,T-1) + f(K,T-1) + 1，其中当鸡蛋只有1个，只能测出T层高；当只有1次机会，无论多少颗鸡蛋，只能测出1层高。下面是代码：

class Solution {
public:
    int fun(int K, int T)   
    {
        if (T == 1)return 1;
        if (K == 1)return T;
        return fun(K - 1, T - 1) + fun(K, T - 1) + 1;
    }
    int superEggDrop(int K, int N)
    {
        int T = 1;  // 测试机会
        while (fun(K, T) < N) {
            ++T;
        }
        return T;
    }
};

上面的代码有子问题，可以用自底向上的形式进行优化:

class Solution {
public:
    int superEggDrop(int K, int N)
    {
        if (N == 1) {
            return 1;
        }
        int dp[105][10005];
        for (int i = 1; i <= K; ++i) {
            dp[i][1] = 1;
        }
        for (int i = 1; i <= N; ++i) {
            dp[1][i] = i;
        }
        for (int j = 2; j <= N; ++j) {
            for (int i = 2; i <= K; ++i) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + 1;
                if (dp[i][j] >= N)return j;
            }
        }
        return N;
    }
};

最后编辑于：2020.07.10 16:52:56