bigint subtract

bigint subtract

import java.util.Random;

public class Solution {

public String sub(String str1, String str2) {

if (str1.length() < str2.length() || (str1.length() == str2.length() && str1.compareTo(str2) < 0)) {

return "-" + sub(str2, str1);

}

StringBuilder sb = new StringBuilder();

int i1 = str1.length() - 1;

int i2 = str2.length() - 1;

int carry = 0;

while (i1 >= 0 || i2 >= 0) {

int val = -carry;

val += i1 >= 0 ? (str1.charAt(i1) - '0') : 0;

val -= i2 >= 0 ? (str2.charAt(i2) - '0') : 0;

if (val < 0) {

carry = 1;

val += 10;

} else {

carry = 0;

}

sb.append(val);

i1--;

i2--;

}

return sb.reverse().toString();

}

public static void main(String args[]) {

Solution s = new Solution();

Random r = new Random();

int n1 = r.nextInt(100000000);

int n2 = r.nextInt(100000000);

String n3 = s.sub(Integer.toString(n1), Integer.toString(n2));

System.out.println((n1 + "-" + n2) + "=" + (n1 - n2) + "=" + Integer.parseInt(n3));

}

}

BigInt add

刚刚面完第二轮电面，原题 BigInt, 不过把详细一点的放在这里，和我的答案。// This is the text editor interface. 
// Anything you type or change here will be seen by the other person in real time.
. more info on 1point3acres.com
/*
* class BigInt, to represent non-negative integers of arbitrary size
        * constructor accept a String, representing this non-neg int (e.g. "50"), assume valid input    . visit 1point3acres.com for more.
        * needs to be able to add to another BigInt, and return their sum as a new BigInt object
        * immutable
            * new BigInt("20").add(new BigInt("30")) --> BigInt("50")

import java.util.Random;

public class Solution {

public String add(String str1, String str2) {

StringBuilder sb = new StringBuilder();

int i1 = str1.length() - 1;

int i2 = str2.length() - 1;

int carry = 0;

int base = 10;

while (i1 >= 0 || i2 >= 0 || carry != 0) {

int val = carry;

val += i1 >= 0 ? (str1.charAt(i1) - '0') : 0;

val += i2 >= 0 ? (str2.charAt(i2) - '0') : 0;

carry = val / base;

sb.append(val % base);

i1--;

i2--;

}

return sb.reverse().toString();

}

public static void main(String args[]) {

Solution s = new Solution();

Random r = new Random();

int n1 = r.nextInt(100000000);

int n2 = r.nextInt(100000000);

String n3 = s.add(Integer.toString(n1), Integer.toString(n2));

System.out.println((n1 + n2) == Integer.parseInt(n3));

}

}

compute 24

 24点游戏。给你几个数字，判断他们做加减乘除运算是否可以得到24，顺序可以是任意的。dfs搜索搞定。。。但是这里要注意一些细节，每次计算得到新的数之后最好加入数组做下一次搜索，不然容易出错。

public class Solution {

private boolean compute(int[] nums, int target) {

boolean[] visit = new boolean[nums.length];

return helper(nums, visit, target, nums.length);

}

private boolean helper(int[] nums, boolean[] visit, int target, int c) {

if (c == 1) {

for (int i = 0; i < nums.length; i++) {

if (!visit[i]) {

return nums[i] == target;

}

}

} else {

for (int i = 0; i < nums.length; i++) {

if (visit[i])

continue;

for (int j = i + 1; j < nums.length; j++) {

if (visit[j])

continue;

int n1 = nums[i];

int n2 = nums[j];

visit[j] = true;

nums[i] = n1 + n2;

if (helper(nums, visit, target, c - 1))

return true;

nums[i] = n1 - n2;

if (helper(nums, visit, target, c - 1))

return true;

nums[i] = n2 - n1;

if (helper(nums, visit, target, c - 1))

return true;

nums[i] = n1 * n2;

if (helper(nums, visit, target, c - 1))

return true;

if (n2 != 0) {

nums[i] = n1 / n2;

if (helper(nums, visit, target, c - 1))

return true;

}

if (n1 != 0) {

nums[i] = n2 / n1;

if (helper(nums, visit, target, c - 1))

return true;

}

nums[i] = n1;

visit[j] = false;

}

}

}

return false;

}

public static void main(String args[]) {

Solution s = new Solution();

System.out.println(s.compute(new int[] { 2, 3, 2, 1 }, 24));

}

}

find all amicable numbers.

1. find all amicable numbers. more info on 1point3acres.com
输入一个正整数，找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff，最后写了时间复杂度O(n^1.5)，空间复杂度O(n)的算法。

import java.util.ArrayList;

import java.util.List;

public class Solution {

public List<int[]> findAmicable(int num) {

List<int[]> res = new ArrayList<>();

for (int i = 1; i <= num; i++) {

int factorSum = getFactorSum(i);

if (i < factorSum && factorSum <= num) {

int factorSum2 = getFactorSum(factorSum);

if (i == factorSum2) {

res.add(new int[] { i, factorSum });

}

}

}

return res;

}

private int getFactorSum(int num) {

int res = 1;

for (int i = 2; i <= Math.sqrt(num); i++) {

if (num % i == 0) {

res += i;

res += num / i;

}

}

return res;

}

public static void main(String args[]) {

Solution s = new Solution();

List<int[]> res = s.findAmicable(3000);

for (int[] arr : res) {

System.out.println(arr[0] + " " + arr[1]);

}

}

}

k-snap point

// This is the text editor interface.  // Anything you type or change here will be seen by the other person in real time. /* Consider a grid where all the points are represented by integers. ..........................................鐣欏璁哄潧-涓€浜�-涓夊垎鍦� ...(-2,2)  (-1,2)  (0,2)  (1,2)  (2,2)... ...(-2,1)  (-1,1)  (0,1)  (1,1)  (2,1)... ...(-2,0)  (-1,0)  (0,0)  (1,0)  (2,0)... ...(-2,-1) (-1,-1) (0,-1) (1,-1) (2,-1)... ...(-2,-2) (-1,-2) (0,-2) (1,-2) (2,-2)... .......................................... k-Snap point: A point whose digits sum up to less than or equal to k. In this question, we ignore all the signs in the number.  For exxample, (1, 0) is a 1-snap point, (0, 10) is a 1-snap point, and (-100, 0) is also a 1-snap point; however (11, 0) is not a 1-snap point. Question 1: Implement the following function boolean isSnapPoint(Point p, int k). visit 1point3acres.com for more. Returns true if p is a k-snap point, and false otherwise.. more info on 1point3acres.com Reachable k-snap point: A k-snap point is a reachable k-snap point if there is a path from (0,0) to that point, where the path only consists of k-snap points. Question 2: Given k, return all the reachable k-snap points.. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴 */. from: 1point3ac

import java.util.HashSet;

import java.util.Set;

public class Solution {

public static class Point {

int x;

int y;

public Point(int x, int y) {

this.x = x;

this.y = y;

}

public boolean equals(Object o2) {

if (o2 instanceof Point) {

Point p2 = (Point) o2;

return this.x == p2.x && this.y == p2.y;

}

return false;

}

public int hashCode() {

return (x + " " + y).hashCode();

}

public String toString() {

return (x + " " + y);

}

}

private Set<Point> getAllPoint(int k) {

Set<Point> res = new HashSet<>();

helper(new Point(0, 0), k, res);

return res;

}

private void helper(Point p, int k, Set<Point> res) {

// System.out.println(p);

if (isKSnap(p, k)) {

res.add(p);

} else {

return;

}

Point left = new Point(p.x - 1, p.y);

if (!res.contains(left)) {

helper(left, k, res);

}

Point right = new Point(p.x + 1, p.y);

if (!res.contains(right)) {

helper(right, k, res);

}

Point up = new Point(p.x, p.y + 1);

if (!res.contains(up)) {

helper(up, k, res);

}

Point down = new Point(p.x, p.y - 1);

if (!res.contains(down)) {

helper(down, k, res);

}

}

private boolean isKSnap(Point p, int k) {

int sum = getSum(p.x);

if (sum > k) {

return false;

}

sum += getSum(p.y);

if (sum > k) {

return false;

}

return true;

}

private int getSum(int x) {

x = Math.abs(x);

int res = 0;

while (x != 0) {

res += x % 10;

x /= 10;

}

return res;

}

public static void main(String args[]) {

Solution s = new Solution();

System.out.println(s.isKSnap(new Point(0, 1), 1));

System.out.println(s.isKSnap(new Point(0, 10), 1));

System.out.println(s.isKSnap(new Point(0, 101), 1));

Set<Point> ps = s.getAllPoint(2);

for (Point p : ps) {

System.out.println(p);

}

}

}

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it, each time your friend guesses a number, you give a hint, the hint tells your friend how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows"), your friend will use those hints to find out the secret number.

For example:

Secret number:  1807
Friend's guess: 7810

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

According to Wikipedia: "Bulls and Cows (also known as Cows and Bulls or Pigs and Bulls or Bulls and Cleots) is an old code-breaking mind or paper and pencil game for two or more players, predating the similar commercially marketed board game Mastermind. The numerical version of the game is usually played with 4 digits, but can also be played with 3 or any other number of digits."

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows, in the above example, your function should return 1A3B.

You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Credits:

Special thanks to @jeantimex for adding this problem and creating all test cases.

public class Solution {
    public String getHint(String secret, String guess) {
        int a = 0;
        int b = 0;
        int[] nums = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            int c1 = secret.charAt(i) - '0';
            int c2 = guess.charAt(i) - '0';
            if (c1 == c2) {
                a++;
            } else {
                if (nums[c1] < 0) {
                    b++;
                }
                if (nums[c2] > 0) {
                    b++;
                }
                nums[c1]++;
                nums[c2]--;
            }
        }
        return a + "A" + b + "B";
    }
}

Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    private int maxLen = 0;
   
    public int longestConsecutive(TreeNode root) {
        maxLen = 0;
        if (root == null) {
            return maxLen;
        }
        helper(root, 1);
        return maxLen;
    }
   
    private void helper(TreeNode node, int len) {
        if (node == null) return;
        maxLen = Math.max(maxLen, len);
        if (node.left != null) {
            if (node.left.val == node.val + 1) {
                helper(node.left, len + 1);
            } else {
                helper(node.left, 1);
            }
        }
        if (node.right != null) {
            if (node.right.val == node.val + 1) {
                helper(node.right, len + 1);
            } else {
                helper(node.right, 1);
            }
        }
    }
}