LeetCode刷題筆記-資料結構-day1

136. 只出現一次的數字

1.題目描述

原題鏈接：136. 只出現一次的數字

2.解題思路

演算法：位運算

題目這里要求演算法應該具有線性時間復雜度，而且不使用額外空間，

因為只有一個元素出現一次，其余都是兩次，這里可以用位運算，

這里用異或運算^就行，異或運算的性質：

1. 任何數和 0 做異或運算，結果仍然是原來的數， a ⊕ 0 = a a \oplus 0=a a⊕0=a
2. 任何數和其自身做異或運算，結果是 0， a ⊕ a = 0 a \oplus a=0 a⊕a=0
3. 異或運算滿足交換律和結合律， a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ ( a ⊕ a ) = b ⊕ 0 = b a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus0=b a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b

這里用了異或運算，出現兩次的數都會抵消，最后的結果就是答案，

3.代碼

class Solution {
    public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(auto x:nums){
            res^=x;
        }
        return res;
    }
};

169. 多數元素

1.題目描述

原題鏈接：169. 多數元素

2.解題思路

演算法：投票演算法

題目要求：嘗試設計時間復雜度為 O(n)、空間復雜度為 O(1) 的演算法解決此問題，

具體思路：

因多數元素是指在陣列中出現次數大于陣列個數一半的元素，這里可以使用投票演算法，

維護兩個變數：候選人和他的票數

1. 候選人初始化為 t= 0，票數sum初始化為0
2. 當票數為0時，更換候選人，將票數重置為1
3. 向后遍歷陣列，遇到相同元素票數加1，否則減1
4. 遍歷完陣列，當前候選人即為陣列中出現的多數元素

3.代碼

class Solution {
    public:
    int majorityElement(vector<int>& nums) {
        int t=0,sum=0;
        for(auto x:nums){
            if(sum==0) t=x,sum++;
            else if(x==t) sum++;
            else sum--;
        }
        return t;
    }
};

15. 三數之和

1.題目描述

原題鏈接：15. 三數之和

2.解題思路

演算法：排序+雙指標

具體思路：

1. 先對陣列進行排序
2. 列舉每個數，表示該數a[i]已被確定，在排序后的情況下，通過雙指標j，k分別從j=i+1和k=n-1向中間列舉，找到a[i] + a[j] + a[k] == 0的所有符合條件的搭配，
3. 由于陣列排序后是從小到大的，假設sum = a[i] + a[j] + a[k]，則有：
   • 若sum > 0，則k往左走，使sum變小
   • 若sum < 0，則j往右走，使sum變大
   • 若sum == 0，則表示找到了與nums[i]搭配的組合nums[j]和nums[k]，存到res中
4. 題目需要保證不含重復的答案，這里需要判重：
   • 列舉i時，如果i不是第一個列舉的，需要保證不和前一個i的值相同，
   • 同理，列舉j時，如果j不是第一個列舉的，需要保證不和前一個j的值相同，

3.代碼

class Solution {
    public:
    vector<vector<int>> threeSum(vector<int>& a) {
        vector<vector<int>> res;
        int n=a.size();
        sort(a.begin(),a.end());

        for(int i=0;i<n;i++){
            //防止重復
            if(i>0&&a[i]==a[i-1]) continue;
            for(int j=i+1,k=n-1;j<k;j++){
                //防止重復
                if(j!=i+1&&a[j]==a[j-1]) continue;
                while(j<k&&a[i]+a[j]+a[k]>0) k--;
                if(j<k&&a[i]+a[j]+a[k]==0)
                    res.push_back({a[i],a[j],a[k]});
            }
        }
        return res;
    }
};