Easy

20. Valid Parentheses

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        l = {'(':')','{':'}','[':']'}
        r = []
        if len(s)%2 !=0 :
            return False
        for x in s:
            if len(r) == 0:
                r.append(x)
            elif x == '(' or x == '{' or x == '[':
                r.append(x)
            elif r[-1] == ')' or r[-1] == '}' or r[-1] == ']':
                return False
            elif l[r.pop()] != x:
                return False
        if len(r) == 0:
            return True
        else:
            return False

21. Merge Two Sorted Lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
        struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
        struct ListNode* tail = head;
        head->next = NULL;
        while(l1 && l2)
        {
            if(l1->val <= l2->val)
            {
                tail->next = l1;
                tail = l1;
                l1 = l1->next;
            }
            else
            {
                tail->next = l2;
                tail = l2;
                l2 = l2->next;
            }
        }
        if(l1 == NULL && l2 == NULL) return head->next;
        if(l1 == NULL) tail->next = l2;
        if(l2 == NULL) tail->next = l1;
        return head->next;
}

13. Roman to Integer

class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        values = {
            "I" : 1, "V": 5, "X" : 10, "L" : 50, "C" : 100, "D" : 500, "M" : 1000
        }
        high = 0                        # highest value we have seen 
        result = 0                      # final result
        for letter in s[::-1]:          # letter in reverse order
            value = values[letter]      # integer value of the letter
            if value >= high:           # we found a value >= high and we sum it
                high = value            # record the new high
                result += value         # add value to result
            else:                       # we found a value < high so we subtract
                result -= value         # remove value from result
        return result

27. Remove Element

int removeElement(int* nums, int numsSize, int val) {
    int i;
    int r = 0;
    if(numsSize == 0)
        return 0;
    for(i=0; i<numsSize; i++){
        if(*(nums+i)!=val){
            *(nums+r) = *(nums+i);
            r++;
        }
    }
    return r;
}

35. Search Insert Position

int searchInsert(int* nums, int numsSize, int target) {
    int n = 0;
    int m = numsSize-1;
    int mid;
    while(n<=m){
        mid = (n+m)/2;
        if(*(nums+mid)>target)
            m = mid-1;
        else if(*(nums+mid)<target)
            n = mid+1;
        else
            return mid;
    }
   if (target > *(nums+mid))
       return mid + 1;
    else
        return mid;
}

67. Add Binary

class Solution
{
public:
    string addBinary(string a, string b)
    {
        string s = "";
        
        int c = 0, i = a.size() - 1, j = b.size() - 1;
        while(i >= 0 || j >= 0 || c == 1)
        {
            c += i >= 0 ? a[i --] - '0' : 0;
            c += j >= 0 ? b[j --] - '0' : 0;
            s = char(c % 2 + '0') + s;
            c /= 2;
        }
        
        return s;
    }
};

66. Plus One

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
	int n = digits.size();
	for (int i = n - 1; i >= 0; --i)
	{
		if (digits[i] == 9)
		{
			digits[i] = 0;
		}
		else
		{
			digits[i]++;
			return digits;
		}
	}
		digits[0] =1;
		digits.push_back(0);
        return digits;
    }
};

69. Sqrt(x)

int mySqrt(int x) {
    long r = x;
    while (r*r > x)
        r = (r + x/r) / 2;
    return r;
}

283. Move Zeroes

void moveZeroes(int* nums, int numsSize) {
    int i,j;
    for(i=0,j=0; i<numsSize; i++){
        if(*(nums+i)!=0){
            *(nums+j) = *(nums+i);
            j++;
        }
    }
    for(;j<numsSize;j++)
        *(nums+j) = 0;
}

28. Implement strStr()

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        return haystack.index(needle) if needle in haystack else -1

26. Remove Duplicates from Sorted Array

int removeDuplicates(int* nums, int numsSize) {
    int dup = -1000;
    int r=0;
    for(int i=0; i<numsSize; i++){
        if(*(nums+i)!=dup){
            *(nums+r) = *(nums+i);
            r++;
            dup = *(nums+i);
        }
    }
    return r;
}

80. Remove Duplicates from Sorted Array II

int removeDuplicates(int* nums, int numsSize) {
    int r = 0;
    int j = 0;
    int temp = -100;
    for(int i=0; i<numsSize; i++){
        if(*(nums+i)!=temp){
            j = 1;
            *(nums+r) = *(nums+i);
            r++;
            temp = *(nums+i);
        }else if(*(nums+i)==temp && j<2){
            *(nums+r) = *(nums+i);
            j++;
            r++;
        }
    }
    return r;
}

121. Best Time to Buy and Sell Stock

int maxProfit(int* prices, int pricesSize) {
    
    int min = *prices;
    int *result = (int *)malloc(sizeof(int)*pricesSize);
    for(int i=0; i<pricesSize; i++){
        min = min>*(prices+i)? *(prices+i):min;
        *(result+i) = *(result+i-1)>(*(prices+i)-min)? *(result+i-1):(*(prices+i)-min);
    }
    return *(result+pricesSize-1);
}

88. Merge Sorted Array

void merge(int* nums1, int m, int* nums2, int n) {
    
    while(m && n){
        if(*(nums1+m-1) <= *(nums2+n-1)){
            *(nums1+n+m-1) = *(nums2+n-1);
            n--;
        }else{
            *(nums1+n+m-1) = *(nums1+m-1);
            m--;
        }
    }
    while(n){
        *(nums1+n-1) = *(nums2+n-1);
        n--;
    }
    while(m){
        *(nums1+m-1) = *(nums1+m-1);
        m--;
    }
}

746. Min Cost Climbing Stairs

int minCostClimbingStairs(int* cost, int costSize) {
    int *result = (int *)malloc(sizeof(int)*(costSize+1));
    *result = 0;
    *(result+1) = 0;
    for(int i=2; i<costSize+1; i++){
        *(result+i) = (*(result+i-1)+*(cost+i-1))>(*(result+i-2)+*(cost+i-2))?(*(result+i-2)+*(cost+i-2)):(*(result+i-1)+*(cost+i-1));
    }
    return *(result+costSize);
}

70. Climbing Stairs

int climbStairs(int n) {
    int *result = (int *)malloc(sizeof(int)*n);
    *result = 1;
    *(result+1) = 2;
    if(n<3)
        return *(result+n-1);
    for(int i=2; i<n; i++){
        *(result+i) = *(result+i-1) + *(result+i-2);
    }
    return *(result+n-1);
}

53. Maximum Subarray

int maxSubArray(int* nums, int numsSize) {
    int *result = (int *)malloc(sizeof(int)*numsSize);
    *result = *nums;
    int max = *nums;
    for(int i=1; i<numsSize; i++){
        *(result+i) = *(nums+i) + (*(result+i-1)>0?*(result+i-1):0);
        max = max>*(result+i)? max:*(result+i);
    }
    return max;
}

303. Range Sum Query - Immutable

class NumArray:

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.accu = [0]
        for num in nums: 
            self.accu += self.accu[-1] + num,

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.accu[j + 1] - self.accu[i]

198. House Robber

int rob(int* nums, int numsSize) {
    int *result = (int *)malloc(sizeof(int)*numsSize);
    *result = *nums;
    *(result+1) = *(nums+1)>*(nums)?*(nums+1):*(nums);
    for(int i=2; i<numsSize; i++){
        *(result+i) = (*(result+i-2)+*(nums+i))>*(result+i-1)?(*(result+i-2)+*(nums+i)):*(result+i-1);
    }
    return *(result+numsSize-1);
}

680. Valid Palindrome II

class Solution:
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        j = len(s)-1
        i = 0
        while s[i]==s[j]:
            if i>=j:
                return True
            i+=1
            j-=1
        c = i
        p = j
        if s[i] == s[j-1]:
            j -= 1
            while s[i]==s[j]:
                if i>=j:
                    return True
                i+=1
                j-=1
        if s[c+1] == s[p]:
            c += 1
            while s[c]==s[p]:
                if c>=p:
                    return True
                c+=1
                p-=1
            return False
        else:
            return False

125. Valid Palindrome

import re
class Solution:
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s=re.sub('[^a-zA-Z0-9]+', '', s.lower())
        return s[::-1] == s

633. Sum of Square Numbers

bool judgeSquareSum(int c) {
    //interesting approach 
    
    int left = 0;
    int right = (int)sqrt(c);
        
    while (left <= right) {
        
        if (left * left + right *right < c) {
            left++;
        } else if (left * left + right *right > c) {
            right--;
        } else {
            return true;
        }
    }
    return false;
}

633. Sum of Square Numbers

bool isPerfectSquare(int num) {
    long r = num;
    while (r*r > num)
        r = (r + num/r) / 2;
    if(r*r==num)
        return true;
    else
        return false;
}

234. Palindrome Linked List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return True
        lis = []
        p = head
        while p != None:
            lis.append(p.val)
            p = p.next
        return lis == lis[::-1]

167. Two Sum II - Input array is sorted

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int* res = malloc(sizeof(int)*2);
    int i = 0;
    int j = numbersSize - 1;
    if(i>=j) return NULL;
    while(i<j){
        if(numbers[i] + numbers[j] == target){
            res[0] = i+1;
            res[1] = j+1;
            break;
        }
        if(numbers[i] + numbers[j] > target)
            j--;
        else
            i++;
    }
    
    *returnSize = 2;   //题目要求返回returenSize的值，如果不给returnSize值，数组为空
    return res;
}

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        r = list(str(x))
        r.reverse()
        s = list(str(x))
        return r==s
        

7. Reverse Integer

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        s = cmp(x, 0)
        r = int(`s*x`[::-1])
        return s*r * (r < 2**31)

771. Jewels and Stones

int numJewelsInStones(char* J, char* S) {
    char symbol[128] = {0};
    char sum = 0;
    for(int i=0; *(S+i)!='\0'; i++){
        symbol[*(S+i)]++;
    }
    for(int i=0; *(J+i)!='\0'; i++){
        sum += symbol[*(J+i)];
    }
    return sum;
}

709. To Lower Case

char* toLowerCase(char* str) {
    int i = 0;
    while(*(str+i)!='\0'){
        if(*(str+i)>=65 && *(str+i)<=90)
            *(str+i)+=32;
        i++;
    }
    return str;
}

821. Shortest Distance to a Character

class Solution:
    def shortestToChar(self, S, C):
        """
        :type S: str
        :type C: str
        :rtype: List[int]
        """
        h = C[0]
        xplace = [i for i in range(len(S)) if S[i]==h]
        r = [abs(x-xplace[0]) for x in range(len(S))]
        for i in xplace:
            r = [min(r[x],abs(x-i)) for x in range(len(S))]
        return r

868. Binary Gap

class Solution:
    def binaryGap(self, N):
        """
        :type N: int
        :rtype: int
        """
        nbin = bin(N)[2:]
        m = 0
        oneplace = [c for c in range(len(nbin)) if nbin[c] == '1']
        for i in range(len(oneplace)-1):
            m = oneplace[i+1]-oneplace[i] if (oneplace[i+1]-oneplace[i])>m else m
        return m

500. Keyboard Row

class Solution:
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        r1, r2, r3 = set('qwertyuiop'), set('asdfghjkl'), set('zxcvbnm')
        res = []
        for word in words:
            w = set(word.lower())
            if w.issubset(r1) or w.issubset(r2) or w.issubset(r3):
                res.append(word)
        return res

766. Toeplitz Matrix

class Solution:
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        for idx, row in enumerate(matrix):
            if idx == 0:
                pass
            elif row[1:] != matrix[idx-1][0:-1]:
                return False
        return True

575. Distribute Candies

class Solution:
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        return min(len(set(candies)), len(candies)//2)

412. Fizz Buzz

class Solution:
    def fizzBuzz(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        r = []
        for i in range(1,n+1):
            if i%3==0 and i%5!=0:
                r.append("Fizz")
            elif i%3!=0 and i%5==0:
                r.append("Buzz")
            elif i%3==0 and i%5==0:
                r.append("FizzBuzz")
            else:
                r.append(str(i))
        return r

206. Reverse Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
            return head;
    }
    struct ListNode* newhead = NULL;
    struct ListNode* temp1 = head;
    struct ListNode* temp2 = head->next;
    while(temp2){
        temp1->next = newhead;
        newhead = temp1;
        temp1 = temp2;
        temp2 = temp2->next;
    }
    temp1->next = newhead;
    newhead = temp1;
    return newhead;
}

669. Trim a Binary Search Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* trimBST(struct TreeNode* root, int L, int R) {
    if(root==NULL)
        return root;
    if(root->val > R)
        return trimBST(root->left, L, R);
    if(root->val < L)
        return trimBST(root->right, L, R);
    // root->left = trimBST(root->right, L, R);
    // root->right = trimBST(root->right, L, R);
    root->left = L == root->val ? NULL : trimBST(root->left, L, R);
    root->right = R == root->val ? NULL : trimBST(root->right, L, R);
    return root;
}