sj
BAN USER// Use bucket sort
//Time complexity: O(N+K)
//Space: O(K)
class Sorting
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(sorting("a390testai")); // output: 039aaeistt
}
public static String sorting(String str) {
if (str == null || str.length() == 0)
return str;
ArrayList<Character>[] al = new ArrayList[80];
for (char c: str.toCharArray()) {
if (c - '0' >= 0) {
if (al[c - '0'] == null)
al[c - '0'] = new ArrayList<Character>();
al[c - '0'].add(c);
}
}
StringBuilder sb = new StringBuilder();
for (List<Character> list: al) {
if (list == null) continue;
for (char c: list) {
sb.append(c);
}
}
return sb.toString();
}
}
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("vil");set.add("sit");set.add("flick");set.add("pat");set.add("pluck");set.add("sat");set.add("vat");
System.out.println(ladderLength("vit", 3, set));
}
public static List<String> ladderLength(String beginWord, int count, Set<String> wordDict) {
LinkedList<String> queue = new LinkedList<>();
queue.offer(beginWord);
List<String> result = new ArrayList<>();
while(!queue.isEmpty()){
String word = queue.poll();
if(result.size() == count){
break;
}
if (!word.equals(beginWord)) {
result.add(word);
}
char[] arr = word.toCharArray();
for(int i=0; i<arr.length; i++){
for(char c='a'; c<='z'; c++){
char temp = arr[i];
if(arr[i]!=c){
arr[i]=c;
}
String newWord = new String(arr);
if(wordDict.contains(newWord)){
queue.add(newWord);
wordDict.remove(newWord);
}
arr[i]=temp;
}
}
}
return result;
}
TIME: O(n^2)
public static void main(String[] args) {
int[] nums = {2,4,5,7};
int k = 8;
List<List<Integer>> result = new ArrayList<>();
List<Integer> subset = new ArrayList<>();
calculateSubSetsTwo(nums, k, -1, result, subset);
System.out.println(result);
}
public static void calculateSubSetsTwo(int[] nums, int k, int index, List<List<Integer>> result, List<Integer> subset) {
if (index == nums.length || (index >= 0 && nums[index] > k)) {
return;
}
if (subset.size() == 1 && nums[index] * 2 <= k) {
result.add(new ArrayList<>(subset));
} else if (subset.size() > 1) {
result.add(new ArrayList<>(subset));
}
for (int i = index + 1; i < nums.length; i++) {
subset.add(nums[i]);
if (index == -1 || subset.get(0) + nums[i] <= k) {
calculateSubSetsTwo(nums, k, i, result, subset);
}
subset.remove(subset.size() - 1);
}
}
public class Random {
public static void main(String[] args) {
int[] nums = {2,4,5,7};
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
calculateSubSets(nums, 8, i, result);
}
System.out.println(result);
System.out.println(result.size());
}
public static void calculateSubSets(int[] nums, int k, int index, List<List<Integer>> result) {
if (index == nums.length || nums[index] > k) {
return;
}
List<Integer> subset = new ArrayList<>();
if (nums[index] * 2 <= k) {
subset.add(nums[index]);
result.add(subset);
}
subset = new ArrayList<>();
subset.add(nums[index]);
for (int i = index + 1; i < nums.length; i++) {
if (nums[index] + nums[i] <= k) {
subset.add(nums[i]);
result.add(new ArrayList<>(subset));
} else {
while (subset.size() > 2) {
subset.remove(1);
result.add(new ArrayList<>(subset));
}
}
}
}
}
class Team
{
public static void main (String[] args) throws java.lang.Exception
{
int nosCountries = 5;
int nosPlayers = 5;
int teamSize = 3;
int[][] mat = new int[nosPlayers][nosCountries];
List<Integer> list = new ArrayList<>();
int[] out = {0};
int teamCount = 0;
for (int r = 0; r < mat.length; r++) {
int currTeamPlayerCount = 0;
dfs(mat, r, 0, currTeamPlayerCount, out, teamSize);
teamCount += out[0];
out[0] = 0;
}
System.out.println(teamCount);
}
public static boolean isValid(int[][] mat, int p, int c) {
return p >= 0 && c >= 0 && p < mat.length && c < mat[0].length;
}
public static void dfs(int[][] arr, int p, int c, int currTeamPlayerCount, int[] output, int k) {
if (!isValid(arr, p, c)) {
return;
}
if (currTeamPlayerCount == k - 1) {
output[0]++;
return;
}
for (int j = c + 1; j < arr[0].length; j++) {
currTeamPlayerCount++;
dfs(arr, p, j, currTeamPlayerCount, output, k);
currTeamPlayerCount--;
}
}
}
RepI am Susan From Wasilla USA. and my strong interest in yoga and reading historical books. I have a large ...
- sj June 03, 2019