647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/
Solution 1. Moving the center of the palindrome and count.
    int countSubstrings(string s) {
        int n = s.size();
        int res = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; i-j>=0 && i+j<n; j++) {
                if(s[i-j] == s[i+j]) res++;
                else break;
            }
            for(int j=0; i-j>=0 && i+j+1<n; j++) {
                if(s[i-j] == s[i+j+1]) res++;
                else break;
            }
        }
        return res;
    }
Solution 2. Recursion. Slow because of duplicated comparisons.
    int count(string& s, int n) {
        if(n<2) return n;
        int m = count(s, n-1);
        for(int lo = 0; lo<n; lo++) {
            int i=lo, j = n-1;
            for(; i<=j; i++, j--) {
                if(s[i]!=s[j]) break;
            }
            m += i>j;
        }
        return m;
    }
    int countSubstrings(string s) {
        return count(s, s.size());
    }

125. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/description/
    bool isPalindrome(string s) {
        if(s.size()<2) return true;
        for(int i=0, j=s.size()-1; i<j;) {
            char a = tolower(s[i]);
            char b = tolower(s[j]);
            if(!(a>='a'&&a<='z') && !(a>='0'&&a<='9')) { i++; continue;}
            if(!(b>='a'&&b<='z') && !(b>='0'&&b<='9')) { j--; continue;}
            if(a!=b) return false;
            i++;
            j--;
        }
        return true;
    }

680. Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/description/
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
    bool valid(string& s, int i, int j, int del) {
        if(del == 2) return false;
        if(i>=j) return true;
        if(s[i]!=s[j])
            return valid(s, i+1, j, del+1) || valid(s, i, j-1, del+1);
        else return valid(s, i+1, j-1, del);
    }
    bool validPalindrome(string s) {
        return valid(s, 0, s.size()-1, 0);
    }

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/description/
Solution 1. Use a recursive call to check the values. The call stack acts as a stack for the node values, which access the node values backwardly. At the same time, use a pointer p to access the node values forwardly. O(n) in space.
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        return check(head, p);
    }
    bool check(ListNode* node, ListNode*& p) {
        if(!node) return true;
        bool isNext = check(node->next,p) && (node->val == p->val);
        p = p->next;
        return isNext;
    }
Solution 2. O(1) space?
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        ListNode* slow = head, * fast = head, *p;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = reverseList(slow->next);
        slow->next = fast;
        p = head;
        while(fast) {
            if(p->val != fast->val) return false;
            p = p->next;
            fast = fast->next;
        }
        slow->next = reverseList(slow->next);
        return true;
    }
    ListNode* reverseList(ListNode* head){
        ListNode* hd = nullptr, * next;
        while(head) {
            next = head->next;
            head->next = hd;
            hd = head;
            head = next;
        }
        return hd;
    }

1. Two Sum

https://leetcode.com/problems/two-sum/description/
Solution 1. Sort the index according to its value using lambda expression and search. (6 ms)
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> idx(nums.size(),0);
        for(int i=0; i<idx.size(); i++) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int i, int j){return nums[i]<nums[j];});
        for(int i=0, j=idx.size()-1; i<j;) {
            int x = nums[idx[i]]+nums[idx[j]];
            if(x == target) return {idx[i], idx[j]};
            else if(x>target) j--;
            else i++;
        }
        return {};

    }
Solution 2. Use a map: target - nums[i] -> i. (12 ms)
    vector<int> twoSum(vector<int>& nums, int target) {
        if(nums.size()<2) return {};
        unordered_map<int,int> mp;
        mp[target-nums[0]] = 0;
        for(int i=1; i<nums.size(); i++){
            if(mp.count(nums[i])) return {mp[nums[i]], i};
            else mp[target-nums[i]] = i;
        }
        return {};
    }

9. Palindrome Number

https://leetcode.com/problems/palindrome-number/description/
Solution 1. Only compare half digits (fastest). Corner cases are (x!=0 && x%10 == 0).
    bool isPalindrome(int x) {
        if(x<0 || (x!=0 && x%10==0)) return false;
        int y = 0;
        while(x>y) {
            y = y*10 + (x%10);
            x /= 10;
        }
        return x == y || (x == y/10);
    }
Solution 1.1 Reverse whole number
    bool isPalindrome(int x) {
        if(x<0) return false;
        int a = x;
        int y = 0;
        while(a) {
            y = y*10 + (a%10);
            a /= 10;
        }
        return x == y;
    }
Solution 2. Covert to string and compare it to its reverse.
    bool isPalindrome(int x) {
        if(x<0) return false;
        string s = to_string(x);
        string t = s;
        reverse(begin(t),end(t));
        return s == t;
    }
Solution 2.1 Two pointers for string.
    bool isPalindrome(int x) {
        if(x<0) return false;
        string s = to_string(x);
        for(int i=0, j=s.size()-1;i<j; i++,j--){
            if(s[i] != s[j]) return false;
        }
        return true;
    }

643. Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/
Solution 1. Sliding window.
double findMaxAverage(vector<int>& nums, int k) {
        int start = 0, end = 0, sum = 0, res = INT_MIN;
        while(end < nums.size()) {
            sum += nums[end];
            if(end - start + 1 == k) {
                res = max(sum, res);
                sum -= nums[start++];
            }
            end++;
        }
        return (double)res/(double)k;
    }
or,
    double findMaxAverage(vector<int>& nums, int k) {
        int mx = 0, s = 0, i = 0, j = 0;
        for(j=0; j<k; j++) s += nums[j];
        mx = s;
        while(j < nums.size()) {
            s = s - nums[i++] + nums[j++];
            mx = max(mx, s);
        }
        return double(mx)/k;
    }

27. Remove Element

https://leetcode.com/problems/remove-element/description/
Solution 1. Move nums[i] to nums[j] if it does not equal val. Index 0~j-1 contains all the numbers that are different from index 0~i-1. (3ms)
    int removeElement(vector<int>& nums, int val) {
        int i, j;
        for(i=0, j=0; i<nums.size(); i++) {
            if(nums[i] != val) {
                nums[j++] = nums[i];
            }
        }
        return j;      
    }
Solution 2. Move the numbers equal to val to the end of array.
Swap nums[i] with the  nums[j] if it equals val and decrease j. Numbers with index>j are then equal to val. (6ms)
    int removeElement(vector<int>& nums, int val) {
        int i, j;
        for(i=0, j=nums.size()-1; i<=j; i++) {
            if(nums[i] == val) {
                swap(nums[i], nums[j]);
                i--;
                j--;
            }
        }
        return i;      
    }

541. Reverse String II

https://leetcode.com/problems/reverse-string-ii/description/
Solution 1.
    string reverseStr(string s, int k) {
        for(int i=0; i<s.size(); i += 2*k) {
            reverse(s.begin()+i, min(s.begin()+i+k, s.end()));
        }
        return s;
    }
Solution 2.
    string reverseStr(string s, int k) {
        for(int i=0; i<s.size(); i += 2*k) {
            for(int m=i, n=min(i+k-1, (int)s.size()-1);m<n;m++,n--) {
                swap(s[m], s[n]);
            }
        }
        return s;
    }

167. Two Sum II - Input array is sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
Solution 1. Use two pointers to search the array
   vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        for(int i=0,j=numbers.size()-1;i<j;) {
            if(numbers[i]+numbers[j] == target) {
                res={i+1,j+1};
                break;
            }
            else if(numbers[i]+numbers[j] < target) i++;
            else j--;
        }
        return res;
    }
Solution 2. Construct a map from value to its index
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int,int> m;
        for(int i=0; i<numbers.size();i++) {
            if(m.find(target-numbers[i])!=m.end())
                return vector<int> {m[target-numbers[i]]+1,i+1};
            m[numbers[i]] = i;
        }
    }