jgriesser
BAN USERdef is_aggregated(number):
num = str(number)
for i in range(1, len(num) - 1):
summand1 = int(num[:i])
for j in range(i + 1, len(num)):
summand2 = int(num[i:j])
sum = summand1 + summand2;
pos = j
while num.startswith(str(sum), pos):
pos += len(str(sum))
summand1, summand2 = summand2, sum
sum = summand1 + summand2
if pos == len(num):
return True
return False
static class Coordinate {
int x, y;
Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void distance(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
Queue<Coordinate> q = new LinkedList<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 'G') {
q.add(new Coordinate(i, j));
}
}
}
final int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
while (!q.isEmpty()) {
Coordinate curr = q.remove();
for (int[] dir : dirs) {
int x = curr.x + dir[0];
int y = curr.y + dir[1];
if (isValid(matrix, x, y) && matrix[x][y] == '0') {
matrix[x][y] = matrix[curr.x][curr.y] == 'G'
? '1'
: (char) (matrix[curr.x][curr.y] + 1);
q.add(new Coordinate(x, y));
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '0') {
matrix[i][j] = 'X';
}
}
}
}
private static boolean isValid(char[][] matrix, int x, int y) {
return x >= 0 && x < matrix.length
&& y >= 0 && y < matrix[0].length;
}
public static int maxSubArrayDifference(int[] arr) {
if (arr == null || arr.length < 2) return 0;
int[] minSumAtIdx = minSubArray(arr, false);
int[] minSumReverseAtIdx = minSubArray(arr, true);
int[] maxSumAtIdx = maxSubArray(arr, false);
int[] maxSumReverseAtIdx = maxSubArray(arr, true);
int diff = 0;
for (int i = 0; i < arr.length - 1; i++) {
int diff1 = Math.abs(maxSumAtIdx[i] - minSumReverseAtIdx[i + 1]);
diff = Math.max(diff, diff1);
int diff2 = Math.abs(maxSumReverseAtIdx[i + 1] - minSumAtIdx[i]);
diff = Math.max(diff, diff2);
}
return diff;
}
public static int[] minSubArray(int[] arr, boolean reverse) {
if (arr == null || arr.length == 0) return null;
int n = arr.length;
int[] minAtIdx = new int[n];
if (reverse) {
int minSoFar = arr[n - 1];
int min = arr[n - 1];
minAtIdx[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
minSoFar = Math.min(arr[i], arr[i] + minSoFar);
min = Math.min(min, minSoFar);
minAtIdx[i] = min;
}
} else {
int minSoFar = arr[0];
int min = arr[0];
minAtIdx[0] = arr[0];
for (int i = 1; i < n; i++) {
minSoFar = Math.min(arr[i], arr[i] + minSoFar);
min = Math.min(min, minSoFar);
minAtIdx[i] = min;
}
}
return minAtIdx;
}
public static int[] maxSubArray(int[] arr, boolean reverse) {
if (arr == null || arr.length == 0) return null;
int n = arr.length;
int[] maxAtIdx = new int[n];
if (reverse) {
int maxSoFar = arr[n - 1];
int max = arr[n - 1];
maxAtIdx[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxSoFar = Math.max(arr[i], arr[i] + maxSoFar);
max = Math.max(max, maxSoFar);
maxAtIdx[i] = maxSoFar;
}
} else {
int maxSoFar = arr[0];
int max = arr[0];
maxAtIdx[0] = arr[0];
for (int i = 1; i < n; i++) {
maxSoFar = Math.max(arr[i], arr[i] + maxSoFar);
max = Math.max(max, maxSoFar);
maxAtIdx[i] = maxSoFar;
}
}
return maxAtIdx;
}
Works as long as there are no cycles
static class Node {
int id, weight;
Node parent;
List<Node> children = new ArrayList<>();
Node(int id) {
this.id = id;
}
}
private static final Map<Integer, Node> nodeGraph = new HashMap<>();
public static void parseCsvFile(String fileName) throws IOException {
try (Stream<String> stream = Files.lines(Paths.get(fileName))) {
stream.forEach(s -> parseCsvRow(s));
}
}
private static void parseCsvRow(String row) {
String[] cells = row.split(",");
int id = Integer.parseInt(cells[0]);
int parent = !cells[1].isEmpty()
? Integer.parseInt(cells[1])
: -1;
int weight = Integer.parseInt(cells[2]);
createNode(id, parent, weight);
}
private static void createNode(int id, int parent, int weight) {
Node node = nodeGraph.computeIfAbsent(id, Node::new);
node.weight = weight;
Node parentNode = parent != -1
? nodeGraph.computeIfAbsent(parent, Node::new)
: null;
if (parentNode != null) {
parentNode.children.add(node);
node.parent = parentNode;
}
}
public static int subWeight(Node node) {
if (node == null) return 0;
int weight = node.weight;
for (Node child : node.children) {
weight += subWeight(child);
}
return weight;
}
public static String mul(String l, String r) {
if (l == null || l.equals("0") || r == null || r.equals("0")) {
return "0";
}
boolean isNegative = false;
if (l.startsWith("-")) {
isNegative = true;
l = l.substring(1);
}
if (r.startsWith("-")) {
isNegative ^= true;
r = r.substring(1);
}
int[] result = new int[l.length() + r.length()];
int resultEnd = result.length - 1;
int resultIdx = 0;
for (int rightIdx = r.length() - 1; rightIdx >= 0; rightIdx--) {
int carry = 0;
resultIdx = resultEnd;
for (int leftIdx = l.length() - 1; leftIdx >= 0; leftIdx--) {
int curr = (l.charAt(leftIdx) - '0') * (r.charAt(rightIdx) - '0')
+ carry + result[resultIdx];
result[resultIdx--] = curr % 10;
carry = curr / 10;
}
if (carry > 0) {
result[resultIdx] = carry;
}
resultEnd--;
}
StringBuilder sb = new StringBuilder();
if (isNegative) sb.append("-");
if (result[resultIdx] == 0) resultIdx++;
for (int i = resultIdx; i < result.length; i++) {
sb.append(result[i]);
}
return sb.toString();
}
public static int minRows(String[] strings, int K) {
int rows = 0;
while (rows < Integer.MAX_VALUE) {
rows++;
if (testMinRows(strings, rows, K)) return rows;
}
return -1;
}
private static boolean testMinRows(String[] strings, int rows, int K) {
for (int i = 0; i < rows; i++) {
int rowCharCount = 0;
int space = 0;
for (int j = i; j < strings.length; j += rows) {
rowCharCount += space;
rowCharCount += strings[j].length();
space = 1;
if (rowCharCount > K) return false;
}
}
return true;
}
Only works if Strings contain unique characters.
public static char findInsertedChar(String s1, String s2) {
int low = 0, high = s1.length() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
char c1 = s1.charAt(mid), c2 = s2.charAt(mid);
if (c1 == c2) {
low = mid + 1; // find char on right-hand side
} else if (mid == 0 || s1.charAt(mid - 1) != c2) {
return c2;
} else {
high = mid - 1; // find char on left-hand side
}
}
return s2.charAt(high + 1);
}
Multiple solutions exist (based on the dictionary used), e.g.:
[fever, queue, zoo, mat, speaker, person, backgammon, house, wax, jury, diligent]
public static void fillInWords(String[] words) {
Set<String> dict = generateDict();
Set<Character> usedLetters = new HashSet<>();
if (fillInWords(words, 0, "", dict, usedLetters)) {
System.out.println(Arrays.toString(words));
} else {
System.out.println("No solution exists.");
}
}
private static boolean fillInWords(String[] words, int wordIdx, String candidate,
Set<String> dict, Set<Character> usedLetters) {
// Final word completed
if (wordIdx == words.length) return true;
// Construct word
StringBuilder sb = new StringBuilder(candidate);
for (int i = sb.length(); i < words[wordIdx].length(); i++) {
char currChar = words[wordIdx].charAt(i);
// Fill in a blank and recurse or simply add current char to StringBuilder
if (currChar == '*') {
for (char c = 'a'; c <= 'z'; c++) {
if (!usedLetters.contains(c)) {
sb.append(c);
usedLetters.add(c);
if (fillInWords(words, wordIdx, sb.toString(), dict, usedLetters)) {
return true;
}
// Backtrack
sb.setLength(sb.length() - 1);
usedLetters.remove(c);
}
}
// No letter fits
return false;
} else {
sb.append(currChar);
}
}
candidate = sb.toString();
// Test completed word
if (candidate.length() == words[wordIdx].length() && dict.contains(candidate)) {
if (fillInWords(words, wordIdx + 1, "", dict, usedLetters)) {
words[wordIdx] = candidate;
return true;
}
}
return false;
}
public class Solution {
public static String[] shortestSubArray(String[] words, String[] keywords) {
// Sliding window of words and their indices
Map<String, Integer> wordAtIdx = new LinkedHashMap<>();
Set<String> keywordSet = new HashSet<>(Arrays.asList(keywords));
int solutionSize = Integer.MAX_VALUE; // can alo be words.length + 1
int solutionStartIdx = -1;
for (int i = 0; i < words.length; i++) {
if (keywordSet.contains(words[i])) {
// Remove (if necessary) and re-add word to end of sliding window
wordAtIdx.remove(words[i]);
wordAtIdx.put(words[i], i);
// Check for new solution if our window matches the keyword size
if (wordAtIdx.size() == keywordSet.size()) {
int windowStartIdx = wordAtIdx.values().iterator().next();
int candidateSize = i - windowStartIdx + 1;
if (candidateSize < solutionSize) {
solutionSize = candidateSize;
solutionStartIdx = windowStartIdx;
}
// Remove the leftmost element from the window
wordAtIdx.remove(words[windowStartIdx]);
}
}
}
return solutionStartIdx == -1 ? null
: Arrays.copyOfRange(words, solutionStartIdx, solutionStartIdx + solutionSize);
}
}
public class Solution {
static class TreeNode{
int val;
int numberOfChildren;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
public static int findKthOfInorder(TreeNode root, int k) {
if (root == null) return -1;
int leftChildCount = (root.left != null) ? root.left.numberOfChildren + 1 : 0;
if (k == leftChildCount + 1) return root.val;
else if (k <= leftChildCount) return findKthOfInorder(root.left, k);
else return findKthOfInorder(root.right, k - leftChildCount - 1);
}
public static TreeNode insertInorderAtKth(TreeNode root, int k, int newVal) {
if (root == null) return k == 1 ? new TreeNode(newVal) : null;
int leftChildCount = (root.left != null) ? root.left.numberOfChildren + 1 : 0;
if (k == leftChildCount + 1) {
TreeNode newNode = new TreeNode(newVal);
newNode.left = root.left;
newNode.right = root;
newNode.numberOfChildren = root.numberOfChildren + 1;
root.left = null;
root.numberOfChildren -= leftChildCount;
return newNode;
} else if (k <= leftChildCount) {
root.left = insertInorderAtKth(root.left, k, newVal);
root.numberOfChildren += root.left != null ? 1: 0;
} else {
root.right = insertInorderAtKth(root.right, k - leftChildCount - 1, newVal);
root.numberOfChildren += root.right != null ? 1: 0;
}
return root;
}
}
public static int[][] generateArray(int N) {
int[][] arr = new int[N][N];
Set<Integer> oneToFour = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Random rand = new Random();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int duplicateInCol = 1;
int duplicateInRow = 1;
if (i > 1 && arr[i - 1][j] == arr[i - 2][j]) { // Same nums in col
duplicateInCol = arr[i - 1][j];
oneToFour.remove(duplicateInCol);
}
if (j > 1 && arr[i][j - 1] == arr[i][j - 2]) { // Same nums in row
duplicateInRow = arr[i][j - 1];
oneToFour.remove(duplicateInRow);
}
arr[i][j] = new ArrayList<>(oneToFour).get(rand.nextInt(oneToFour.size()));
oneToFour.add(duplicateInCol);
oneToFour.add(duplicateInRow);
}
}
return arr;
}
- jgriesser March 05, 2018