您现在的位置是：首页 >技术杂谈 >代码随想录补打卡 392 判断子序列 53 最大子数组和 115 不同的子序列网站首页技术杂谈

392 判断子序列 

代码如下 

func isSubsequence(s string, t string) bool {   //dp[i][j]数组的含义是到下标i-1和到下标j-1相同子序列的长度

           dp := make([][]int,len(s)+1)    设置二维数组

           for i,_ := range dp {

               dp[i] = make([]int,len(t)+1)   

           }

           for i := 1 ; i <= len(s) ; i++ {     遍历数组

               for j := 1 ; j <= len(t) ; j++ {

                   if s[i-1] == t[j-1] {    如果元素相同 

                       dp[i][j] = dp[i-1][j-1]+1 则说明相同的子序列长度需要加上该元素，即在没有算上该元素的长度上加1 

                   }else {

                       dp[i][j] = dp[i][j-1]    如果不相同，则要去除掉t序列，即较长数组的当前一个元素，继续匹配

                   }

               }

           }

           if dp[len(s)][len(t)] == len(s) {  如果最终的结果是相同子序列长度和s即较短的数组长度一致，说明较短数组是长数组的子序列 

               return true 

           }else {

               return false 

           }

}

53 最大数组和 

func maxSubArray(nums []int) int {

          dp := make([]int,len(nums))  dp数组的含义是到当前下标，数组的和

          dp[0] = nums[0]      

          res := dp[0]   记录一个最大值 

          for i := 1 ; i < len(nums) ; i++ { 遍历数组

              dp[i] = max(dp[i-1]+nums[i],nums[i])  当前数组的和有两种可能一种是到前一个元素的和加上当前元素，或者是直接算当前元素，取两者较大的值

              if dp[i] > res {

                  res = dp[i]

              }

          }

          return res 

}

func max(a,b int) int {

    if a > b {

        return a

    }else {

        return b 

    }

}

115 不同的子序列

代码如下

func numDistinct(s string, t string) int {

             dp := make([][]int,len(s)+1)    dp数组的含义是以i-1为结尾的s中出现以j-1为结尾的t数组的个数，举例来说  s为 abcaaa t为a 则在s数组中，出现t的个数为4 

             for i,_ := range dp {

                 dp[i] = make([]int,len(t)+1)

             }

             for i := 0 ; i <= len(s) ; i++ {

                 dp[i][0] = 1        dp[i][0] 表示t数组为空，则说明个数为1个

             }

             for i := 1 ; i <= len(s) ; i++ {

                 for j := 1 ; j <= len(t) ; j++ {

                     if s[i-1] == t[j-1] {  如果当前元素相同，则有两种可能，一种是放入这两个元素，其个数则等于在没放入两个元素之前的数组的 举例来说 s为babg t为bag 在最后同时放入g时，他的结果等于bab 中出现ba的个数 第二种可能是在长数组中不放入这个元素，在短数组放入这个元素，放入元素后的新数组出现在原来的长数组中，举例来说bagbbg 和 bag 当两个数组都要放入最后的g时，长数组可以不放入g因为之前已经有出现过bag

                         dp[i][j] = dp[i-1][j-1]+dp[i-1][j]

                     }else {

                         dp[i][j] = dp[i-1][j]     //如果两个元素不相同，则要去除掉长数组中的元素继续匹配，举例来说，bagbbg和bag，当放入b和g时两个元素不同则要，去除掉b，因为根据定义要在长数组中找到bag出现的个数，但是当前这个b元素在数组中没有按顺序出现即没有在a后面出现，所以需要去除

                     }

                 }

             }

             return dp[len(s)][len(t)]

}