xzhan211@binghamton.edu
BAN USERimport java.util.*;
public class DistanceSort{
static boolean ans = false;
public static void main(String[] args){
List<List<Integer>> res = new ArrayList<>();
int in = Integer.valueOf(args[0]);
int[] arr = new int[in * 2];
int pos = 0;
for(int i=1; i<=in; i++){
arr[pos++] = i;
arr[pos++] = i;
}
System.out.println(Arrays.toString(arr));
dfs(arr, new boolean[in * 2], new ArrayList<>(), res);
System.out.println(ans);
for(List<Integer> li : res){
System.out.println(li.toString());
}
}
public static void dfs(int[] arr, boolean[] visited, List<Integer> temp, List<List<Integer>>res){
if(temp.size() == arr.length){
if(check(temp)){
res.add(new ArrayList<>(temp));
ans = true;
return;
}
}
int k = -1;
for(int i=0; i<arr.length; i++){
if(visited[i]) continue;
if(arr[i] == k) continue;
k = arr[i];
visited[i] = true;
temp.add(arr[i]);
dfs(arr, visited, temp, res);
visited[i] = false;
temp.remove(temp.size()-1);
}
}
public static boolean check(List<Integer> temp){
for(int i=0; i<temp.size(); i++){
int right = i + temp.get(i) + 1;
int left = i - temp.get(i) - 1;
if(right < temp.size() && left >= 0){
if(temp.get(right) != temp.get(i) && temp.get(left) != temp.get(i)){
return false;
}
}else if((right >= temp.size()) && (left < 0)){
return false;
}else if((right < temp.size()) && (temp.get(right) != temp.get(i))){
return false;
}else if((left >= 0) && (temp.get(left) != temp.get(i))){
return false;
}
}
return true;
}
}
{
key1 : value1,
key2 : {key2_1: value2_1},
key3 : [{key3_1: value3_1}, {key3_2: value3_2}]
}
recursion
/*
* T: O(n^2)
* S: O(n)
* */
public class PeriodicPattern{
static boolean ans = false;
public static void main(String[] args){
String str = "aabbaaabba";
for(int i=0; i<str.length()/2+1; i++){
String s = str.substring(0, i+1);
dfs(str, s.length(), s);
}
System.out.println(ans);
}
public static void dfs(String str, int start, String p){
if(start == str.length()){
ans = true;
System.out.println(p);
return;
}
if(str.indexOf(p, start) == start)
dfs(str, start+p.length(), p);
}
}
import java.util.*;
public class BreakWord{
static boolean ans = false;
public static void main(String[] args){
Map<String, Integer> map = new HashMap<>();
//map.put("abc", 3);
//map.put("ab", 2);
//map.put("abca", 1);
map.put("abc", 3);
map.put("ab", 2);
String str = "abcabcabcabca";
//String str = "abcabab";
Set<String> set = new HashSet<>();
for(String s : map.keySet()){
set.add(s);
}
dfs(map, set, str, 0);
System.out.println(ans);
}
public static void dfs(Map<String, Integer> map, Set<String> set, String str, int start){
if(start == str.length()){
ans = true;
return;
}
for(int i=start; i<str.length(); i++){
String ss = str.substring(start, i+1);
if(!set.contains(ss))
continue;
if(map.get(ss) == 0){
continue;
}
map.put(ss, map.get(ss)-1);
dfs(map, set, str, i+1);
map.put(ss, map.get(ss)+1);
}
}
}
- xzhan211@binghamton.edu July 22, 2019