LeetCode - 13. Roman to Integer

Source Link:
https://leetcode.com/problems/roman-to-integer/description/

Question:
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

My Solution:
Note:
1. new an integer array to store all the numbers
int[] nums = new int[ s.length() ];
2. convert each "char" to "number"
for(int i=0; i<s.length(); i++){
if(s.charAt(i) == 'M'){
nums[i] = 1000;
}
...
} 
3. to compute the sum
// note: from bigger one to smaller one -> sum = sum + nums
// note: if nums[j] == nums[j+1] -> sum = sum + nums (be careful)
// note: from smaller one to bigger one -> sum = sum - nums (important)
for(int j=0; j< s.length()-1 ; j++){
if(nums[j] >= nums[j+1]){
sum = sum + nums[j];
}
else{
sum = sum - nums[j];
}
}   
4. note: the final one -> sum = sum + nums
sum = sum + nums[ s.length()-1 ];
5. return
return sum;

LeetCode - 26. Remove Duplicates from Sorted Array

Source Link:
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/ 

Question:
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2], 

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length. 

My Solution: Note:
1. we need to return "the new length" and need to "modify the given array"
2. it doesn't matter what you leave beyond the new length (simple)
3. the array has been sorted (so only need one pass)
4. the value that we need to compare with
int index = nums[0];
5. a different value appears
if(nums[i] != index){
index = nums[i];       // change the value that we need to compare with
nums[count]=index; // modify the given array
count++;                   // the new length++
}
6. skip the case: nums[i] == index
7. return the new length
return count;

LeetCode - 21. Merge Two Sorted Lists

Source Link:
https://leetcode.com/problems/merge-two-sorted-lists/description/ 

Question:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

My Solution: Note:
1. we create a "dummy node" to be the "previous node" of the head of the new list to avoid some potential bugs (and to keep the 1st node)
2. process the nodes of both lists (until one node becomes "null")
while(a != null && b != null)
3. case 1: a is smaller than b
if(a.val <= b.val){
current.next = a;
a = a.next;
current = current.next;
}
4. case 2: b is smaller than a
else{
current.next = b;
b = b.next;
current = current.next;
}
5. the remaining nodes
if(a == null){
current.next = b;
}
if(b == null){
current.next = a;
}
6. dummy.next is the "1st" node
return dummy.next;

LeetCode - 14. Longest Common Prefix

Source Link:
https://leetcode.com/problems/longest-common-prefix/description/ 

Question: 
Write a function to find the longest common prefix string amongst an array of strings. 

Hint:
https://leetcode.com/problems/longest-common-prefix/solution/

My Solution: Note:
1. we will shorten the common prefix if not perfectly match
2. Using Horizontal Scanning: from the 1st string to the last string
for(int i=1; i< strs.length; i++)
3. match: using string.indexOf(string)==0
while( prefix_match == false){
if(strs[i].indexOf(prefix) ==0) {
prefix_match = true;
}
else{
prefix = prefix.substring(0, prefix.length()-1); 
//shorten prefix: using string.substring(0, length-1)
}
}