有趣的算法02

有趣的算法02

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

Pure mathematics is, in this way, the poetry of logical ideas. -- Einstein

[使数组惟一的最小增量]

【问题描述】

​ 给定一个整数数组，每次move操做能够数组中任意元素，将其增1。问move操做数最少能够为多少，使数组中每一个数都是惟一的，参LeetCode 945. 使数组惟一的最小增量。算法

【解法思路】

1. 先排序，后遍历：时间复杂度$O(n\log n)$编程

   public int minIncrementForUnique(vector<int>& A) {
     //先排序
       sort(A.begin(), A.end());
     int count = 0;
     
     //再遍历，若当前元素小于等于前一个，则变为前一个元素加1
     for(int i=1; i<A.size(); i++){
       if(A[i]<=A[i-1]){
         count += A[i-1]+1-A[i];
         A[i] = A[i-1]+1;
       }
     }
     
     return count;
   }

2. 计数排序，用空间换时间：时间复杂度$O(n)$数组

   public int minIncrementForUnique(vector<int>& A) {
     int counter[50000] = {0};
     
     //计数
     for(int i=0; i<A.size(); i++){
       counter[A[i]]++;
     }
     int count = 0;
     
     //若是同一个数的数量n大于1，则将n-1个数移入下一个位置
     for(int i=0; i<50000; i++){
       if(counter[i]>1){
         count+=counter[i]-1;
         counter[i+1]+=counter[i]-1;
       }
     }
   
     return count;
   }

3. 寻找空位，填入数值：时间复杂度$O(n)$

[链表的中间节点]--快慢指针

【问题描述】

​ 已知一个非空单链表的头指针head，要求返回链表的中间节点（如有两个中间节点，则返回第二个中间节点），参LeetCode 876. 链表的中间结点ide

【解法思路】

1. 遍历链表获得长度，找到中间长度，再遍历获得。this

   ListNode* middleNode(ListNode* head) {
           int count = 0;
           int runNum = 0;
           ListNode *p = head;
   
           while (p->next != NULL) {
               p = p->next;
                       ++count;
           }
   
           runNum = (count + 1) / 2 + 1;
           p = head;
   
           for (count = 1; count < runNum; ++count) {
               p = p->next;
           }
   
           return p;
       }

2. 使用快慢指针，快指针一次走两步，慢指针一次走一步。编码

   public ListNode* middleNode(ListNode* head) {
     ListNode* fast = head;
     ListNode* slow = head;
     
     while (fast != NULL && fast->next!=NULL) {
       fast = (fast->next)->next;
       slow = slow->next;
     }
     
     return slow;
   }

[打家劫舍]--动态规划

【问题描述】

​ 给定一个非负整数数组，按序找出一个相邻两数在原数组中不相邻的子序列，求最大和，参LeetCode 198. 打家劫舍。idea

【解法思路】

• 典型的动态规划问题，每次有偷和不偷两种选择，能够写出状态转移方程：${\rm dp}[i]=\max({\rm dp}[i-1],{\rm dp}[i-2]+{\rm nums}[i])$

• 编码实现以下：指针

  public int rob(vector<int>& nums) {
    vector<int> dp(nums.size(),0);
    
    if(nums.size()==0) return 0;
    else if(nums.size()==1) return nums[0];
    
    dp[0] = nums[0];
    dp[1] = max(nums[0],nums[1]);
    for(int i=2; i<nums.size(); i++){
      dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
    }
  
    return dp[nums.size()-1];
  }

继续，继续～