u***8
发帖数: 1581 | 1 这个是dp的问题吧。
给一个数字n，用减1，or 能整除2 就整除，能整除3就整除，3种方法，将n 减到1。
求最少的steps。
好像简单的。
我给了个算法。最后15分钟，有点赶。leetcode有类似题目么？不记得了。貌似有个变
形的题目，类似。
public int getMinSteps(int n) { // 1 ---> n , better way to do from n
-->1
int[] arr = new int[n]; arr[i] denotes how many steps to get value
i+1;
//dynamic programming to refresh the array;
//arr[i] denotes min steps to reach 1＋i, so 1 =1 , 0 steps needed.
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < n ; i++) {
int min = arr[i-1] + 1// this value is the +1 operation to get
the number i+1;
//so
if ( (i+1) % 3 == 0) {
min = Math.min(arr[(i+1)/3 - 1] + 1, min);// make sure the
min
}
if ( (i+1) % 2 == 0) {
min = Math.min(arr[(i+1)/2-1] + 1, min);//make sure
}
}
return arr[n-1];// n-1+1 = n
}
|
a********5
发帖数: 1631 | 2 dp[0] = -1, dp[1] = 0.
dp[n] = min {
dp[n-1],
dp[n/2] if n%2 == 0,
dp[n/3] if n%3 == 0
} + 1
print dp[n]
n
value
【在 u***8 的大作中提到】
: 这个是dp的问题吧。
: 给一个数字n，用减1，or 能整除2 就整除，能整除3就整除，3种方法，将n 减到1。
: 求最少的steps。
: 好像简单的。
: 我给了个算法。最后15分钟，有点赶。leetcode有类似题目么？不记得了。貌似有个变
: 形的题目，类似。
: public int getMinSteps(int n) { // 1 ---> n , better way to do from n
: -->1
: int[] arr = new int[n]; arr[i] denotes how many steps to get value
: i+1;
|
w****e
发帖数: 586 | 3 实际运行bfs可能更快点。worst case大概都是O(n),但是bfs大多情况下不需要把1到n
都算一遍 |
u***8
发帖数: 1581 | 4 how?
n
【在 w****e 的大作中提到】
: 实际运行bfs可能更快点。worst case大概都是O(n),但是bfs大多情况下不需要把1到n
: 都算一遍
|
V***a
发帖数: 206 | 5 变形版本是hackerrank原题Down To Zero II
https://www.hackerrank.com/challenges/down-to-zero-ii
从归类看是bfs做的，下面这个bfs做法pass了。
static Map> route = new HashMap
>();
static Map cache = new HashMap();
public int downZero(int K) {
if (K == 0)
return 0;
if (cache.containsKey(K))
return cache.get(K);
Queue q = new LinkedList();
boolean[] marked = new boolean[K+1];
int step = 1;
q.add(K);
marked[K] = true;
while (! q.isEmpty()) {
int counter = q.size();
for (int j = 0; j < counter; j++) {
int P = q.poll();
if (P == 1) {
cache.put(K, step);
return step;
}
for (Integer d : findRoute(P)) {
if (! marked[d]) {
marked[d] = true;
q.add(d);
}
}
}
step ++;
}
return -1;
}
public List findRoute(int P) {
if (route.containsKey(P)) {
return route.get(P);
}
List res = new ArrayList();
for (int i = 2; i <= (int)Math.sqrt((double)P); i++) {
if (P % i == 0) {
res.add(P / i);
}
}
res.add(P - 1);
route.put(P, res);
return res;
} |
w****e
发帖数: 586 | 6 从n开始往回走，搜走到1的最短路径啊。用长度为n的array存着搜过的点的最短路径长
度，
避免以后重复搜索。空间复杂度O(n)。标准的bfs
【在 u***8 的大作中提到】
: how?
:
: n
|
