algorithms/leetcode/2311-LongestBinarySubsequenceLessThanOrEqualToK.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package main

// 2311. Longest Binary Subsequence Less Than or Equal to K
// You are given a binary string s and a positive integer k.

// Return the length of the longest subsequence of s that makes up a binary number less than or equal to k.

// Note:
//     1. The subsequence can contain leading zeroes.
//     2. The empty string is considered to be equal to 0.
//     3. A subsequence is a string that can be derived from another string by deleting some
//        or no characters without changing the order of the remaining characters.

// Example 1:
// Input: s = "1001010", k = 5
// Output: 5
// Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
// Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
// The length of this subsequence is 5, so 5 is returned.

// Example 2:
// Input: s = "00101001", k = 1
// Output: 6
// Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
// The length of this subsequence is 6, so 6 is returned.

// Constraints:
//     1 <= s.length <= 1000
//     s[i] is either '0' or '1'.
//     1 <= k <= 10^9

import "fmt"
import "math"
import "strings"
import "math/bits"
import "strconv"

// 解答错误 151 / 153
// func longestSubsequence(s string, k int) int {
//     res, sum, flag := 0, 0, false
//     pow := func (b int, p int) int { // 求幂
//         res := 1
//         for i := 0; i < p; i++ {
//             res *= b
//         }
//         return res
//     }
//     for i := len(s) - 1; i >= 0; i--{
//         if rune(s[i]) == '0' {
//             res++
//         } else if !flag {
//             sum += pow(2, res)
//             if sum > k {
//                 flag = true
//             } else {
//                 res++
//             }
//         }
//     }
//     return res
// }

func longestSubsequence(s string, k int) int {
    res, sum, flag := 0, float64(0), false
    for i := len(s) - 1; i >= 0; i--{
        if s[i] == '0'{
            res++
        } else if !flag {
            sum += math.Pow(float64(2), float64(res))
            if sum > float64(k) {
                flag = true
            } else {
                res++
            }
        }
    }
    return res
}

func longestSubsequence1(s string, k int) int {
    n, m := len(s), bits.Len(uint(k))
    if n < m { return n }
    res := m
    if v, _ := strconv.ParseInt(s[n-m:], 2, 0); int(v) > k {
        res--
    }
    return res + strings.Count(s[:n-m], "0")
}

func main() {
    // Example 1:
    // Input: s = "1001010", k = 5
    // Output: 5
    // Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
    // Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
    // The length of this subsequence is 5, so 5 is returned.
    fmt.Println(longestSubsequence("1001010", 5)) // 5
    // Example 2:
    // Input: s = "00101001", k = 1
    // Output: 6
    // Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
    // The length of this subsequence is 6, so 6 is returned.
    fmt.Println(longestSubsequence("00101001", 1)) // 6

    fmt.Println(longestSubsequence("1111111111", 1)) // 1
    fmt.Println(longestSubsequence("1111100000", 1)) // 5
    fmt.Println(longestSubsequence("0000011111", 1)) // 6
    fmt.Println(longestSubsequence("0000000000", 1)) // 10
    fmt.Println(longestSubsequence("0101010101", 1)) // 6
    fmt.Println(longestSubsequence("1010101010", 1)) // 5

    fmt.Println(longestSubsequence1("1001010", 5)) // 5
    fmt.Println(longestSubsequence1("00101001", 1)) // 6
    fmt.Println(longestSubsequence1("1111111111", 1)) // 1
    fmt.Println(longestSubsequence1("1111100000", 1)) // 5
    fmt.Println(longestSubsequence1("0000011111", 1)) // 6
    fmt.Println(longestSubsequence1("0000000000", 1)) // 10
    fmt.Println(longestSubsequence1("0101010101", 1)) // 6
    fmt.Println(longestSubsequence1("1010101010", 1)) // 5
}