# Easy

{% code title="20. Valid Parentheses" %}

```python
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
```

{% endcode %}

{% code title="21. Merge Two Sorted Lists" %}

```c
/**
 * 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;
}
```

{% endcode %}

{% code title="13. Roman to Integer " %}

```python
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

```

{% endcode %}

{% code title="27. Remove Element" %}

```c
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;
}
```

{% endcode %}

{% code title="35. Search Insert Position" %}

```c
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;
}
```

{% endcode %}

{% code title="67. Add Binary" %}

```cpp
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;
    }
};
```

{% endcode %}

{% code title="66. Plus One" %}

```cpp
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;
    }
};
```

{% endcode %}

{% code title="69. Sqrt(x)" %}

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

{% endcode %}

{% code title="283. Move Zeroes" %}

```c
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;
}
```

{% endcode %}

{% code title="28. Implement strStr()" %}

```python
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
```

{% endcode %}

{% code title="26. Remove Duplicates from Sorted Array" %}

```c
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;
}
```

{% endcode %}

{% code title="80. Remove Duplicates from Sorted Array II" %}

```c
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;
}
```

{% endcode %}

{% code title="121. Best Time to Buy and Sell Stock" %}

```c
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);
}
```

{% endcode %}

{% code title="88. Merge Sorted Array" %}

```c
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--;
    }
}
```

{% endcode %}

{% code title="746. Min Cost Climbing Stairs" %}

```c
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);
}
```

{% endcode %}

{% code title="70. Climbing Stairs" %}

```c
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);
}
```

{% endcode %}

{% code title="53. Maximum Subarray" %}

```c
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;
}
```

{% endcode %}

{% code title="303. Range Sum Query - Immutable" %}

```python
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]
```

{% endcode %}

{% code title="198. House Robber" %}

```c
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);
}
```

{% endcode %}

{% code title="680. Valid Palindrome II" %}

```python
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

```

{% endcode %}

{% code title="125. Valid Palindrome" %}

```python
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
```

{% endcode %}

{% code title="633. Sum of Square Numbers" %}

```c
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;
}
```

{% endcode %}

{% code title="633. Sum of Square Numbers" %}

```c
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;
}
```

{% endcode %}

{% code title="234. Palindrome Linked List" %}

```python
# 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]

```

{% endcode %}

{% code title="167. Two Sum II - Input array is sorted" %}

```python
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;
}

```

{% endcode %}

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

{% code title="7. Reverse Integer" %}

```python
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)

```

{% endcode %}

{% code title="771. Jewels and Stones" %}

```c
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;
}
```

{% endcode %}

{% code title="709. To Lower Case" %}

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

{% endcode %}

{% code title="821. Shortest Distance to a Character" %}

```python
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
```

{% endcode %}

{% code title="868. Binary Gap" %}

```python
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
```

{% endcode %}

{% code title="500. Keyboard Row" %}

```python
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
```

{% endcode %}

{% code title="766. Toeplitz Matrix" %}

```python
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
```

{% endcode %}

{% code title="575. Distribute Candies" %}

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

{% endcode %}

{% code title="412. Fizz Buzz" %}

```python
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
```

{% endcode %}

{% code title="206. Reverse Linked List" %}

```c
/**
 * 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;
}
```

{% endcode %}

{% code title="669. Trim a Binary Search Tree" %}

```c
/**
 * 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;
}
```

{% endcode %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://home2asa.gitbook.io/asa2leetcode/easy.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.