手机网站一年费用吗公众号编辑器免费模板

手机网站一年费用吗,公众号编辑器免费模板,东莞网站策划,哈尔滨开网站到达终点数字 问题描述 在一根无限长的数轴上#xff0c;你站在 0 的位置。终点在 target 的位置。 你可以进行移动。每次移动#xff0c;你可以向左或向右移动#xff0c;第 n 次移动#xff08;从 1 开始#xff09;#xff0c;可以走 n 步。 返回到达终点需要的最小移…到达终点数字问题描述在一根无限长的数轴上你站在 0 的位置。终点在target的位置。你可以进行移动。每次移动你可以向左或向右移动第n次移动从 1 开始可以走n步。返回到达终点需要的最小移动次数。注意target可能是负数但由于数轴对称性我们可以只考虑正数情况。示例输入: target 3 输出: 2 解释: 第一次移动从 0 到 1 。 第二次移动从 1 到 3 。输入: target 2 输出: 3 解释: 第一次移动从 0 到 1 。 第二次移动从 1 到 -1 。 第三次移动从 -1 到 2 。算法思路核心对称性target和-target的答案相同所以可以只考虑target 0的情况累加和前k步的最大可达距离是S 1 2 ... k k(k1)/2调整方向如果超过了目标点可以通过将某些步骤改为向左走来调整位置代码实现方法一逐步累加classSolution{/** * 计算到达目标位置所需的最小移动次数 * * param target 目标位置可以是负数 * return 最小移动次数 */publicintreachNumber(inttarget){// 利用对称性只考虑非负目标targetMath.abs(target);intstep0;// 当前移动次数intsum0;// 当前累计移动距离全部向右// 逐步增加步数直到满足条件while(sumtarget||(sum-target)%2!0){step;sumstep;}returnstep;}}方法二数学classSolution{/** * 使用数学直接计算最小步数 * * param target 目标位置 * return 最小移动次数 */publicintreachNumber(inttarget){targetMath.abs(target);// 使用求根公式估算最小的k使得 k(k1)/2 target// k^2 k - 2*target 0// k (-1 sqrt(1 8*target)) / 2intk(int)Math.ceil((-1Math.sqrt(18.0*target))/2);// 计算对应的累加和intsumk*(k1)/2;// 如果差值是偶数直接返回kif((sum-target)%20){returnk;}// 如果差值是奇数需要继续增加步数// 增加1步差值变化为 (sum k 1 - target) (sum - target) (k 1)// 增加2步差值变化为 (sum - target) (k 1) (k 2)// 由于连续两个整数中必有一个是奇数所以最多再走2步就能得到偶数差值if((sumk1-target)%20){returnk1;}else{returnk2;}}}算法分析时间复杂度方法一O(√target)方法二O(1) - 直接数学计算空间复杂度O(1) - 只使用常数空间算法过程1target 3target 3绝对值step 0, sum 0step 1, sum 11 3继续step 2, sum 33 3 且 (3-3)0 是偶数返回22target 2target 2绝对值step 0, sum 0step 1, sum 11 2继续step 2, sum 33 2 但 (3-2)1 是奇数继续step 3, sum 66 2 且 (6-2)4 是偶数返回33target 4step 1, sum 1step 2, sum 3step 3, sum 66 4 且 (6-4)2 是偶数返回3路径1 2 3 6需要减少2所以将第1步反向-1 2 3 4测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例System.out.println(Test 1 (target3): solution.reachNumber(3));// 2// 测试用例2需要调整方向System.out.println(Test 2 (target2): solution.reachNumber(2));// 3// 测试用例3负数目标System.out.println(Test 3 (target-1): solution.reachNumber(-1));// 1// 测试用例4较大目标System.out.println(Test 4 (target10): solution.reachNumber(10));// 4// 测试用例5边界情况System.out.println(Test 5 (target0): solution.reachNumber(0));// 0// 测试用例6需要多步调整System.out.println(Test 6 (target5): solution.reachNumber(5));// 5// 测试用例7较大数值System.out.println(Test 7 (target100): solution.reachNumber(100));// 13// 测试用例8验证对称性System.out.println(Test 8 (target-3): solution.reachNumber(-3));// 2// 测试用例9差值为奇数的情况System.out.println(Test 9 (target7): solution.reachNumber(7));// 5// 测试用例10刚好等于累加和System.out.println(Test 10 (target6): solution.reachNumber(6));// 3}关键点对称性正负目标的解相同简化问题为非负情况累加和前k步的最大可达距离是k(k1)/2这是所有步骤都向同一方向移动的情况反向调整将第i步反向会使总和减少2i只能调整偶数值的距离差奇偶性当(sum - target)为偶数时可以直接调整当为奇数时需要继续增加步数直到差值变为偶数最多需要再走2步因为连续整数的奇偶性交替数学利用求根公式可以快速估算最小步数常见问题为什么反向操作只能改变偶数值原本加i反向后减i总变化量是-2i必为偶数为什么最多再走2步就能解决奇数差值问题连续两个整数中必有一个奇数如果当前差值是奇数加上一个奇数就变成偶数如果k1是偶数则k2必是奇数