# EASY
###### Tags: `Leetcode`, `Easy`
## 9. Palindrome Number
> Given an integer x, return true if x is palindrome integer. An integer is a palindrome when it reads the same backward as forward.
> For example, 121 is a palindrome while 123 is not.
**!!Answer!!**
```c++=
[C++]
class Solution {
public:
bool isPalindrome(int x) {
int record = x;
int flag = 1;
while(record%10>9){
record = record%10;
flag++;
}
int * array;
array = new int [flag-1];
int n = flag;
int i = 0;
while(n>0){
array[i++] = record%10;
record = record%10;
}
if (flag%2==1){
for(int i = 0; i<flag/2; i++){
if(array[i]!=array[flag/2]) return false;
}
}
else if (flag%2==0){
for(int i = 0; i<=flag/2; i++){
if(array[i]!=array[flag/2]) return false;
}
}
delete [] array;
return true;
}
};
```
```c=
bool isPalindrome(int x){
if(x<0)return false;
if(x==0)return true;
int i, temp, count=0;
char *arr = (char*)malloc(10*sizeof(char*));
while(x!=0){
temp=x%10;
arr[count]=temp;
count++;
x/=10;
}
for(i=0;i<count/2;i++){
if(arr[i]!=arr[count-1-i]) return false;
}
return true;
}
```
---
## 20. Valid Parentheses
###### Tags: `Leetcode`, `Easy`
> Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
> An input string is valid if:
> Open brackets must be closed by the same type of brackets.
> Open brackets must be closed in the correct order.
> Note that an empty string is also considered valid.
Example 1:
```
Input: "()"
Output: true
```
Example 2:
```
Input: "()[]{}"
Output: true
```
Example 3:
```
Input: "(]"
Output: false
```
Example 4:
```
Input: "([)]"
Output: false
```
Example 5:
```
Input: "{[]}"
Output: true
```
**!!Answer!!**
**Result**
> Runtime: 64 ms, faster than 99.94% of C# online submissions.
> Memory Usage: 21.2 MB, less than 6.38% of C# online submissions.
> Time Complexity: O(n)
> Space Complextiy: O(1)
```c++=
class Solution {
public:
bool isValid(string s) {
stack<char>istrue;
if (s.Length() % 2 == 1) return false;
for(int i=0;i<s.length();i++){
switch(s[i]){
case '(':{istrue.push('(');break;}
case '[':{istrue.push('[');break;}
case '{':{istrue.push('{');break;}
case ')':{
if(istrue.size()==0||istrue.top()!='(')
return false;
istrue.pop();
break;
}
case ']':{
if(istrue.size()==0||istrue.top()!='[')
return false;
istrue.pop();
break;
}
case '}':{
if(istrue.size()==0||istrue.top()!='{')
return false;
istrue.pop();
break;
}
}
}
if(istrue.size()!=0)
return false;
return true;
}
};
```
```c=
bool isValid(char * s){
char stack[10000]= { 0 };
int top = 0;
while(*s) {
if(*s == '(')
stack[top++] = *s + 1;
else if(*s == '[' || *s == '{')
stack[top++] = *s + 2;
else if(top == 0)
return false;
else if(stack[top - 1] == *s)
top--;
else
return false;
s++;
}
return top == 0;
}
```
---
## 496. Next Greater Element I
> The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
>
> You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
>
> For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
>
> Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example 1:
```c
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
---
```
Example 2:
```c
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.
```
**!!Answer!!**
```C++=
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> rest(findNums.size());
for (int i = 0; i < findNums.size(); ++i) {
int j = 0, k = 0;
//to find where is the findNums[i] in nums, then pass the location to next for loop
for (; j < nums.size(); ++j) {
if (nums[j] == findNums[i]) break;
}
//find if the value of nums[j+1] is greater than findNums[i], then return value
for (k = j + 1; k < nums.size(); ++k) {
if (nums[k] > nums[j]) {
rest[i] = nums[k];
break;
}
}
//if findNums[i] is greater than nums[j+1], then return -1
if (k == nums.size()) rest[i] = -1;
}
return rest;
}
};
```
---
**2022/05/29**
## 26. Remove Duplicates from Sorted Array
> Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. Return k after placing the final result in the first k slots of nums. Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Custom Judge:
The judge will test your solution with the following code:
```
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
```
```c=
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
```c=
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
**!!Answer!!**
```c=
int removeDuplicates(int* nums, int numsSize){
int count = 1;
int tmp = nums[0];
for(int i = 1; i < numsSize; i++){
if(tmp != nums[i])
{
tmp = nums[i];
nums[count++] = nums[i];
}
}
return count;
}
```
==CKD==
```c=
int removeDuplicates(int* nums, int numsSize){
int i = 0, j = 1;
int temp = nums[0]; // first element
while(i < numsSize) {
if(temp != nums[i]) {
temp = nums[i];
nums[j] = nums[i];
j++;
}
i++;
}
return j;
}
```
---
## 35. Search Insert Position
> Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
> You must write an algorithm with O(log n) runtime complexity.
Example 1:
```
Input: nums = [1,3,5,6], target = 5
Output: 2
```
Example 2:
```
Input: nums = [1,3,5,6], target = 2
Output: 1
```
Example 3:
```
Input: nums = [1,3,5,6], target = 7
Output: 4
```
**Constraints:**
> 1 <= nums.length <= 104
> 104 <= nums[i] <= 104
> nums contains distinct values sorted in ascending order.
104 <= target <= 104
**!!Answer!!**
> Runtime: 4 ms, Memory Usage: 6.2 MB.
```c=
int searchInsert(int* nums, int numsSize, int target){
int i = 0;
while(i < numsSize){
if(target<=nums[0]) break;
else if(target>nums[numsSize-1]){
i = numsSize;
break;
}
else if(target>nums[i] && target<=nums[i+1]){
i += 1;
break;
}
}
i++;
return i;
}
```
>Runtime: 4 ms, Memory Usage: 5.9 MB.
```c=
int searchInsert(int* nums, int numsSize, int target){
int i = 0;
for(; i < numsSize; i++) {
if (nums[i] == target || target < nums[i]){
if(target < nums[0]) return 0;
return i;
}
}
return i;
}
```
==CKD==
```c=
int searchInsert(int* nums, int numsSize, int target){
int i = 0;
for(; i < numsSize; i++) {
if (nums[i] == target || target < nums[i])
return target < nums[0] ? 0:i;
}
return i;
}
```
---
## 21. Merge Two Sorted Lists
> You are given the heads of two sorted linked lists list1 and list2.
>
> Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
>
> Return the head of the merged linked list.
Example 1:
```
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
```
Example 2:
```
Input: list1 = [], list2 = []
Output: []
```
Example 3:
```
Input: list1 = [], list2 = [0]
Output: [0]
```
Constraints:
> The number of nodes in both lists is in the range [0, 50].
> 100 <= Node.val <= 100
> Both list1 and list2 are sorted in non-decreasing order.
**!!Answer!!**
>Runtime: 11 ms, Memory Usage: 6.2 MB,
```c=
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(!list1 && !list2) return NULL;
if(!list1) return list2;
else if (!list2) return list1;
struct ListNode temp;
struct ListNode *head = &temp;
while(list1 && list2){
if(list1->val < list2->val){
head->next = list1;
list1 = list1->next;
head = head->next;
}
else{
head->next = list2;
head = head->next;
list2 = list2->next;
}
}
if (list1)
head->next = list1;
if (list2)
head->next = list2;
return temp.next;
}
```
>Runtime: 3 ms, Memory Usage: 6 MB.
```c=
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(!list1 && !list2) return NULL;
if(!list1) return list2;
else if (!list2) return list1;
struct ListNode temp;
struct ListNode *head = &temp;
while(list1 && list2){
if(list1->val < list2->val){
head->next = list1;
list1 = list1->next;
head = head->next;
}
else{
head->next = list2;
head = head->next;
list2 = list2->next;
}
}
if (list1) head->next = list1;
if (list2) head->next = list2;
return temp.next;
}
```
---
2022/05/30
## 680. Valid Palindrome II
> Given a string s, return true if the s can be palindrome after deleting at most one character from it.
>
Example 1:
```
Input: s = "aba"
Output: true
```
Example 2:
```
Input: s = "abca"
Output: true
```
Explanation: You could delete the character 'c'.
Example 3:
```
Input: s = "abc"
Output: false
```
Constraints:
> 1 <= s.length <= 105
> s consists of lowercase English letters.
**!!Answer!!**
>Runtime: 21 ms, Memory Usage: 9.3 MB
```c=
bool checkVP(char* s, int left, int right, int count){
if(count>1) return false;
while(left <= right){//directly correct
if(s[left] != s[right])
return checkVP(s, left+1, right, count+1) || checkVP(s, left, right-1, count+1);
left++; right--;
}
return true;
}
bool validPalindrome(char * s){
return checkVP(s, 0, strlen(s)-1, 0);
}
```
>Runtime: 27 ms, Memory Usage: 9.2 MB
```c=
bool checkVP(char * s, int left, int right);
bool validPalindrome(char * s){
int left = 0;
int right = strlen(s) - 1;
while(left <= right){//directly correct
if(s[left] != s[right])
return checkVP(s, left+1, right) || checkVP(s, left, right-1);
left++;
right--;
}
return true;
}
bool checkVP(char* s, int left, int right){
while (s[left] == s[right])
{
if (left == right || left == right + 1) return true;
left++;
right--;
}
return false;
}
```
>Runtime: 33 ms, Memory Usage: 9.1 MB ==(CKD)==
```c=
bool isPanlindrome(char *s, int i, int j) {
for (;i<j;i++,j--) {
if (s[i] != s[j]) {
return false; // avoiding iteration return;
}
}
return true;
}
bool validPalindrome(char * s){
int len = strlen(s) -1 ;
for (int i= 0 ; i < len; i++, len--) {
if (s[i] != s[len]) {
return isPanlindrome(s, i+1, len) || isPanlindrome(s, i, len-1);
}
}
return true;
}
```
---
## 27. Remove Element
> Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
>
> Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
>
> Return k after placing the final result in the first k slots of nums.
>
> Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
**Custom Judge:**
The judge will test your solution with the following code:
```c
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
```
If all assertions pass, then your solution will be accepted.
Example 1:
```c
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
Example 2:
```c
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
**Constraints:**
> 0 <= nums.length <= 100
> 0 <= nums[i] <= 50
> 0 <= val <= 100
**Next challenges:
(Remove Linked List Elements), (Move Zeroes)**
**!!Answer!!**
> Runtime: 0 ms, faster than 100.00% of C online submissions for Remove Element. Memory Usage: 6.2 MB, less than 8.28% of C online submissions for Remove Element.
```c=
int removeElement(int* nums, int numsSize, int val){
int i=0, count=0;
if(numsSize == 0) return 0;
while(i < numsSize){
if(nums[i]!=val && i==numsSize-1){
nums[count] = nums[i];
count++;
}
else if(nums[i]!=val){
nums[count] = nums[i];
count++;
}
i++;
}
return count;
}
```
---
## 28. Implement strStr()
> Implement strStr().
>
> Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
>
> Clarification:
>
> What should we return when needle is an empty string? This is a great question to ask during an interview.
>
> For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
Example 1:
```
Input: haystack = "hello", needle = "ll"
Output: 2
```
Example 2:
```
Input: haystack = "aaaaa", needle = "bba"
Output: -1
```
Constraints:
> 1 <= haystack.length, needle.length <= 104
> haystack and needle consist of only lowercase English characters.
**!!Answer!!**
>Runtime: 0 ms, faster than 100.00% of C online submissions for Implement strStr().
**Memory Usage: 5.6 MB**, less than 95.59% of C online submissions for Implement strStr().
```c=
int strStr(char * haystack, char * needle){
int len1 = strlen(haystack);
int len2 = strlen(needle);
int i=0, j=0;
for(int i=0; i<len1; i++){
if(haystack[i]==needle[j]){
while(j<=len2){
if (haystack[i+j] == needle[j]) j++;
else break;
if(j == len2) return i;
}
}
j=0;
}
return -1;
}
```
---
## 119. Pascal's Triangle II
> Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
>
> In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
```
Input: rowIndex = 3
Output: [1,3,3,1]
```
Example 2:
```
Input: rowIndex = 0
Output: [1]
```
Example 3:
```
Input: rowIndex = 1
Output: [1,1]
```
Constraints:
> 0 <= rowIndex <= 33
>
**!!Answer!!**
>Runtime: 0 ms, faster than 100.00% of C online submissions for Pascal's Triangle II. **Memory Usage: 5.8 MB**, less than 46.02% of C online submissions for Pascal's Triangle II.
```c=
int* getRow(int rowIndex, int* returnSize){
int i=0, j=0;
int **returnArr = (int **)malloc(sizeof(int*) * (rowIndex+1)); //2D-array
for(i=0; i<rowIndex+1; i++){
returnArr[i] = (int *)malloc(sizeof(int *) * (i+1));
for(j=0; j<i+1; j++){
if(j==0 || i==j)
returnArr[i][j]=1;
else
returnArr[i][j] = returnArr[i-1][j-1] + returnArr[i-1][j];
}
}
*returnSize = rowIndex+1;
return returnArr[rowIndex];
}
```
>Runtime: 4 ms, faster than 37.72% of C online submissions for Pascal's Triangle II. **Memory Usage: 5.7 MB**, less than 65.74% of C online submissions for Pascal's Triangle II. ==-George==
```c=
int* getRow(int rowIndex, int* returnSize){
int *p = calloc(1, sizeof(int)*2);
p[0] = 1;
*returnSize = rowIndex+1;
for(int i = 1; i<=rowIndex; i++)
{
int* temp = calloc(1, sizeof(int)*(i+2));
temp[0] = 1;
for(int j = 1; j<i+1; j++)
{
temp[j] = p[j] + p[j-1];
}
temp[i] = 1;
int* temp1 = p;
p = temp;
free(temp1);
}
return p;
}
```
---
2022/06/01
## 121. Best Time to Buy and Sell Stock
> You are given an array prices where prices[i] is the price of a given stock on the ith day.
>
> You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
>
> Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
```
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
```
Example 2:
```
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
```
Constraints:
> 1 <= prices.length <= 105
> 0 <= prices[i] <= 104
**!!Answer!!**
```c=
int maxProfit(int* prices, int pricesSize){
int profit=0, maxprofit=0;
for(int i=0 ; i<pricesSize-1; i++) {
profit += prices[i+1] - prices[i];
if (profit < 0){
profit = 0; // reset
}
else if (profit > maxprofit){ //find max. profit
maxprofit = profit;
}
}
return maxprofit;
}
```
> **效率極差**
```c=
int maxProfit(int* prices, int pricesSize){
int max, min, tmp=0, maxprofit=0;
for(int i=0; i<pricesSize; i++){
min = prices[i];
for(int j=i; j<pricesSize; j++){
max = prices[j];
tmp = max-min;
if(tmp>maxprofit) maxprofit = tmp;
}
}
return maxprofit;
}
```
---
## 136. Single Number
> Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
>
> You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
```
Input: nums = [2,2,1]
Output: 1
```
Example 2:
```
Input: nums = [4,1,2,1,2]
Output: 4
```
Example 3:
```
Input: nums = [1]
Output: 1
```
Constraints:
> 1 <= nums.length <= 3 * 104
> -3 * 104 <= nums[i] <= 3 * 104
> Each element in the array appears twice except for one element which appears only once.
**!!Answer!!**
> Memory Usage: 7.1 MB, less than 93.47%
```c=
#define MAXLENGTH 30000
int singleNumber(int* nums, int numsSize){
if(numsSize == 1) return nums[0];
int ht[MAXLENGTH*2] = {0}; // HashTable
for(int i=0; i<numsSize; i++){
ht[nums[i]+MAXLENGTH] += 1;
}
for(int i = 0; i < numsSize; i++) {
if (ht[nums[i]+MAXLENGTH] == 1)
return nums[i]; //return if table value == 1
}
return 0;
}
```
> **Other Solution**
```c=
int singleNumber(int* nums, int numsSize){
int ans = nums[0];
for(int i=1; i<numsSize; i++){
ans ^= nums[i]; // XOR
}
return ans;
}
```
**Use XOR, e.g. [4,1,2,1,2] :**
> **4^1 = 0000 0001 ^ 0000 0100 = 0000 0101**
> **5^2 = 0000 0101 ^ 0000 0010 = 0000 0111**
> **7^1 = 0000 0111 ^ 0000 0001 = 0000 0110**
> **6^2 = 0000 0110 ^ 0000 0010 = 0000 0100**
---
## 169. Majority Element
> Given an array nums of size n, return the majority element.
>
> The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
```
Input: nums = [3,2,3]
Output: 3
```
Example 2:
```
Input: nums = [2,2,1,1,1,2,2]
Output: 2
```
Constraints:
> n == nums.length
> 1 <= n <= 5 * 104
> -109 <= nums[i] <= 109
**!!Answer!!**
> Memory Usage: 7.6 MB, less than 99.52% of C online submissions.
```c=
#define MAXLENGTH 100000
int majorityElement(int* nums, int numsSize){
if(numsSize == 1) return nums[0];
int tmp=0, ht[MAXLENGTH] = {0};
for(int i=0; i<numsSize; i++){
ht[nums[i]+50000] += 1;
}
for(int i=1;i<numsSize; i++){
if(ht[nums[tmp]+50000]<=ht[nums[i]+50000] ){
tmp = i;
}
}
return nums[tmp];
}
```
---
## 217. Contains Duplicate
> Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
```
Input: nums = [1,2,3,1]
Output: true
```
Example 2:
```
Input: nums = [1,2,3,4]
Output: false
```
Example 3:
```
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
```
Constraints:
> 1 <= nums.length <= 105
> -109 <= nums[i] <= 109
**!!Answer!!**
>Memory Usage: 11 MB, less than 95.93% of C online submissions
```c=
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
bool containsDuplicate(int* nums, int numsSize){
if(numsSize==1) return false;
heapSort(nums, numsSize);
for(int i=1; i<numsSize; i++){
if(nums[i]==nums[i-1])
return true;
}
return false;
}
```
**Working of Heap Sort**
:::spoiler
* Since the tree satisfies Max-Heap property, then the largest item is stored at the root node.
* Swap: Remove the root element and put at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place.
* Remove: Reduce the size of the heap by 1.
* Heapify: Heapify the root element again so that we have the highest element at root.
* The process is repeated until all the items of the list are sorted.
**Heap Sort**
**https://www.programiz.com/dsa/heap-sort**
:::
---
## 219. Contains Duplicate II
> Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Example 1:
```
Input: nums = [1,2,3,1], k = 3
Output: true
```
Example 2:
```
Input: nums = [1,0,1,1], k = 1
Output: true
```
Example 3:
```
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
```
Constraints:
>1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105
**!!Answer!!**
---
## 268. Missing Number
> Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Constraints:
> n == nums.length
> 1 <= n <= 104
> 0 <= nums[i] <= n
> All the numbers of nums are unique.
```C==
int missingNumber(int* nums, int numsSize){
int* ht = calloc(numsSize + 1, sizeof(int));
// int ht[MAXLENGTH] = {0};
for(int i=0; i<numsSize; i++)
ht[nums[i]] = 1;
for(int i=0; i<numsSize; i++)
if(ht[i] == 0) return i;
return numsSize;
}
```
---
## 876. Middle of the Linked List
```C==
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head){
if(head==NULL || head->next==NULL)
return head;
struct ListNode *fast=head, *slow=head;
while(fast!-NULL && fast->next!=NULL){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
```
---
## 190. Reverse Bits
> Reverse bits of a given 32 bits unsigned integer.
**Example 1:**
```
Input : n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
```
- Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
**Example 2:**
```
Input : n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
```
- Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
**Constraints:**
```
The input must be a binary string of length 32
```
**!!Answer!!**
>Memory Usage: 5.4 MB, less than 32.63% of C online submissions for Reverse Bits.
```c
uint32_t reverseBits(uint32_t n){
uint32_t revB = 0; // 宣告一個新變數
for(int i=0; i<32; i++, n>>=1){
revB <<= 1; // Right Shift 1 bit
revB += n&1; // if n&1==TRUE, then revB = revB + 1(Least Significant Bit)
/*
* revB |= n&1; // if n&1==TRUE, then revB = revB+1
*/
}
return revB;
}
```
---
## 455. Assign Cookies
> Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
>
> Each child i has a greed factor `g[i]`, which is the minimum size of a cookie that the child will be content with; and each cookie `j` has a size `s[j]`. If `s[j] >= g[i]`, we can assign the cookie `j` to the child `i`, and the child `i` will be content. Your goal is to maximize the number of your content children and output the maximum number.
**Example 1:**
```
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
```
**Example 2:**
```
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
```
**Constraints:**
```
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
```
==**!!Answer!!**==
- **Do sorting first**
```c
void quicksort(int *arr, const int left, const int right){
if (left >= right)
return; //如果左邊大於右邊，就跳出function
int i = left; //左邊的代理人
int j = right; //右邊的代理人
int key = arr[left]; //基準點
while(i != j){
while(arr[j] > key && i < j) //從右邊開始找，找比基準點小的值
j -= 1;
while(arr[i] <= key && i < j) //從左邊開始找，找比基準點大的值
i += 1;
if(i < j){ //當左右代理人沒有相遇時，互換值
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//將基準點歸換至代理人相遇點
arr[left] = arr[i];
arr[i] = key;
quicksort(arr, left, i-1); //繼續處理較小部分的子循環
quicksort(arr, i+1, right); //繼續處理較大部分的子循環
}
int findContentChildren(int* g, int gSize, int* s, int sSize){
quicksort(g, 0, gSize-1);
quicksort(s, 0, sSize-1);
int child = 0;
int cookie = 0;
while(child < gSize && cookie < sSize){
//如果greedy factor 和 cookie number匹配
if(g[child] <= s[cookie]){
child++;
}
cookie++;
}
return child;
}
```
---
## 628. Maximum Product of Three Numbers
> Given an integer array nums, find three numbers whose product is maximum and return the maximum product.
==**!!Answer!!**==
```c
void quicksort(int *arr, const int left, const int right){
if (left >= right)
return; //如果左邊大於右邊，就跳出function
int i = left; //左邊的代理人
int j = right; //右邊的代理人
int key = arr[left]; //基準點
while(i != j){
while(arr[j] > key && i < j) //從右邊開始找，找比基準點小的值
j -= 1;
while(arr[i] <= key && i < j) //從左邊開始找，找比基準點大的值
i += 1;
if(i < j){ //當左右代理人沒有相遇時，互換值
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//將基準點歸換至代理人相遇點
arr[left] = arr[i];
arr[i] = key;
quicksort(arr, left, i-1); //繼續處理較小部分的子循環
quicksort(arr, i+1, right); //繼續處理較大部分的子循環
}
int maximumProduct(int* nums, int numsSize){
if(numsSize == 3) return nums[0]*nums[1]*nums[2];
int temp = -1000;
quicksort(nums, 0, numsSize-1);
if(nums[0]<0 && nums[1]<0 && nums[numsSize-1]>0)
temp = nums[0]*nums[1]*nums[numsSize-1];
if(temp<nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3])
temp = nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3];
return temp;
}
```c
#include <stdio.h>
#include <malloc.h>
int Max = 0;
int find_max(int len, int arr[])
{
int i, sum = 0;
for(i=0; i<len; i++)
{
sum += arr[i];
if(sum > Max)
{
Max = sum;
}else if(sum < 0){
sum = 0;
}
}
return Max;
}
int main(){
int i, len, *arr;
printf("請輸入數組的長度：");
scanf("%d",&len);
arr = (int *)malloc(sizeof(int)*len);
printf("請輸入數組的值：");
for (i=0; i<len; i++)
{
scanf("%d", &arr[i]);
}
find_max(len, arr);
printf("最大連續子序列和：%d \n",Max);
return 0;
}
```
**Use define to simplify the code**
```c
#define IS_NEGATIVE nums[0] * nums[1] * nums[numsSize - 1]
#define NO_NEGATIVE nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3]
void quicksort(int *arr, const int left, const int right){
if (left >= right)
return; //如果左邊大於右邊，就跳出function
int i = left; //左邊的代理人
int j = right; //右邊的代理人
int key = arr[left]; //基準點
while(i != j){
while(arr[j] > key && i < j) //從右邊開始找，找比基準點小的值
j -= 1;
while(arr[i] <= key && i < j) //從左邊開始找，找比基準點大的值
i += 1;
if(i < j){ //當左右代理人沒有相遇時，互換值
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//將基準點歸換至代理人相遇點
arr[left] = arr[i];
arr[i] = key;
quicksort(arr, left, i-1); //繼續處理較小部分的子循環
quicksort(arr, i+1, right); //繼續處理較大部分的子循環
}
int maximumProduct(int* nums, int numsSize){
quicksort(nums, 0, numsSize-1);
return IS_NEGATIVE > NO_NEGATIVE ? IS_NEGATIVE : NO_NEGATIVE;
}
```
---
## 2089. Find Target Indices After Sorting Array
>You are given a 0-indexed integer array nums and a target element target.
>
>A target index is an index i such that nums[i] == target.
>
>Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.
==**!!Answer!!**==
>Memory Usage: 5.9 MB, less than 78.35% of C online submissions for Find Target Indices After Sorting Array.
```c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void quicksort(int *arr, const int left, const int right){
if (left >= right)
return; //如果左邊大於右邊，就跳出function
int i = left; //左邊的代理人
int j = right; //右邊的代理人
int key = arr[left]; //基準點
while(i != j){
while(arr[j] > key && i < j) //從右邊開始找，找比基準點小的值
j -= 1;
while(arr[i] <= key && i < j) //從左邊開始找，找比基準點大的值
i += 1;
if(i < j){ //當左右代理人沒有相遇時，互換值
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//將基準點歸換至代理人相遇點
arr[left] = arr[i];
arr[i] = key;
quicksort(arr, left, i-1); //繼續處理較小部分的子循環
quicksort(arr, i+1, right); //繼續處理較大部分的子循環
}
int* targetIndices(int* nums, int numsSize, int target, int* returnSize){
// 如果 nums 只有一個值
if(numsSize==1 && nums[0]==target){
*returnSize = 1;
int *ans = (int *) malloc(sizeof(int));
ans[0] = 0;
return ans;
}
// 正常情況
int count = 0;
//先 malloc 一個陣列存放 index 的值
int *tmp = (int *) malloc(sizeof(int) * numsSize);
//quicksort 遞增排列
quicksort(nums, 0, numsSize-1);
for(int i=0; i<numsSize; i++){
// 如果 nums[i]==target，紀錄 index，並把 count+1
if(nums[i]==target){
tmp[count] = i;
count++;
}
}
// malloc 一個最終大小的陣列
int *ans = (int *) malloc(sizeof(int) * count);
//將暫時存放的值移至新的 array
for(int i=0; i<count; i++)
ans[i]=tmp[i];
//釋放原本的 array
free(tmp);
*returnSize = count;
return ans;
}
```
---
## 561. Array Partition
>Given an integer array `nums` of `2n` integers, group these integers into n pairs `(a1, b1), (a2, b2), ..., (an, bn)` such that the sum of `min(ai, bi)` for all `i` is maximized. Return the maximized sum.
==**!!Answer!!**==
>Memory Usage: 7.4 MB, less than 94.07% of C online submissions for Array Partition.
```c
void quicksort(int *arr, const int left, const int right){
if (left >= right)
return; //如果左邊大於右邊，就跳出function
int i = left; //左邊的代理人
int j = right; //右邊的代理人
int key = arr[left]; //基準點
while(i != j){
while(arr[j] > key && i < j) //從右邊開始找，找比基準點小的值
j -= 1;
while(arr[i] <= key && i < j) //從左邊開始找，找比基準點大的值
i += 1;
if(i < j){ //當左右代理人沒有相遇時，互換值
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//將基準點歸換至代理人相遇點
arr[left] = arr[i];
arr[i] = key;
quicksort(arr, left, i-1); //繼續處理較小部分的子循環
quicksort(arr, i+1, right); //繼續處理較大部分的子循環
}
int arrayPairSum(int* nums, int numsSize){
quicksort(nums, 0, numsSize-1);
int i=0, sum=0;
while(i<numsSize){
sum += nums[i];
i+=2;
}
return sum;
}
```
---
## 746. Min Cost Climbing Stairs
>You are given an integer array cost where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps
>
>You can either start from the step with index `0`, or the step with index `1`.
>
>Return the minimum cost to reach the top of the floor.
==**!!Answer!!**==
```c
int minCostClimbingStairs(int* cost, int costSize){
int count[costSize+1];
count[0] = 0;
count[1] = 0;
for(int i=2; i<=costSize; i++)
count[i] = cost[i-2]+count[i-2] < cost[i-1]+count[i-1] ? cost[i-2]+count[i-2] : cost[i-1]+count[i-1];
return count[costSize];
}
```
- Dynamic Programming
- https://web.ntnu.edu.tw/~algo/DynamicProgramming.html
- https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98%E7%B3%BB%E5%88%97-dynamic-programming-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83-de980ca4a2d3
---
## 206. Reverse Linked List
>Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
==**!!Answer!!**==
```c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *prev = NULL, *after = NULL;
if (head == NULL) return NULL;
while(head != NULL){
after = head->next;
head->next = prev;
prev = head;
head = after;
}
return prev;
}
```
---
## 941. Valid Mountain Array
> Given an array of integers arr, return true if and only if it is a valid mountain array.
> Recall that arr is a mountain array if and only if:
:::info
- arr.length >= 3
- There exists some i with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
:::
* Example 1:
>Input: arr = [2,1]
Output: false
* Example 2:
>Input: arr = [3,5,5]
Output: false
* Example 3:
>Input: arr = [0,3,2,1]
Output: true
==**!!Answer!!**==
```c
bool validMountainArray(int* arr, int arrSize){
if (arrSize < 2) return false;
int i = 0, status = 0;
char *result = "";
while(i < arrSize){
if (arr[i] == arr[i+1])
return false;
if(arr[i] < arr[i+1])
status = 1;
else if(arr[i] > arr[i+1]){
if(status == 0)
return false;
status = 2;
}
++i;
}
if(status == 1) return false;
return true;
}
```
---
# MEDIUM
## 852. Peak Index in a Mountain Array
>An array arr a mountain if the following properties hold:
arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].
You must solve it in O(log(arr.length)) time complexity.
==**!!Answer!!**==
```c
int peakIndexInMountainArray(int* arr, int arrSize){
if(arrSize < 3) return -1;
int index = 0;
for(int i=1; i<arrSize; i++){
if(arr[i] > arr[index])
index = i;
else
return index;
}
return -1;
}
```
```c
int peakIndexInMountainArray(int* arr, int arrSize){
for(int i = 0; i < arrSize - 1; i++){
if(arr[i+1] < arr[i])
return i;
}
return -1;
}
```
Sign in with Wallet
Connect another wallet