随心刷题计划

今日题解：

1. Two Sum

class Solution {
   
public:
    vector<int> twoSum(vector<int>& nums, int target) {
   
        int n = nums.size();
        for (int i = 0; i < n-1;i++){
   
            for (int j = 1; j < n;j++){
   
                if(nums[i]+nums[j]==target)
                    return {
   i, j};
            }
        }
        return {
   };
    }
};

2. Add Two Numbers

class Solution {
   
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
   
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
   
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            if (!head) {
   
                head = tail = new ListNode(sum % 10);
            } else {
   
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
   
                l1 = l1->next;
            }
            if (l2) {
   
                l2 = l2->next;
            }
        }
        if (carry > 0) {
   
            tail->next = new ListNode(carry);
        }
        return head;
    }
};

- 7. Reverse Integer

class Solution {
   
public:
    int reverse(int x) {
   
        int rev = 0;
        while (x != 0) {
   
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
   
                return 0;
            }
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev;
    }
};

- 9. Palindrome Number

class Solution {
   
public:
    bool isPalindrome(int x) {
   
        if(x<0)
            return false;
        else{
   
            vector<int> a;
            while(x){
   
                a.push_back(x % 10);
                x /= 10;
            }
            int flag = 1;
            for (int i = 0; i < a.size()/2;i++){
   
                if(a[i]!=a[a.size()-i-1]){
   
                    flag = 0;
                    break;
                }
            }
            if(flag)
                return true;
            else
                return false;
        }  
    }
};

class Solution {
   
public:
    bool isPalindrome(int x) {
   
        if(x<0)
            return false;
        else{
   
            long a=0,b=x;
            while(b){
   
                a=a*10+b%10;
                b/=10;
            }
            return a==x;
        }  
    }
};

- 13. Roman to Integer

class Solution {
   
public:
    int romanToInt(string s) {
   
        unordered_map<char, int> a = {
   //无序map
            {
   'I', 1},
            {
   'V', 5},
            {
   'X', 10},
            {
   'L', 50},
            {
   'C', 100},
            {
   'D', 500},
            {
   'M', 1000},
        };
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n;i++){
   
            int value = a[s[i]];
            if (i < n - 1 && value < a[s[i + 1]])
                ans -= value;
            else
                ans += value;
        }
        return ans;
    }
};

- 14. Longest Common Prefix

class Solution {
   
public:
    string longestCommonPrefix(vector<string>& strs) {
   
        if(!strs.size())
            return "";
        string ans = strs[0];
        for (int i = 1; i < strs.size();i++){
   
            string s = ans;
            ans = "";
            for (int j = 0; j < strs[i].size(); j++){
   
                if(s[j]==strs[i][j])
                    ans += s[j];
                else
                    break;
            }
            if(ans=="")
                break;
        }
        return ans;
    }
};

- 20. Valid Parentheses

class Solution {
   
public:
    bool isValid(string s) {
   
        stack<char> q;
        int n = s.size();
        for (int i = 0; i < n;i++){
   
            if(s[i]=='('||s[i]=='{'||s[i]=='['||q.empty())//越界访问注意！！！
                q.push(s[i]);
            else{
   
                if(s[i]==']'&&q.top()=='[')
                    q.pop();
                else if(s[i]=='}'&&q.top()=='{')
                    q.pop();
                else if(s[i]==')'&&q.top()=='(')
                    q.pop();
                else
                    q.push(s[i]);
            }
        }
        if(q.empty())
            return true;
        else
            return false;
    }
};

- 21. Merge Two Sorted Lists

class Solution{
   
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
   
    ListNode* head = new ListNode();        //头结点
    ListNode* l3 = head;                   //新链表
    while(l1 && l2 ){
   
        if(l1->val >= l2->val){
   
            l3->next =  l2;
            l2 = l2->next;
        }
        else{
      
            l3->next = l1;
            l1 = l1->next;
        }
        l3 = l3->next;       
    }
    l3->next = (l1 != NULL) ? l1 : l2;
    return head->next;
    }
};

class Solution{
   
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2){
   
        if(l1==nullptr)
            return l1;
        else if(l2==nullptr)
            return l2;
        else if(l1->val<l2->val){
   
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
   
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

- 26. Remove Duplicates from Sorted Array

class Solution {
   
public:
    int removeDuplicates(vector<int>& nums) {
   
        if(nums.size()<2)
            return nums.size();
        auto it = nums.begin() + 1;
        while(it!=nums.end()){
   
            if(*it==*(it-1))
                nums.erase(it);
            else
                it++;
        }
        return nums.size();
    }
};

class Solution {
   
public:
    int removeDuplicates(vector<int>& nums) {
   
        set<int>st(nums.begin(), nums.end());
        nums.assign(st.begin(), st.end());
        return nums.size();
    }
};

class Solution {
   
public:
    int removeDuplicates(vector<int>& nums) {
   
        int size = nums.size();
        if (size < 2)
            return size;
        int slow = 0;//重排指针
        for (int fast = 0; fast < size; fast++) {
   
            if (nums[slow] != nums[fast]) {
   
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;//[0]位置还有一个元素
    }
};

- 27. Remove Element

class Solution {
   
public:
    int removeElement(vector<int>& nums, int val) {
   
        auto it=nums.begin();
        while( it != nums.end()){
   
            if(*it==val)
                nums.erase(it);
            else
                it++;
        }
        return nums.size();
    }
};