Misc Problems

mjain

May 1st, 2025 (edited)

290

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Java 38.20 KB | Source Code | 0 0

raw download clone embed print report

import java.util.*;
class Solution {
//You are given two integer arrays nums1 and nums2,
// sorted in non-decreasing order, and two integers m and n,
// representing the number of elements in nums1 and nums2 respectively.
public void merge(int[] nums1, int m, int[] nums2, int n) {
int l1 = m - 1;
int l2 = n - 1;
int i = l1 + l2 + 1;
while (l1 >= 0 && l2 >= 0) {
if (nums1[l1] > nums2[l2]) {
nums1[i--] = nums1[l1--];
} else {
nums1[i--] = nums2[l2--];
}
}
while (l2 >= 0) {
nums1[i--] = nums2[l2--];
}
}
//Given an integer array nums and an integer val, remove all occurrences of val in nums in-place.
// The order of the elements may be changed.
// Then return the number of elements in nums which are not equal to val.
public int removeElement(int[] nums, int val) {
int n = nums.length;
int index = n - 1;
int count = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == val) {
while (index >= 0) {
if (nums[index] == val) {
nums[index] = Integer.MAX_VALUE;
index--;
} else if (nums[i] != Integer.MAX_VALUE) {
nums[i] = nums[index];
nums[index] = Integer.MAX_VALUE;
index--;
break;
} else {
index--;
}
}
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != Integer.MAX_VALUE) {
count++;
}
}
return count;
}
//Given an integer array nums sorted in non-decreasing order,
// remove the duplicates in-place such that each unique element appears only once.
// The relative order of the elements should be kept the same.
// Then return the number of unique elements in nums.
public int removeDuplicates(int[] nums) {
int inderpos = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
nums[inderpos++] = nums[i];
}
}
for (int j = inderpos; j < nums.length; j++) {
nums[j] = 0;
}
return inderpos;
}
//Given an integer array nums sorted in non-decreasing order,
// remove some duplicates in-place such that each unique element appears at most twice.
// The relative order of the elements should be kept the same.
//
//Since it is impossible to change the length of the array in some languages,
// you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
public int removeDuplicatesV2(int[] nums) {
int inderpos = 1;
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
nums[inderpos++] = nums[i];
count = 1;
} else if (nums[i] == nums[i - 1] && count < 2) {
count++;
nums[inderpos++] = nums[i];
}
}
for (int j = inderpos; j < nums.length; j++) {
nums[j] = 0;
}
return inderpos;
}
//Given an array nums of size n, return the majority element.
//
//The majority element is the element that appears more than ⌊n / 2⌋ times.
// You may assume that the majority element always exists in the array.
public int majorityElement(int[] nums) {
int votes = 0;
int candidate = -1;
for (int i = 0; i < nums.length; i++) {
if (votes == 0) {
candidate = nums[i];
}
if (nums[i] == candidate) {
votes++;
} else {
votes--;
}
}
return candidate;
}
//Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
int count = 0;
for (int start = 0; count < n; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % n;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start != current);
}
}
//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.
public 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;
}
//You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
//
//On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
//
//Find and return the maximum profit you can achieve.
public int maxProfitV2(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i - 1] < prices[i]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
//You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
//
//Return true if you can reach the last index, or false otherwise.
public boolean canJump(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
if (i > max) {
return false;
}
max = Math.max(max, i + nums[i]);
}
return true;
}
//ou are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
//
//Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j]
public int jump(int[] nums) {
int jumps = 0;
int fartherest = 0;
int currentIndex = 0;
for (int i = 0; i < nums.length - 1; i++) {
fartherest = Math.max(fartherest, i + nums[i]);
if (i == currentIndex) {
jumps++;
currentIndex = fartherest;
}
}
return jumps;
}
//Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.
//
//According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
//
//
public int hIndex(int[] citations) {
Arrays.sort(citations);
int n = citations.length;
for (int i = 0; i < n; i++) {
int h = n - i;
if (citations[i] >= h) {
return h;
}
}
return 0;
}
//Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
//
//The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
//
//You must write an algorithm that runs in O(n) time and without using the division operation.
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] answer = new int[length];
answer[0] = 1;
for (int i = 1; i < length; i++) {
answer[i] = nums[i - 1] * answer[i - 1];
}
int rightProduct = 1;
for (int i = length - 1; i >= 0; i--) {
answer[i] = answer[i] * rightProduct;
rightProduct = rightProduct * nums[i];
}
return answer;
}
//There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
//
//You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
//
//Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalTank = 0;
int currentTank = 0;
int startStation = 0;
for (int i = 0; i < gas.length; i++) {
totalTank += gas[i] - cost[i];
currentTank += gas[i] - cost[i];
if (currentTank < 0) {
currentTank = 0;
startStation = i + 1;
}
}
return totalTank >= 0 ? startStation : -1;
}
//There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
//
//You are giving candies to these children subjected to the following requirements:
//
//Each child must have at least one candy.
//Children with a higher rating get more candies than their neighbors.
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
for (int i = 0; i < n; i++) {
candies[i] = 1;
}
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
int totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
//Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
public int trap(int[] height) {
int n = height.length;
int trappedWater = 0;
int leftMax = height[0];
int rightMax = height[n - 1];
int left = 1;
int right = n - 2;
while (left <= right) {
if (leftMax >= rightMax) {
trappedWater += Math.max(0, rightMax - height[right]);
rightMax = Math.max(rightMax, height[right]);
right--;
} else {
trappedWater += Math.max(0, leftMax - height[left]);
leftMax = Math.max(leftMax, height[left]);
left++;
}
}
return trappedWater;
}
//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
public int romanToInt(String s) {
java.util.Map<Character, Integer> romanMap = new java.util.HashMap<>();
romanMap.put('I', 1);
romanMap.put('V', 5);
romanMap.put('X', 10);
romanMap.put('L', 50);
romanMap.put('C', 100);
romanMap.put('D', 500);
romanMap.put('M', 1000);
int result = 0;
int prevValue = 0;
for (int i = s.length() - 1; i >= 0; i--) {
int currentValue = romanMap.get(s.charAt(i));
if (currentValue < prevValue) {
result -= currentValue;
} else {
result += currentValue;
}
prevValue = currentValue;
}
return result;
}
//Given an integer, convert it to a Roman numeral.
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
for (int i = 0; i < values.length; i++) {
while (num >= values[i]) {
num -= values[i];
sb.append(symbols[i]);
}
}
return sb.toString();
}
//Given a string s consisting of words and spaces, return the length of the last word in the string.
//
//A word is a maximal substring consisting of non-space characters only.
public int lengthOfLastWord(String s) {
int length = 0;
int i = s.length() - 1;
while (i >= 0 && s.charAt(i) == ' ') {
i--;
}
while (i >= 0 && s.charAt(i) != ' ') {
length++;
i--;
}
return length;
}
//Write a function to find the longest common prefix string amongst an array of strings.
//
//If there is no common prefix, return an empty string "".
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
if (strs.length == 1) {
return strs[0];
}
String pref = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(pref) != 0) {
pref = pref.substring(0, pref.length() - 1);
if (pref.isEmpty()) {
return "";
}
}
}
return pref;
}
//Given an input string s, reverse the order of the words.
//
//A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
//
//Return a string of the words in reverse order concatenated by a single space.
public String reverseWords(String s) {
StringBuilder result = new StringBuilder();
int i = s.length() - 1;
while (i >= 0) {
while (i >= 0 && s.charAt(i) == ' ') {
i--;
}
if (i < 0) break;
int end = i;
// Find the start of the word
while (i >= 0 && s.charAt(i) != ' ') {
i--;
}
int start = i + 1;
result.append(s.substring(start, end + 1));
result.append(" ");
}
return result.toString().trim();
}
//The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
public String convert(String s, int numRows) {
int length = s.length();
if (length <= numRows || numRows == 1) {
return s;
}
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) {
rows[i] = new StringBuilder();
}
int currentRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows[currentRow].append(c);
if (currentRow == 0 || currentRow == numRows - 1) {
goingDown = !goingDown;
}
if (goingDown) {
currentRow++;
} else {
currentRow--;
}
}
StringBuilder result = new StringBuilder();
for (StringBuilder row : rows) {
result.append(row);
}
return result.toString();
}
//Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}
if (needle.length() == 0) {
return -1;
}
int l1 = haystack.length();
int l2 = needle.length();
for (int i = 0; i <= l1 - l2; i++) {
if (haystack.substring(i, i + l2).equalsIgnoreCase(needle)) {
return i;
}
}
return -1;
}
//A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
public boolean isPalindrome(String s) {
if (s == null || s.length() == 1) {
return true;
}
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
sb.append(Character.toLowerCase(c));
}
}
String s1 = sb.toString();
int left = 0, right = s1.length() - 1;
System.out.println(s1);
while (left < right) {
if (s1.charAt(left) != s1.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
//Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
//
//A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == s.length();
}
//Given a 1-indexed 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. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 1) {
return null;
}
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
}
if (sum > target) {
right--;
}
if (sum < target) {
left++;
}
}
return null;
}
//You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
//
//Find two lines that together with the x-axis form a container, such that the container contains the most water.
//
//Return the maximum amount of water a container can store.
public int maxArea(int[] height) {
int water = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
int currentWater = Math.min(height[right], height[left]) * (right - left);
water = Math.max(currentWater, water);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return water;
}
//Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
//
//Notice that the solution set must not contain duplicate triplets.
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
int length = nums.length;
for (int i = 0; i < length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return list;
}
//Given an array of positive integers nums and a positive integer target,
// return the minimal length of a subarray whose sum is greater than or equal to target.
// If there is no such subarray, return 0 instead.
public int minSubArrayLen(int target, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
if (nums[0] >= target) {
return 1;
}
}
int ans = Integer.MAX_VALUE;
int sum = 0;
int start = 0;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
while (sum >= target) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}
}
if (ans == Integer.MAX_VALUE) return 0;
return ans;
}
//Given a string s, find the length of the longest substring without duplicate characters.
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
if (s.length() == 1) {
return 1;
}
int left = 0;
int right = 0;
HashMap<Integer, Boolean> vMap = new HashMap();
int maxWindow = 1;
while (right < s.length()) {
while (vMap.get(s.charAt(right) - 'a') != null && vMap.get(s.charAt(right) - 'a') == true) {
int i = s.charAt(left) - 'a';
vMap.put(i, false);
left++;
}
vMap.put(s.charAt(right) - 'a', true);
maxWindow = Math.max(right - left + 1, maxWindow);
right++;
}
return maxWindow;
}
//You are given a string s and an array of strings words. All the strings of words are of the same length.
//
//A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
//
//For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.
//Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words == null || words.length == 0 || s == null || s.length() == 0) {
return result;
}
Map<String, Integer> frequencyMap = new HashMap<>();
int wordCount = words.length;
int wordLength = words[0].length();
for (String word : words) {
frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);
}
for (int start = 0; start < s.length(); start++) {
HashMap<String, Integer> currentWindowWords = new HashMap<>();
int currWordCount = 0;
int left = start;
for (int right = start; right + wordLength <= s.length(); right += wordLength) {
String currentWord = s.substring(right, right + wordLength);
currentWindowWords.put(currentWord, currentWindowWords.getOrDefault(currentWord, 0) + 1);
currWordCount++;
while (currWordCount > wordCount) {
String wordToRemove = s.substring(left, left + wordLength);
if (currentWindowWords.containsKey(wordToRemove)) {
if (currentWindowWords.get(wordToRemove) > 1) {
currentWindowWords.put(wordToRemove, currentWindowWords.get(wordToRemove) - 1);
} else {
currentWindowWords.remove(wordToRemove);
}
}
currWordCount--;
left += wordLength;
}
if (!frequencyMap.containsKey(currentWord)) {
currentWindowWords.clear();
currWordCount = 0;
left = right + wordLength;
continue;
}
if (currWordCount == wordCount && currentWindowWords.equals(frequencyMap)) {
result.add(left);
}
}
}
return result;
}
//Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
//
//The testcases will be generated such that the answer is unique.
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
Map<Character, Integer> tMap = new HashMap<>();
for (char c : t.toCharArray())
tMap.put(c, tMap.getOrDefault(c, 0) + 1);
Map<Character, Integer> windowMap = new HashMap<>();
int have = 0, need = tMap.size();
int left = 0, minLen = Integer.MAX_VALUE;
int start = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
if (tMap.containsKey(c) && windowMap.get(c).intValue() == tMap.get(c).intValue()) {
have++;
}
while (have == need) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
char leftChar = s.charAt(left);
windowMap.put(leftChar, windowMap.get(leftChar) - 1);
if (tMap.containsKey(leftChar) && windowMap.get(leftChar).intValue() < tMap.get(leftChar).intValue()) {
have--;
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
public boolean isValidSudoku(char[][] board) {
HashSet<Character>[] rows = new HashSet[9];
HashSet<Character>[] cols = new HashSet[9];
HashSet<Character>[] subMat = new HashSet[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashSet<>();
cols[i] = new HashSet<>();
subMat[i] = new HashSet<>();
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char val = board[i][j];
if (val == '.') continue;
if (rows[i].contains(val)) return false;
rows[i].add(val);
if (cols[j].contains(val)) return false;
cols[j].add(val);
int idx = (i / 3) * 3 + (j / 3);
if (subMat[idx].contains(val)) return false;
subMat[idx].add(val);
}
}
return true;
}
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new LinkedList<>();
int rows = matrix.length;
int cols = matrix[0].length;
int top = 0;
int bottom = rows - 1;
int leftIndex = 0;
int rightIndex = cols - 1;
while (top <= bottom && leftIndex <= rightIndex) {
for (int i = leftIndex; i <= rightIndex; i++) {
list.add(matrix[top][i]);
}
top++;
for (int i = top; i <= bottom; i++) {
list.add(matrix[i][rightIndex]);
}
rightIndex--;
if (top <= bottom) {
for (int i = rightIndex; i >= leftIndex; i--) {
list.add(matrix[bottom][i]);
}
bottom--;
}
if (leftIndex <= rightIndex) {
for (int row = bottom; row >= top; row--) {
list.add(matrix[row][leftIndex]);
}
leftIndex++;
}
}
return list;
}
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean firstRow = false;
boolean firstCol = false;
for (int i = 0; i < cols; i++) {
if (matrix[0][i] == 0) {
firstRow = true;
break;
}
}
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == 0) {
firstCol = true;
break;
}
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
if (firstRow) {
for (int i = 0; i < cols; i++) {
matrix[0][i] = 0;
}
}
if (firstCol) {
for (int i = 0; i < rows; i++) {
matrix[i][0] = 0;
}
}
}
public void gameOfLife(int[][] board) {
int rows = board.length;
int cols = board[0].length;
int directions[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0},
{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
int liveNeighbours = 0;
for (int[] direction : directions) {
int r = row + direction[0];
int c = col + direction[1];
if (board[r][c] == 1 || board[r][c] == 3) {
liveNeighbours++;
}
}
if (board[row][col] == 1 && (liveNeighbours < 2 || liveNeighbours > 3)) {
board[row][col] = 3;
}
if (board[row][col] == 0 && liveNeighbours == 3) {
board[row][col] = 2;
}
}
}
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (board[row][col] == 3) {
board[row][col] = 0;
} else if (board[row][col] == 2) {
board[row][col] = 1;
}
}
}
}
public boolean canConstruct(String ransomNote, String magazine) {
if (magazine == null || magazine.length() == 0 || ransomNote == null || ransomNote.length() == 0) {
return false;
}
Map<Character, Integer> charCount = new HashMap<>();
Map<Character, Integer> ransomCount = new HashMap<>();
for (char c : magazine.toCharArray()) {
if (charCount.containsKey(c)) {
int count = charCount.get(c);
charCount.put(c, count + 1);
} else {
charCount.put(c, 1);
}
}
for (char c : ransomNote.toCharArray()) {
if (ransomCount.containsKey(c)) {
int count = ransomCount.get(c);
ransomCount.put(c, count + 1);
} else {
ransomCount.put(c, 1);
}
}
for (char c : ransomCount.keySet()) {
if (!charCount.containsKey(c) || charCount.get(c) < ransomCount.get(c)) {
return false;
}
}
System.out.println(charCount.toString());
System.out.println(ransomCount.toString());
return true;
}
public boolean isIsomorphic(String s, String t) {
if (s == null && t == null) {
return true;
}
if (s.length() == 0 && t.length() == 0) {
return true;
}
Map<Character, Character> csMap = new HashMap<>();
Map<Character, Character> mapTS = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char cs = s.charAt(i);
char ct = t.charAt(i);
if (csMap.containsKey(cs)) {
if (csMap.get(cs) != ct) {
return false;
}
} else {
if (mapTS.containsKey(ct)) return false;
csMap.put(cs, ct);
mapTS.put(ct, cs);
}
}
return true;
}
public boolean wordPattern(String pattern, String s) {
if (s == null && pattern == null) {
return true;
}
Map<String, Character> wordMap = new HashMap<>();
Map<Character, String> charMap = new HashMap<>();
String[] words = s.split(" ");
if (pattern.length() != words.length) {
return false;
}
for (int i = 0; i < words.length; i++) {
String word = words[i];
char c = pattern.charAt(i);
if (wordMap.containsKey(word)) {
if (wordMap.get(word) != c) {
return false;
}
} else {
if (charMap.containsKey(c)) {
return false;
}
charMap.put(c, word);
wordMap.put(word, c);
}
}
return true;
}
public boolean isAnagram(String s, String t) {
if (s == null && t == null) {
return true;
}
if (s.length() == 0 && t.length() == 0) {
return true;
}
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c1 = s.charAt(i);
char c2 = t.charAt(i);
if (map.containsKey(c1)) {
map.put(c1, map.get(c1) + 1);
} else {
map.put(c1, 1);
}
if (map.containsKey(c2)) {
map.put(c2, map.get(c2) - 1);
} else {
map.put(c2, -1);
}
}
for (int val : map.values()) {
if (val != 0) {
return false;
}
}
return true;
}
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> list = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
map.computeIfAbsent(new String(chars), k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(map.values());
}
public int[] twoSumByMap(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return null;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int currentNumber = nums[i];
if (map.containsKey(currentNumber)) {
Integer startIndex = map.get(currentNumber);
return new int[]{startIndex, i};
}
map.put(target - currentNumber, i);
}
return null;
}
public static void main(String[] args) {
Solution s = new Solution();
int nums[] = {3,3};
int ans[] = s.twoSumByMap(nums, 6);
printArray(ans);
}
private static void printArray(int[] result) {
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
}

Add Comment

Please, Sign In to add comment