Roman to Integer - LeetCode 13

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

 

Example 1:

Input: s = "III"
Output: 3

Example 2:

Input: s = "IV"
Output: 4

Example 3:

Input: s = "IX"
Output: 9

Example 4:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: s = "MCMXCIV"
Output: 1994 

Explanation: M = 1000, CM = 900, XC = 90 and IV = 4

Solution:

Note: Only function is written.

class Solution {

    public int romanToInt(String s) {

        

        Map<Character,Integer> map=new HashMap<>();

        

        map.put('I',1);

        map.put('V',5);

        map.put('X',10);

        map.put('L',50);

        map.put('C',100);

        map.put('D',500);

        map.put('M',1000);

        

        int result=map.get(s.charAt(s.length()-1));

        

        for(int i=s.length()-2;i>=0;--i)

        {

            if(map.get(s.charAt(i))<map.get(s.charAt(i+1))){

                result-=map.get(s.charAt(i));

            }else{

                result+=map.get(s.charAt(i));

            }

        }

        

        return result;

    }

}

 

Two Sum II - Input array is sorted - LeetCode -118

 Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

 

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]

 Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Solution:

Note: Only function is written

class Solution {

    public int[] twoSum(int[] numbers, int target) {

        int a_pointer=0,b_pointer=numbers.length-1;

        

        while(a_pointer <= b_pointer){

            

            int sum = numbers[a_pointer] + numbers[b_pointer];

            

            if(sum>target){

                b_pointer-=1;

            }else if(sum<target){

                a_pointer+=1;

            }else{

                return new int[] {a_pointer+1,b_pointer+1};

            }  

        }

        

         return new int[] {a_pointer+1,b_pointer+1};

    }

}

Number of Islands - LeetCode 200

 Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'

 

Solution:

Note: Only function is written

class Solution {

    public int numIslands(char[][] grid) {

        

        int count=0;

        

        for(int i=0;i<grid.length;i++){

            for(int j=0;j<grid[i].length;j++){

                if(grid[i][j]=='1'){

                    count+=1;

                    fun(grid,i,j);

                }

            }

        }

        return count;

        

    }

    

    public void fun(char[][] grid,int i,int j){

        if(i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0')

            return;

        

        grid[i][j]='0';

        fun(grid,i-1,j);

        fun(grid,i+1,j);

        fun(grid,i,j-1);

        fun(grid,i,j+1);    

       }

}

Output:

Your input

[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]

Output

1

Expected

1

Pascal's Triangle - LeetCode 118

 Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Solution: 

Note: Only function is written

class Solution {

    public List<List<Integer>> generate(int numRows) {

        

        List<List<Integer>> triangle = new ArrayList<>(); //created empty List of lists

        

        if(numRows==0)

            return triangle;

        

        

        List<Integer> first_row = new ArrayList<>(); //created first row 

        first_row.add(1); // and assigned 1 to first row

        

        triangle.add(first_row); //adding first row to our List of lists

        

        

        //Looping through each row

        for(int i=1;i<numRows;i++){

            List<Integer> prev_row=triangle.get(i-1); //retreiving previous row from triangle

            List<Integer> row = new ArrayList<>(); // creating an empty row to fill each element in this row

            

            row.add(1); // adding 1 at first as 1 is the first element for every row

            

            for(int j=1;j<i;j++){

                row.add(prev_row.get(j-1)+prev_row.get(j)); // summing up elements in previous row and filling in the row   

                

            }

            

            row.add(1); // adding 1 to row as last element for every row is 1

            triangle.add(row); // Now adding the row to List of lists

            

        }

        

        return triangle;

        

    }

}

Output:

Your input

5

Output

[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Diff

Expected

[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Contains Duplicate - LeetCode 217

 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

Solution:

import java.io.*;

import java.util.*;

public class Main

{

    static Scanner sc=new Scanner(System.in);

public static void main(String[] args) {

    

    int n;

    n=sc.nextInt();

    int[] arr=new int[n];

    for(int i=0;i<n;i++){

        arr[i]=sc.nextInt();

    }

    Solution s=new Solution();

    boolean res=s.containsDuplicate(arr);

    System.out.println(res);

}

}

public class Solution {

  

   public boolean containsDuplicate(int[] nums) {

        

        HashSet<Integer> hashset = new HashSet<>();

        

        for(int i=0;i<nums.length;i++){

            if(hashset.contains(nums[i]))

                return true;

            

            hashset.add(nums[i]);

        }

        

        return false;

    }

}

Your input

[1,2,3,1]

Output

true

Expected

true