DSA: Arrays

1. Best Score: Given an array, write a function to get first, second best scores from the array and return it in new array.

  1. myArray = {84,85,86,87,85,90,85,83,23,45,84,1,2,0}
  2. firstSecond(myArray) // {90, 87}

 


package test;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 91, 15, 3, 90, 8, 79, 91, 13};
        System.out.println(Arrays.toString(findTopTwoScores(arr)));
    }

    public static int[] findTopTwoScores(int[] array) {
        int[] result = new int[2];
        int first = array[0];
        int second = first;
        for (int i = 1; i < array.length; i++) {
            if (array[i] > first) {
                second = first;
                first = array[i];
            } else if (array[i] > second && array[i] < first) {
                second = array[i];
            }
        }
        result[0] = first;
        result[1] = second;
        return result;
    }

}




2. Missing Number: Write Java function called findMissingNumberInArray that takes an integer array containing n-1 unique elements from a range of 1 to n, with one missing number, and returns the missing number.

  1. myArray = {1,2,3,4,6}
  2. findMissingNumberInArray(myArray, 6) // 5


package test;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6};
        System.out.println(findMissingNumberInArray(arr));
    }

    public static int findMissingNumberInArray(int[] arr) {
        int sum = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
        }
        n++;
        n = (n * (n + 1)) / 2;
        return n - sum;
    }

}



3. Duplicate Number: Write a function which takes integer array as a parameter and returns a new integer array with unique elements. (remove duplicates)

  1. removeDuplicates({1, 1, 2, 2, 3, 4, 5})
  2. Output : [1, 2, 3, 4, 5]





package test;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 1, 1, 2, 2, 3, 4, 1, 5};
        System.out.println(Arrays.toString(removeDuplicates(arr)));
    }

    public static int[] removeDuplicates(int[] array) {
        int n = array.length;
        int[] uniqueArray = new int[n];
        int index = 0;

        for (int i = 0; i < n; i++) {
            boolean isDuplicate = false;
            for (int j = i + 1; j < n; j++) {
                if (array[i] == array[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                uniqueArray[index++] = array[i];
            }
        }

        return Arrays.copyOf(uniqueArray, index);
    }

}



4. Remove Duplicates from Sorted Array - LeetCode 26

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.

Example:

5. Best Time to Buy and Sell Stock - LeetCode 121

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:

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.



Solution1:


package test;

public class Main {
    public static void main(String[] args) {
        int[] arr = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(arr));
    }

    public static int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] - prices[i] > result) {
                    result = prices[j] - prices[i];
                }
            }
        }
        return result;
    }

}


Solution2:

package test;

public class Main {
    public static void main(String[] args) {
        int[] arr = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(arr));
    }

    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for(int price : prices) {
            if(price < minPrice) minPrice = price;
            else if(price - minPrice > maxProfit) maxProfit = price - minPrice;
        }
        return maxProfit;
    }

}



-- Burada ilk once biz min value tapmaliyiq, bunun ucun ise int minPrice = Integer.MAX_VALUE; teyin edirik. Ikinci etap butun deyerleri iterate edirik. Burada key point if shertidir: eger price minPrice den kicikdirse o zaman minPrice set edirik price. Else if hissesi ise  en cox price oldugu halda result-a set edecek.

6. Two Sum - LeetCode 1

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Examples




package main;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 11, 7, 15};
        System.out.println(Arrays.toString(twoSum(arr, 9)));
    }

    public static int[] twoSum(int[] nums, int target) {
        int[] result = {-1, -1};
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                break;
            }
            map.put(nums[i], i);
        }
        return result;
    }

}



7. Max Product of Two Integers

How to find maximum product of two integers in the array where all elements are positive.

Example


package test;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 4, 3, 2, 1};
        System.out.println(maxProduct(arr));
    }

    public static String maxProduct(int[] intArray) {
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        for (int i : intArray) {
            if (i > first) {
                second = first;
                first = i;
            } else if (i > second) {
                second = i;
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(first).append(",").append(second);
        return sb.toString();
    }

}




8. Permutation

Your are given two integer arrays. Write a program to check if they are permutation of each other.

Example

Output

true


package test;

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {5, 4, 3, 2, 1};
        System.out.println(permutation(arr1, arr2));
    }

    public static boolean permutation(int[] array1, int[] array2) {
        int sum1 = 0, sum2 = 0, multiplication1 = 1, multiplication2 = 1;
        for (int i = 0; i < array1.length; i++) {
            sum1 += array1[i];
            sum2 += array2[i];
            multiplication1 *= array1[i];
            multiplication2 *= array2[i];
        }
        return sum1 == sum2 && multiplication1 == multiplication2;
    }

}




9. Rotate Matrix

Given an image represented by an NxN matrix write a method to rotate the image by 90 degrees.

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly.

DO NOT allocate another 2D matrix and do the rotation.


package test;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotateMatrix(arr);
    }

    public static void rotateMatrix(int[][] matrix) {
        int n = matrix.length;
        int[][] newMatrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newMatrix[i][j] = matrix[n - j - 1][i];
            }
        }
        System.out.println(Arrays.deepToString(newMatrix));
    }

}








Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Lesson1: JDK, JVM, JRE

Изображение
1. Compiler - takes the entire programming code written in high language and translates the whole of it into machine code at once. After this process the an executable file will be ready to run. The translation takes some times to be done, but after that execution is so fast. 2. Interpreter - takes each single instructions of the code translates it and then executes it on its own. The translation step is before the program runs is fast, but execution is slow. JDK = JRE + development tools JRE = JVM + library class JDK -> Java Development Kit. A kit which provides the environment to develop and execute (run) Java program. JRE -> Java Runtime Environment. Provides environment to only run. JVM -> Java Virtual Machine f * Compiled: Fortran, C, C++, Pascal, Haskell, Rust, Go * Interpreted: JavaScript, PHP, Python, Ruby Java both compiled and interpreted language. Terminalda : javac Main.java yazdiqda, source fayli(.java) bytecode(.class) faylina cevirir. Terminalda: java Main (bu z...
Далее...

SE_21_Lesson_9: Initialization Blocks, Wrapper types, String class

Изображение
-> static block: package org.example.test3 ; public class Blocks { static { System . out .println( "In static block" ) ; } public static void method () { System . out .println( "In static method" ) ; } } package org.example.test3 ; public class Main { public static void main ( String [] args ) { Blocks . method () ; } } -> Class.forName() metodunu ishe salmaq: package org.example.test3 ; public class Blocks { static { System . out .println( "In static block" ) ; } } package org.example.test3 ; public class Main { public static void main ( String [] args ) throws Exception { Class . forName ( "org.example.test3.Blocks" ) ; } } -> non-static (instance) block: package org.example.test3 ; public class Blocks { static { System . out .println( "in static block" ) ; } { System . out .println( "in non static (instance) block...
Далее...

SE_21_Lesson_11: Inheritance, Polymorphism

->  instanceof anlayishi, misallarla izahi   package org.example.lesson_13 ; public class Ulubaba { public String ad ; public String soyad ; public Integer yash ; public void odunDogramaq () { System . out .println( "Ulubaba 50 kq odunu 1 saata dograyir" ) ; } } package org.example.lesson_13 ; public class Baba extends Ulubaba { public String hobbi ; public void otBicmek () { System . out .println( "Baba 1 hektar otu 1 gune bicir" ) ; } } package org.example.lesson_13 ; public class Main { public static void main ( String [] args ) { Baba baba = new Baba() ; System . out .println( baba instanceof Ulubaba ) ; System . out .println( baba instanceof Object ) ; } } -> Upcasting package org.example.lesson_13 ; public class Main { public static void main ( String [] args ) { Ulubaba u = new Baba() ; } } -> Downcasting Problemsiz situasiya: package org.example.lesson_13...
Далее...