Poozmak
BAN USERpublic static Calendar getDateIn(int days, Calendar now) {
Map<Integer, Integer> daysMap = monthToDaysMap();
int dayInYear = days + now.day;
for(int m=1; m<now.month; m++) {
dayInYear += daysMap.get(m);
}
int day = 0;
int month = 1;
int year = now.year;
while(dayInYear > 365) {
year ++;
dayInYear -= 365;
}
while(dayInYear > daysMap.get(month)) {
dayInYear -= daysMap.get(month);
month ++;
}
day += dayInYear;
return new Calendar(year, month, day);
}
private static Map<Integer, Integer> monthToDaysMap() {
Map<Integer, Integer> daysMap = new HashMap<Integer, Integer>();
daysMap.put(1, 31);
daysMap.put(2, 28);
daysMap.put(3, 31);
daysMap.put(4, 30);
daysMap.put(5, 31);
daysMap.put(6, 30);
daysMap.put(7, 31);
daysMap.put(8, 31);
daysMap.put(9, 30);
daysMap.put(10, 31);
daysMap.put(11, 31);
daysMap.put(12, 31);
return daysMap;
}
For the O(1) solution - first find the max and then iterate through the array in a cycle from a random "start" index until length+"start" where the index i is the mod value
Return the first value equals to max
public static int randomIndexOfMax(Integer[] arr) {
Random rand = new Random();
int max = arr[0];
//Find max
for(int i=1; i<arr.length; i++) {
if(max < arr[i]) {
max = arr[i];
}
}
int index = -1;
int start = rand.nextInt(arr.length);
//Iterate from start to length+start in mod indexes
for(int i=start; i<arr.length+start; i++) {
int loc = i%(arr.length);
if(max == arr[loc]) {
index = loc;
}
}
return index;
}
/**
* Find all k length subsets and calculate the sum of each of them
* When the sum equals target - add the subset to the solution list
* Use a hashMap to avoid duplications
*/
public class Solution {
public static void main(String[] args) {
List<List<Integer>> solution = combinationSum(new int[]{5,3,1,6,2,-1,0}, 5, 3);
System.out.println(solution);
}
private static List<List<Integer>> combinationSum(int[] nums, int target, int k) {
List<List<Integer>> solution = new ArrayList<List<Integer>>();
Map<Integer,List<Integer>> solutionMap = new HashMap<Integer, List<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i<nums.length; i++) {
list.add(nums[i]);
}
combinationSum(solutionMap, new ArrayList<Integer>(), list ,k ,target);
solution.addAll(solutionMap.values());
return solution;
}
private static void combinationSum(Map<Integer,List<Integer>> solutionMap, ArrayList<Integer> subList1, ArrayList<Integer> subList2, int k, int target) {
if(subList1.size() == k && subList1.stream().mapToInt(Integer::intValue).sum() == target) {
Integer hash = subList1.hashCode();
if(!solutionMap.containsKey(hash)) {
subList1.sort(Integer::compareTo);
solutionMap.put(subList1.hashCode(), subList1);
}
}
for(int i=0; i<subList2.size(); i++) {
ArrayList<Integer> newSubList1 = new ArrayList<Integer>();
newSubList1.addAll(subList1);
newSubList1.add(subList2.get(i));
ArrayList<Integer> newSubList2 = new ArrayList<Integer>();
newSubList2.addAll(subList2);
newSubList2.remove(i);
combinationSum(solutionMap, newSubList1, newSubList2, k, target);
}
}
Result:
[[0, 2, 3], [-1, 1, 5], [-1, 0, 6]]
public static void main(String[] args) {
System.out.println(getPermutation("a1b"));
}
private static List<String> getPermutation(String s) {
List<String> result = new ArrayList<String>();
getPermutation("", s, result);
return result;
}
private static void getPermutation(String prefix, String suffix, List<String> result) {
if(suffix.length() == 0) {
result.add(prefix);
return;
}
char currChar = suffix.charAt(0);
String newSuffix = suffix.substring(1);
if(Character.isAlphabetic(currChar)) {
getPermutation(prefix + Character.toUpperCase(currChar), newSuffix, result);
getPermutation(prefix + Character.toLowerCase(currChar), newSuffix, result);
} else {
getPermutation(prefix + currChar, newSuffix, result);
}
}
Or, without using prefix and suffix:
private static List<String> getPermutation(String s) {
List<String> result = new ArrayList<String>();
getPermutation(s, 0, result);
return result;
}
private static void getPermutation(String s, int i, List<String> result) {
if(s.length() == i) {
result.add(s);
return;
}
char currChar = s.charAt(i);
if(Character.isAlphabetic(currChar)) {
String newSUp = s.substring(0,i) + Character.toUpperCase(currChar) + s.substring(i+1,s.length());
String newSLow = s.substring(0,i) + Character.toLowerCase(currChar) + s.substring(i+1,s.length());
getPermutation(newSUp, i+1, result);
getPermutation(newSLow, i+1, result);
} else {
getPermutation(s, i+1, result);
}
}
Or without recursion
private static List<String> getPermutatuion(String s) {
List<String> result = new ArrayList<String>();
int len = s.length();
for(int i=0; i<len; i++) {
char currChar = s.charAt(i);
if(Character.isAlphabetic(currChar)) {
result.add(s.substring(0,i) + Character.toLowerCase(currChar) + s.substring(i+1,len));
result.add(s.substring(0,i) + Character.toUpperCase(currChar) + s.substring(i+1,len));
}
}
return result;
}
In order for both sums to be as close as possible - each needs to be as close as possible to half of the total sum.
In my approach i first sort the initial set, then go through it from highest to lowest and sum the numbers. If the result of adding a number to the current sum is greater than the half of the total sum - i continue iterating (to the lower numbers) and try to add them
Examples:
{1,2,3,4,90}
s1: 90 (sum 90)
s2: 1,2,3,4 (sum 10)
{1,2,3,14,15,16}
s1: 16,3,2,1 (sum 22)
s2: 15,14 (sum 29)
- Poozmak February 23, 2020