LeetCode 算法系列：第 1 ~ 5 題

1.兩數之和

題目描述

給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那兩個整數，并傳回他們的數組下标。

你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素不能使用兩遍。

示例

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

是以傳回 [0, 1]

思路

第一種做法：循環倆次，依次周遊查找，時間複雜度為O(n^2)

第二種方法：使用哈希表，将出現過的數全部存到哈希表中，然後依次周遊哈希表中的值，判斷目标值減去x的值target - x是否存在即可，時間複雜度為O(n)

c++版本

vector<int> twoSum(vector<int>& nums, int target) {
       unordered_map<int, int> mp;
       for(int i =0;i<nums.size();i++)
       {
           int r = target - nums[i];
           if(mp.count(r))
                return {mp[r],i};
            mp[nums[i]]=i;
       } 
       return {};
    }

python版本

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        mp = {}
        for i, x in enumerate(nums):
            r = target - x
            if r in mp:
                return [mp[r], i]
            mp[x] = i
        return [];

2 兩數相加

題目描述

給出兩個非空的連結清單用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且它們的每個節點隻能存儲一位數字。

如果，我們将這兩個數相加起來，則會傳回一個新的連結清單來表示它們的和。

您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

思路

(模拟人工加法) O(n)

這是道模拟題，模拟我們小時候列豎式做加法的過程：

從最低位至最高位，逐位相加，如果和大于等于10，則保留個位數字，同時向前一位進1.

如果最高位有進位，則需在最前面補1.

做有關連結清單的題目，有個常用技巧：添加一個虛拟頭結點：ListNode *head = new ListNode(-1)，可以簡化邊界情況的判斷。

時間複雜度：由于總共掃描一遍，是以時間複雜度是 O(n).

c++版

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode * p = new ListNode(-1);
        ListNode * cur = p;
        int t = 0;
        while(l1 || l2 || t){
            if(l1) t += l1->val, l1 = l1->next;
            if(l2) t += l2->val, l2 = l2->next;
            cur->next = new ListNode(t % 10);
            cur = cur->next;
            t /= 10;
        }
        return p->next;
    }
};

python版本

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p = ListNode(-1)
        cur = p
        t = 0
        while(l1 or l2 or t):
            if l1:
                t += l1.val
                l1 = l1.next
            if l2:
                t += l2.val
                l2 = l2.next
            cur.next = ListNode(t % 10)
            cur = cur.next
            t /= 10
        return p.next
};

3. 無重複字元的最長子串

題目描述

給定一個字元串，請你找出其中不含有重複字元的最長子串的長度

示例1

輸入: “abcabcbb”

輸出: 3

解釋: 因為無重複字元的最長子串是 “abc”，是以其長度為 3。

示例2

輸入: “bbbbb”

輸出: 1

解釋: 因為無重複字元的最長子串是 “b”，是以其長度為 1。

示例3

輸入: “pwwkew”

輸出: 3

解釋: 因為無重複字元的最長子串是 “wke”，是以其長度為 3。

請注意，你的答案必須是子串的長度，“pwke” 是一個子序列，不是子串。

思路

(雙指針掃描) O(n)

定義兩個指針 i,j(i<=j)，表示目前掃描到的子串是 [i,j] (閉區間)。

掃描過程中維護一個哈希表unordered_map<char,int> hash，表示 [i,j]中每個字元出現的次數。

線性掃描時，每次循環的流程如下：

指針 j 向後移一位, 同時将哈希表中 s[j] 的計數加一: hash[s[j]]++;

假設 j 移動前的區間 [i,j]中沒有重複字元，則 j 移動後，隻有 s[j] 可能出現2次。

是以我們不斷向後移動 i，直至區間 [i,j]中 s[j] 的個數等于1為止；

複雜度分析：由于 i,j 均最多增加n次，且哈希表的插入和更新操作的複雜度都是 O(1)，

是以，總時間複雜度 O(n).

c++代碼

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
       unordered_map<char,int>mp;
       int ans =0;
       for(int i=0,j=0;j<s.size();j++)
       {
           mp[s[j]]++;
           while(mp[s[j]]>1)
           {
               mp[s[i++]]--;  
           }
           ans = max(ans,j-i+1);
       }
       return ans;
    }
};

python版本

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        mp={}
        ans=0
        i=0
        for j in range(len(s)):
            if s[j] in mp:
                mp[s[j]] +=1
            else:
                mp[s[j]]=1
            while(mp[s[j]]>1):
                mp[s[i]] -= 1
                i += 1
            ans = max(ans,j-i+1)
        return ans
        """
        :type s: str
        :rtype: int
        """

4. 尋找兩個正序數組的中位數

題目描述

給定兩個大小為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。

請你找出這兩個正序數組的中位數，并且要求算法的時間複雜度為 O(log(m + n))。

你可以假設 nums1 和 nums2 不會同時為空。

示例1

nums1 = [1, 3]

nums2 = [2]

則中位數是 2.0

示例2

nums1 = [1, 2]

nums2 = [3, 4]

則中位數是 (2 + 3)/2 = 2.5

思路

使用二分的做法求解

交換順序

     為了減少思考，我們先假定一個序列的長度總不大于第二個。如果大于了，那麼就交換一下。

怎麼二分查找呢？

     假設兩個序列按順序合并了，那麼中間點的位置就在(len1 + len2 + 1) // 2

假定這個理想中位數為x

     考慮一般情況下，第一個序列存在一個數，其左邊都是小于x，右邊都大于;對第二個序列也是一樣。

我們對這兩個數在各自序列的位置分别稱作mid1和mid2。

     是以我們首先先對第一個序列二分查找。

記錄左邊界，右邊界為第一個序列的左右邊界。

而查找的中間就是左右邊界的中間點。

對于mid2，便是(len1 + len2 + 1) // 2減去mid1

更新二分查找的條件

     mid1左側和mid2左側的數都應該比mid1和mid2對應的數小。

    是以可以肯定，如果mid2左側的數比mid1對應的數都大，那麼第一行的中間太靠左了。

可以這麼想，如果mid2左側的數比mid1對應的都大，那不如第二行的數選小一點而第一行的數選大一點，這樣兩個數會更接近。

要把第一行的中間往右，即二分查找的更新left。

反之更新right。套用模闆。

記得mid1不要越過上限！

c++版本

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0)
        {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
        else
        {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {
        if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
        if (nums1.size() == i) return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
        {
            return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else
        {
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
        }
    }
};

python版本

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1 = len(nums1)
        n2 = len(nums2)
        if n1 > n2:
            return self.findMedianSortedArrays(nums2,nums1)
        k = (n1 + n2 + 1)//2
        left = 0
        right = n1
        while left < right :
            m1 = left +(right - left)//2
            m2 = k - m1
            if nums1[m1] < nums2[m2-1]:
                left = m1 + 1
            else:
                right = m1
        m1 = left
        m2 = k - m1 
        c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )
        if (n1 + n2) % 2 == 1:
            return c1
        c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf"))
        return (c1 + c2) / 2

5 最長回文子串

題目描述

給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

示例1

輸入: “babad” 輸出: “bab” 注意: “aba” 也是一個有效答案。

示例 2：

輸入: “cbbd” 輸出: “bb”

思路

（暴力枚舉） O(n2)

由于字元串長度小于1000，是以我們可以用 O(n2) 的算法枚舉所有可能的情況。

首先枚舉回文串的中心 i，然後分兩種情況向兩邊擴充邊界，直到遇到不同字元為止:

回文串長度是奇數，則依次判斷 s[i−k]==s[i+k],k=1,2,3,…

回文串長度是偶數，則依次判斷 s[i−k]==s[i+k−1],k=1,2,3,…

如果遇到不同字元，則我們就找到了以 ii 為中心的回文串邊界。

時間複雜度分析：一共兩重循環，是以時間複雜度是 O(n2)。

c++版本

class Solution {
public:
 string longestPalindrome(string s) {
        int n = s.size();
        string ans ;
        int l = 0;
        for(int i =0;i<n;i++)
        {
                for(int k =0;i-k>=0&&i+k<n;k++)
                {
                   if(s[i-k]!=s[i+k])
                    break;
                    if(2*k+1>l)
                    {
                        ans = s.substr(i-k,2*k+1);
                        l = 2*k+1;
                    } 
                }


              for(int k =0;i-k>=0&&i+k+1<n;k++)
                {
                   if(s[i-k]!=s[i+k+1])
                    break;
                    if(2*(k+1)>l)
                    {
                        ans = s.substr(i-k,2*(k+1));
                        l = 2*(k+1);
                    } 
                }       
            }
        return ans;
    }
};

python版本

class Solution(object):
    def longestPalindrome(self, s):
    ans =""
        n = len(s)
        for i in range(n):
            for k in range(n):
                if i-k<0 or i+k>=n or s[i-k]!=s[i+k]:
                    break
                if(2*k+1>len(ans)):
                    ans = s[i-k:i+k+1]
            for k in range(n):
                if i-k<0 or i+k+1>=n or s[i-k]!=s[i+k+1]:
                    break
                if(2*(k+1)>len(ans)):
                    ans = s[i-k:i+k+2]
        return ans
         """
        :type s: str
        :rtype: str
        """

LeetCode 算法系列：第 1 ~ 5 題

目錄

1.兩數之和

2 兩數相加

3. 無重複字元的最長子串

4. 尋找兩個正序數組的中位數

5 最長回文子串

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希