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);

}

}

}