有趣的算法题01

有趣的算法题01

​ 为提升算法、编程能力，开始刷LeetCode，一些于我有益的题记录在此系列中（或许对大佬们而言尽是些简单的题，还请见谅）。

A good programmer is someone who looks both ways before crossing a one-way street. --Doug Linder, systems administrator

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

【问题描述】

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

【解法思路】

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

3. 摩尔投票法：一种线性时间($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. 最长上升子序列。

【解法思路】

1. 暴力遍历（时间复杂度$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;
       }
   };

2. 动态规划（时间复杂度$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;
       }
   };

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

[水壶问题]

【问题描述】

• 有一个容量分别为x升和y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好z升的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的k升水。

• 可以：

  • 装满任意一个水壶；
  • 清空任意一个水壶；
  • 从一个水壶向另一个水壶倒水，直到装满或者倒空。
• 参LeetCode 365. 水壶问题

【解法思路】

1. BFS 广度优先搜索/DFS 深度优先搜索

   • （填满第一个桶，填满第二个桶，倒空第一个桶，倒空第二个桶，把第一个桶倒入第二个桶，把第二个桶倒入第一个桶）
   • 加上存储搜索过的状态，哦NO...
   • 时间复杂度$O(xy)$，空间复杂度$O(xy) $

2. 裴蜀定理（贝祖定理）

   • 定理：若$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)$。

加油加油！