LeetCode | 754. Reach a Number 数学原理题解析与证明 - u012737193的博客 - CSDN博客
给你一个数，第n次可以向左走，也可以向右走，问你最少多少次可以走到目的地
一开始我考虑的是广度优先遍历解决，但是这样的话由于target太大，内存超了，于是只好考虑其他的方法，思考过后我发现这题用数学的方法解决其实很简单，首先，要到达目的地一定会有向左和向右，我们假设一定有一个最好的方案，a1,a2,a3…an,假如a1到an都是正数，那么它一定是最好的方案，假如存在负数，那么可以看成把a1,a2…an里面的若干个数变成负数，然后到达target，可以证明，当a1+a2..an-target为偶数的时候，只需要把a1,a2,…an里面的一个数变成负数就能到达目的地，这就是最好的方案
当a1+a2..an-target为奇数的时候，有两种情况，当n为偶数的时候，n+1为奇数，可以证明，当把a1,a2..an里面一个数变成负数之后，只要在加一个数就能到达target，也就是a1+a2…an+an+1一定可以到达target,当n为奇数的时候，可以证明当把a1,a2..an里面一个数变成负数之后只要在加两个个数就能到达target，也就是a1+a2…an+an+1+an+2,所以有以下算法
Read full article from LeetCode | 754. Reach a Number 数学原理题解析与证明 - u012737193的博客 - CSDN博客
No comments:
Post a Comment