Description

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True

Note:

sx, sy, tx, ty will all be integers in the range [1, 10^9].

问题描述

一步为将(x, y)转换为(x + y, y)或者(x, x + y)

给定起始点(sx, sy)和终点(tx, ty),如果经过一系列的移动能从起点到终点，返回true，否则返回false

问题分析

从(x, y)出发可以到达的点的可能性非常多，而从(tx, ty)倒着推只有一条路
即，若tx > ty, tx = tx % ty,否则，ty = ty % tx

举个例子

tx = 5, ty = 7
由于tx < ty,上一轮肯定是(x, x + y),因此ty = ty %tx = 2
依次类推，可以得到初始点为(1, 2)

思路

当tx > sx 且 ty > sy时，将tx和ty倒推
若tx = sx 且 (ty - sy) % sx == 0 或者 ty == sy 且 (tx - sx) % sy ==0 .返回true

解法

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while(tx > sx && ty > sy){
            if(ty < tx) tx %= ty;
            else        ty %= tx;
        }

        if(sx == tx){
            return (ty - sy) % sx == 0;
        }else if(sy == ty){
            return (tx - sx) % sy == 0;
        }

        return false;
    }
}

 1 //C++
 2 class Solution {
 3 public:
 4     bool reachingPoints(int sx, int sy, int tx, int ty) {
 5         if(tx==sx&&ty==sy)
 6         return true;
 7         if(tx==ty||tx==0||ty==0)
 8         return false;
 9         if(ty>tx)
10             return reachingPoints(sx, sy, tx, ty-max((ty-sy)/tx,1)*tx);
11         if(tx>ty)
12             return reachingPoints(sx, sy, tx-max((tx-sx)/ty,1)*ty, ty);   
13         return false;
14     }
15 };

  1 #include <stdio.h>
  2 #include <math.h>
  3 
  4  
  5 #if 1
  6 #define MY_print_ln_E(fmt, arg...)       { if (1 <= g_log_level) {printf("(%s|%d)" fmt"
", __func__, __LINE__, ##arg);} }
  7 #define MY_print_ln_W(fmt, arg...)       { if (2 <= g_log_level) {printf("(%s|%d)" fmt"
", __func__, __LINE__, ##arg);} }
  8 #define MY_print_ln_I(fmt, arg...)       { if (3 <= g_log_level) {printf("(%s|%d)" fmt"
", __func__, __LINE__, ##arg);} }
  9 #define MY_print_ln_D(fmt, arg...)       { if (4 <= g_log_level) {printf("(%s|%d)" fmt"
", __func__, __LINE__, ##arg);} }
 10 #else
 11 #define MY_print_ln_E(fmt, arg...)       {  }
 12 #define MY_print_ln_W(fmt, arg...)       {  }
 13 #define MY_print_ln_I(fmt, arg...)       {  }
 14 #define MY_print_ln_D(fmt, arg...)       {  }
 15 #endif
 16 #define false    (0)
 17 #define true     (1)
 18 
 19 static int g_log_level = 3;
 20 
 21 int max(int a, int b)
 22 {
 23     return  a > b ? a : b;
 24 }
 25 
 26 /**********************************************************************************************
 27         坐标点移动能力测试
 28 
 29     **** 坐标在第一象限移动 ****
 30 
 31     日期: 2020.09.28 21:00:00
 32     作者: LiuYan
 33 
 34     参数: 
 35         sx, 起始点横坐标
 36         sy, 起始点纵坐标
 37         tx, 起始点横坐标
 38         ty, 起始点纵坐标
 39 
 40     返回值: 1能移动到目标坐标, 0不能移动到目标坐标
 41 
 42 **********************************************************************************************/
 43 int move_from_to(int sx, int sy, int tx, int ty)
 44 {
 45     int tmp_x = 0;
 46     int tmp_y = 0;
 47     int move_who = 0; // 0为x, 1为y
 48     int n = 0;
 49 
 50 
 51     MY_print_ln_D("judge from=(%d, %d), to=(%d, %d)
", sx, sy, tx, ty);
 52 
 53     for (tmp_x = tx, tmp_y = ty; !(tmp_x < sx && tmp_y < sy); )
 54     {
 55 
 56         if (tmp_x == sx && tmp_y == sy)
 57         {
 58             MY_print_ln_I("move (%d, %d)->(%d, %d), Success", sx, sy, tx, ty);
 59             return true;
 60         }
 61 
 62         if (tmp_x == tmp_y || 0 == tmp_x || 0 == tmp_y)
 63         {
 64             MY_print_ln_I("move (%d, %d)->(%d, %d), Failed, last_point=(%d, %d)", sx, sy, tx, ty, tmp_x, tmp_y);
 65             return false;
 66         }
 67 
 68         move_who = (tmp_y > tmp_x) ? 1 : 0;
 69 
 70         if (0 == move_who)  // 移动x
 71         {
 72             n = (tmp_x-sx)/tmp_y;
 73             n = n < 1 ? 1 : n;
 74 
 75             tmp_x -= n * tmp_y;
 76         } 
 77         else // 移动y
 78         {
 79             n = (tmp_y-sy)/tmp_x;
 80             n = n < 1 ? 1 : n;
 81 
 82             tmp_y -= n * tmp_x;
 83         }
 84 
 85         MY_print_ln_D("move_who=%d, (%d, %d)", move_who, tmp_x, tmp_y);
 86         
 87     }
 88 
 89     MY_print_ln_I("move (%d, %d)->(%d, %d), Failed, last_point=(%d, %d)", sx, sy, tx, ty, tmp_x, tmp_y);
 90     return false;
 91 }
 92 
 93 int main(int argc, char *argv[])
 94 {
 95     // 成功测试用例
 96     MY_print_ln_I("%d", move_from_to(1, 2, 5, 2));
 97     MY_print_ln_I("%d", move_from_to(2, 3, 2, 9));
 98     MY_print_ln_I("%d", move_from_to(1, 2, 3, 5));
 99     MY_print_ln_I("%d", move_from_to(1, 2, 3, 8));
100     MY_print_ln_I("%d", move_from_to(1, 2, 11, 8));
101     MY_print_ln_I("%d", move_from_to(1, 2, 19, 8));
102     MY_print_ln_I("%d", move_from_to(1, 2, 27, 8));
103 
104     // 失败测试用例
105     MY_print_ln_I("%d", move_from_to(1, 2, 27, 9));
106     return 0;
107 }