有趣的算法题01

为提升算法、编程能力，开始刷LeetCode，一些于我有益的题记录在此系列中（或许对大佬们而言尽是些简单的题，还请见谅）。
A good programmer is someone who looks both ways before crossing a one-way street. --Doug Linder, systems administrator

[多数元素] -- 摩尔投票法

【问题描述】

给定一个数组，寻找其中出现次数大于一半的多数元素（假设数组不为空，总存在这样的多数元素），参LeetCode 169. 多数元素。

【解法思路】

计数取值：遍历整个数组，取出计数最大的那个，简单粗暴。
排序取中间值：先对数组进行排序，然后中间的那个数一定是多数元素。

摩尔投票法：一种线性时间($O(n)$)和常数空间求解多数元素的算法，简单来说，两两删除数组中不同的元素，最终剩下的一定是多数元素，需要维护一个元素和一个计数器。C++实现如下：

public int majorityElement(vectirs<int>& nums){
  int num = nums[0];
  int count = 1;
  for(int i=1; i<nums.size(); i++){
    if(num == nums[i]) count++;
    else{
      count--;
      if(count ==0){
        i++;
        num = nums[i];
        count = 1;
      }
    }
  }
  
  return num;
}

[最长上升子序列] -- 动态规划算法

【问题描述】

给定一个无序数组，寻找其最长上升子序列的长度，参LeetCode 300. 最长上升子序列。

【解法思路】

暴力遍历（时间复杂度$O(2^n)$，我好傻）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int max =0;
        longestlength(nums, max, 0, INT_MIN, 0);
        return max;
    }

    void longestlength(vector<int>& nums, int& max, int count, int temp, int num){
        for(int i=num; i<nums.size(); i++){
            if(temp<nums[i]){
                longestlength(nums, max, count+1, nums[i], i+1);
            }
        }
        if(max<count) max=count;
    }
};

动态规划（时间复杂度$O(n^2)$）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len==0) return 0;
        int max = 1;

        int count[len];
        for(int i=0; i<len; i++){
            count[i] = 1;
        }

        for(int i=0; i<len; i++){
            for(int j=0; j<i; j++){
                if(nums[j]<nums[i] && (count[i]<count[j]+1)){
                    count[i] = count[j]+1;
                }
            }
            if(count[i]>max)
                max = count[i];
        }

        return max;
    }
};

二分查找（时间复杂度$O(n\log n)$，将动态规划方法的内层循环改为二分查找）

[水壶问题]

【问题描述】

有一个容量分别为x升和y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好z升的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的k升水。
可以：
- 装满任意一个水壶；
- 清空任意一个水壶；
- 从一个水壶向另一个水壶倒水，直到装满或者倒空。
参LeetCode 365. 水壶问题

【解法思路】

BFS 广度优先搜索/DFS 深度优先搜索
- （填满第一个桶，填满第二个桶，倒空第一个桶，倒空第二个桶，把第一个桶倒入第二个桶，把第二个桶倒入第一个桶）
- 加上存储搜索过的状态，哦NO...
- 时间复杂度$O(xy)$，空间复杂度$O(xy) $
裴蜀定理（贝祖定理）
- 定理：若$a,b$是整数，且$\gcd(a,b)=d$，那么对于任何的整数$x,y$，有$ax+by$一定是$d$的倍数。
- 此题，等价于求是否存在整数$a,b$使得$ax+by=z$，即，$z$是否是$x,y$的最大公约数的倍数。
- 时间复杂度$O(\log(\min(x,y)))$，空间复杂度$O(1)$。