golang刷leetcode 技巧（28）交换数字、三步问题

golangLeetcode

发布于 2022-08-02 18:44:06

2630

文章被收录于专栏：golang算法架构leetcode技术phpgolang算法架构leetcode技术php

编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。

示例：

输入: numbers = [1,2]

输出: [2,1]

提示：

numbers.length == 2

解题思路：

方法一：

求和

方法二：

异或

代码实现：

func swapNumbers(numbers []int) []int {
   numbers[0]+=numbers[1]
   numbers[1]=numbers[0]-numbers[1]
   numbers[0]-=numbers[1]
   return numbers
}

func swapNumbers(numbers []int) []int {
   numbers[0]^=numbers[1]
   numbers[1]=numbers[0]^numbers[1]
   numbers[0]^=numbers[1]
   return numbers
}

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

输入：n = 3

输出：4

说明: 有四种走法

示例2:

输入：n = 5

输出：13

提示:

n范围在[1, 1000000]之间

解题思路：

1，递归

到达第n步，可以是从n-3步迈3步，或者n-2迈2步，或者n-1迈1步

2，dp

状态转移方程，f（n）=f(n-3)+f(n-2)+f(n-1)

由于用到了n-3,n-2,n-1所以递增方式

func waysToStep(n int) int {
   if n==1{
       return 1
   }
   if n==2{
       return 2
   }
   if n==3{
       return 4
   }
   return (waysToStep(n-3)+waysToStep(n-2)+waysToStep(n-1))%1000000007
}

func waysToStep(n int) int {
    dp:=make([]int,n)
    
   if n==1{
       return 1
   }
   if n==2{
       return 2
   }
   if n==3{
       return 4
   }
   dp[0]=1
   dp[1]=2
   dp[2]=4
   for i:=3;i<n;i++{
       dp[i]=(dp[i-3]+dp[i-2]+dp[i-1])%1000000007
   }
   return dp[n-1]
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-11，如有侵权请联系 cloudcommunity@tencent.com 删除

dp