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.
- myArray = {84,85,86,87,85,90,85,83,23,45,84,1,2,0}
- 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.
- myArray = {1,2,3,4,6}
- 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)
- removeDuplicates({1, 1, 2, 2, 3, 4, 5})
- 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:
- Input: nums = [1, 1, 2]
- Output: 2
public class Main {
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 3, 4, 5};
System.out.println(removeDuplicates(arr));
}
public static int removeDuplicates(int[] nums) {
int result = nums.length;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) result--;
}
return result;
}
}
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:
- 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.
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
- Input: nums = [2,7,11,15], target = 9
- Output: [0,1]
- Output: Because nums[0] + nums[1] == 9, we return [0, 1]
- Input: nums = [3,2,4], target = 6
- Output: [1,2]
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
- int[] intArray = {10,20,30,40,50};
- maxProduct(intArray) // (40,50)
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
- int[] array1 = {1,2,3,4,5};
- int[] array2 = {5,1,2,3,4};
- permutation(array1, array2)
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));
}
}
Комментарии
Отправить комментарий