Jun 22

网易有道难题。。。止步于复赛。。。

昨晚看见第3题就囧了。。。套用某人一句话。。。这俨然不是为我等小菜准备的。。。

做好前两道题用了1小时左右。。。剩下的时间都浪费在第3道上了。。。没做完是一定的。。。结果系统测试的时候第2题挂掉了。。。orz

下来以后越想越郁闷。。。第2题估计就是漏了一个处理。。。如果直接放弃第3题的话应该是可以检查出来的。。。

只能说经验不足了。。。其实第一次参加编程比赛。。。这个成绩也是意料之内。。。下次再接再厉了。。。

第一题代码:

    Public Function getNext(ByVal A As Long) As Long


        A += 1 ' bigger than a
        Dim sA As String = A.ToString()

        Dim i As Integer
        For i = 0 To sA.Length - 2
            If sA(i) = sA(i + 1) Then
                Exit For
            End If
        Next
        If i = sA.Length - 1 Then
            Return A ' A is non repeating number
        End If
        Dim leftPart As Long = (Long.Parse(sA.Substring(0, i + 1)))
        Dim rightPart As New System.Text.StringBuilder
        Dim isZero As Boolean = True

        Dim rightFirst As Long = Long.Parse(sA(i + 1)) + 1
        If rightFirst > 9 Then
            rightFirst = 0
            leftPart = getNext(leftPart)
            Dim newA As String = leftPart & rightFirst
            If i + 2 < sA.Length Then
                newA = newA & sA.Substring(i + 2)
            End If
            Return getNext(Long.Parse(newA))
        End If

        rightPart.Append(rightFirst)
        For j As Integer = i + 2 To sA.Length - 1
            If isZero Then
                rightPart.Append("0")
            Else
                rightPart.Append("1")
            End If
            isZero = Not isZero
        Next
        Return Long.Parse(leftPart & rightPart.ToString())

    End Function

 

第二题:

 

	Public Function maximize(ByVal word As String, ByVal maxChanges As Integer) As Integer


        If word.Length = 1 Then
            Return 1
        End If
        Dim counts As IDictionary(Of Char, Integer) = CountChars(word)
        Dim chars As Char() = word.ToCharArray()
        Dim changes As Integer = 0
        For i As Integer = 0 To word.Length \ 2
            If chars(i) <> chars(chars.Length - i - 1) Then
                If changes = maxChanges Then
                    'not a palindrome
                    Return 0
                End If
                changes += 1
		' 这里我忘记修正字符数了。。。应该就是这个原因而挂掉了。。。迟一点要去平台再试试。。。
                If counts(chars(i)) > counts(chars(chars.Length - i - 1)) Then
                    chars(chars.Length - i - 1) = chars(i)
                Else
                    chars(i) = chars(chars.Length - i - 1)
                End If
            End If
        Next
        If changes = maxChanges Then
            Return Score(New String(chars))
        ElseIf (chars.Length And 1) = 1 Then
            Return 1
        Else
            Return maximize(New String(chars, 0, chars.Length \ 2), maxChanges - changes) + 1
        End If
    End Function

    Private Function CountChars(ByVal word As String) As IDictionary(Of Char, Integer)
        Dim charCounts As New SortedList(Of Char, Integer)
        For Each ch As Char In word
            If charCounts.ContainsKey(ch) Then
                charCounts(ch) += 1
            Else
                charCounts(ch) = 1
            End If
        Next
        Return charCounts
    End Function

    Private Function Score(ByVal word As String) As Integer
        For i As Integer = 0 To word.Length \ 2
            If word.Chars(i) <> word.Chars(word.Length - i - 1) Then
                Return 0 ' not a palindrome
            End If
        Next
        If (word.Length And 1) = 1 Then
            Return 1 ' odd length
        Else
            Return Score(word.Substring(word.Length \ 2)) + 1
        End If
    End Function