到达点-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

1. 给定一个点对(x,y)，每次操作可以变换成(x,x+y)或者(x+y,y)
2. 给定两个点对(sx, sy)，和(tx, ty)，问能否通过任意次操作，使前一个点对可以变换成后一个点对

思路：

- 我们反正来，如果得到一个点对(x,y)，最有可能是从哪些点对来的
- 假设tx<ty，反之亦然
- 那么点对可以从(tx,ty),(tx, ty-tx),(tx,ty-k*tx)。。。得来的
- 我们可以得出一个递归方式
- 如果sx>tx，直接返回false，因为sx不管怎么变换，都不能比sx小
- 如果sx=tx，判断(ty-sy)是否不小于0，并且可以被sx整除
- 如果sx<tx，那么我们需要判断(sx, sy)和(tx, ty % tx)是否可以变换
- 这个算法叫做辗转相除法，也叫欧几里得算法，计算最大公约数也是这个算法

解法：

class Solution {
    	 private boolean solve(int sx, int sy, int tx, int ty) {
            if (tx < ty) {
                if (tx < sx) {
                    return false;
                }
                if (tx == sx) {
                    if (ty >= sy && (ty - sy) % sx == 0) {
                        return true;
                    } else {
                        return false;
                    }
                }
                return solve(sx, sy, tx, ty % tx);
            } else {
                if (ty < sy) {
                    return false;
                }
                if (ty == sy) {
                    if (tx >= sx && (tx - sx) % sy == 0) {
                        return true;
                    } else {
                        return false;
                    }
                }
                return solve(sx, sy, tx % ty, ty);
            }
        }
    
        public boolean reachingPoints(int sx, int sy, int tx, int ty) {
            return solve(sx, sy, tx, ty);
        }
    }

该分类下的相关小册推荐：

编程之道-算法面试(下)

业务开发实用算法精讲

算法面试通关 50 讲

数据结构与算法之美

数据结构与算法(下)

数据结构与算法(上)

编程之道-算法面试(上)