LeetCode #3

I’ve started doing LeetCode. Of course, it’s free plan but, if I get interest I will buy the premium version. Today is the first time so I am doing Explore. I am writing blog simultaniously like in “The Social Network”.

What I’ve Learned

First, hashmap. Hashmap is a array of keys and values. We can search values via key. The order is not important. To use, Map<Integer, Integer> numMap = new HashMap<>();. To add numMap.put(Key, Value);. To get numMap.get(key). For check, numMap.containsKey(Key).
Second, reversing. You can reverse integer simply by dividing in 10 and multiplying back again. It’s a simple algorithm.
Third, .charAt(i) method in string.

Disclaimer

My LeetCode is free plan. I am posting just the free algorithms for now on. Also, I am using JAVA to code.

1. Two Sum

My Solution

I just thought I can check all the numbers and add it to find the matching number of target. It takes a lot of time but, it’s safe and believable.

class Solution {
    public int[] twoSum(int[] nums, int target) {
    	int[] answer = new int[2];
    	
        for(int i = 0; i<nums.length; i++) {
        	for(int j = i+1; j < nums.length; j++) {
        		if(nums[i] + nums[j] == target) {
        			int[] resultarr = {i,j};
        			answer = resultarr;
        		}
        	}
        }
        return answer;
    }
}

Solution

HashMap is a java utility that can make you access easily. Order is not important to consider. We can just find by key and get the value inside. To use, Map<Integer, Integer> numMap = new HashMap<>();. To add numMap.put(Key, Value);. To get numMap.get(key). For check, numMap.containsKey(Key). So the idea is to remove value from the target and search that value.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;

        // Build the hash table
        for (int i = 0; i < n; i++) {
            numMap.put(nums[i], i);
        }

        // Find the complement
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement) && numMap.get(complement) != i) {
                return new int[]{i, numMap.get(complement)};
            }
        }

        return new int[]{}; // No solution found
    }
}

9. Palindrome Number

My Solution

I’ve used LinkedList to check if it’s same or not. I could’ve used arrays but, problem was I need to iterate the size of array. I’ve checked if it’s below zero. And if it’s not I checked the first and last of arraylist.

class Solution {
    public boolean isPalindrome(int x) {
        LinkedList<String> list = new LinkedList<>();
        boolean result = true;
        if(x < 0) {
        	result = false;
        }else {
        	while(x != 0) {
            	int remain = x % 10;
            	list.addLast(Integer.toString(remain));
            	x /= 10;
            }
            	for(int i =0; i<list.size()/ 2; i++) {
                	System.out.println(list.get(i) + " : " +  list.get(list.size() - 1 - i));
                	if(!list.get(i).equals(list.get(list.size() - 1 - i))) {
                		result = false;
                		break;
                	} 
                }
        }
        return result;
    }
}

Solution

I think I’ve thought too much. It was actually simple. Just reverse the whole integer and check if it’s same. Making the reverse of integer is simple. Get each digit of number and make it reverse.

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        long reversed = 0;
        long temp = x;

        while (temp != 0) {
            int digit = (int) (temp % 10);
            reversed = reversed * 10 + digit;
            temp /= 10;
        }

        return (reversed == x);
    }
}

13. Roman to Integer

My Solution

I’ve used Hashmap to save the relation of roman numbers. Also, splited the String into array for checking if it’s same with each hash key.

import java.util.HashMap;

class Solution {
    public int romanToInt(String s) {
    	HashMap<String, Integer> h1 = new HashMap<String, Integer>();
    	h1.put("I",1);
    	h1.put("V",5);
    	h1.put("X",10);
    	h1.put("L",50);
    	h1.put("C",100);
    	h1.put("D",500);
    	h1.put("M",1000);
    	int result = 0;
    	
        String[] str_arr = s.split("");
        for(int i =0; i<str_arr.length-1; i++) {
        	if(h1.get(str_arr[i]) > h1.get(str_arr[i+1]) || h1.get(str_arr[i]) == h1.get(str_arr[i+1]))
        		result += h1.get(str_arr[i]);
        	else
        		result -= h1.get(str_arr[i]); 
        }
        result = result + h1.get(str_arr[str_arr.length - 1]); 
        return result;
    }
}

Solution

HashMap approach was right. But one problem was to split string into array. Best adventage of array is that I can access with index. I didn’t came up of .charAt(i). It could make it faster.

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> m = new HashMap<>();
        
        m.put('I', 1);
        m.put('V', 5);
        m.put('X', 10);
        m.put('L', 50);
        m.put('C', 100);
        m.put('D', 500);
        m.put('M', 1000);
        
        int ans = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (i < s.length() - 1 && m.get(s.charAt(i)) < m.get(s.charAt(i + 1))) {
                ans -= m.get(s.charAt(i));
            } else {
                ans += m.get(s.charAt(i));
            }
        }
        
        return ans;
    }
}