JavaGuide算法题

一、KMP算法

对于两个字符串s1、s2。请设计一个高效算法，找到s1在s2中第一次出现的起始位置。若s2未在s1中出现，则返回-1。

class StringPattern:
    def findAppearance(self, s1, s2):
        array = [-1]
        for i in range(len(s2)-1):
            cur = s2[:i+1]
            change = False
            for j in range(len(cur)-1, 0, -1):
                if cur[:j] == cur[len(cur)-j:]:
                    change = True
                    array.append(j)
                    break
            if change == False:
                array.append(0)
        start1, start2 = 0, 0
        while start1 <= len(s1)-1 and start2 <= len(s2)-1:
            if s1[start1] == s2[start2]:
                start1 += 1
                start2 += 1
                if start2 == len(s2):
                    return start1-len(s2)
            else:
                if array[start2] == -1:
                    start2 = 0
                    start1 += 1
                else:
                    start2 = array[start2]
        return -1

二、替换空格

请实现一个函数，将一个字符串中的每个空格替换成%20。例如，当字符串为We Are Happy，则经过替换之后的字符串为We%20Are%20Happy。

class Solution:
    def replaceSpace(self, s):
        return s.replace(' ', '%20')

三、最长公共前缀

请实现一个函数，找到一个数组中所有字符串最长的公共前缀。如果没有公共前缀，返回""。

先对strs排序，然后找第一个元素和组后一个元素的最长公共前缀即可。

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        strs.sort()
        i = 0
        ans = ""
        while i <= len(strs[0])-1 and i <= len(strs[-1])-1:
            if strs[0][i] == strs[-1][i]:
                ans += strs[0][i]
                i += 1
            else:
                return ans
        return ans

四、最长回文串

给定一个包含大写和小写字母的字符串，找到通过这些字母能构成的最长回文串。

（1）统计每个字母出现的次数；
（2）将每个字母出现次数的偶数部分添加到答案中；
（3）如果有一个或以上字母出现次数为奇数，答案加1。

class Solution:
    def longestPalindrome(self, s):
        hashTable = dict()
        for c in s:
            hashTable[c] = hashTable.get(c, 0) + 1
        ans = 0
        midone = False
        for key in hashTable:
            if not midone and hashTable[key] % 2 == 1:
                midone = True
            ans += hashTable[key] // 2 * 2
        if midone:
            ans += 1
        return ans

五、验证回文串

给定一个字符串，判断它是否是回文串。只考虑字母和数字字符，可忽略字母的大小写。空字符串为有效回文串。

双指针法最快。

class Solution:
    def isPalindrome(self, s):
        left, right = 0, len(s)-1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while right > left and not s[right].isalnum():
                right -= 1
            if left == right:
                return True
            elif s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                return False
        return True

六、最长回文子串

给定一个字符串s，找到s中最长的回文子串。

遍历字符串，以某个元素为中心，分别计算偶数长度的最长回文子串和奇数长度的最长回文子串。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def judgePalindrome(s, l, r):
            while l >= 0 and r <= len(s)-1 and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l+1:r]
        if len(s) == 1:
            return s
        ans = ""
        for i in range(len(s)-1):
            if min(2*i+1, 2*(len(s)-1-i)+1) > len(ans): # 优化
                cur = judgePalindrome(s, i, i)
                if len(cur) > len(ans):
                    ans = cur
            if min(2*(i+1), 2*(len(s)-1-i)) > len(ans): # 优化
                cur = judgePalindrome(s, i, i+1)
                if len(cur) > len(ans):
                    ans = cur
        return ans

七、最长回文子序列

给定一个字符串s，找到其中最长的回文子序列。

用动态规划。 $dp[i][i] = 1$
（1）如果 $s[i] = s[j]$ ，则 $dp[i][j] = dp[i+1][j-1] + 2$
（2）如果 $s[i] != s[j]$ ，则 $dp[i][j] = max(dp[i+1][j], dp[i][j-1])$

解一：

class Solution:
    def longestPalindromeSubseq(self, s):
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(0, len(s)):
            dp[i][i] = 1
        for j in range(1, len(s)):
            for i in range(0, len(s)-1):
                if i+j > len(s)-1:
                    break
                if s[i] == s[i+j]:
                    dp[i][i+j] = dp[i+1][i+j-1] + 2
                else:
                    dp[i][i+j] = max(dp[i+1][i+j], dp[i][i+j-1])
        return dp[0][len(s)-1]

解二：

class Solution:
    def longestPalindromeSubseq(self, s):
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][len(s)-1]

八、括号匹配深度

一个合法的括号匹配序列有以下定义:
1、空串""是一个合法的括号匹配序列
2、如果"X"和"Y"都是合法的括号匹配序列，"XY"也是一个合法的括号匹配序列
3、如果"X"是一个合法的括号匹配序列，那么"(X)"也是一个合法的括号匹配序列
4、每个合法的括号序列都可以由以上规则生成。
例如：""，"()"，"()()"，"((()))"都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
1、空串""的深度是0
2、如果字符串"X"的深度是x，字符串"Y"的深度是y，那么字符串"XY"的深度为max(x,y)
3、如果"X"的深度是x，那么字符串"(X)"的深度是x+1
例如："()()()"的深度是1，"((()))"的深度是3。牛牛现在给你一个合法的括号序列，需要你计算出其深度。

解法是遍历字符串，遇到一个(，计数器加1；遇到一个)，计数器减1。遍历过程中计数器的最大值就是答案了。

import sys
s = sys.stdin.readline().strip()
cur, ans = 0, 0
for c in s:
    if c == '(':
        cur += 1
    else:
        cur -= 1
    ans = max(cur, ans)
print(ans)

九、把字符串转换成整数

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。

class Solution:
    def StrToInt(self, s):
        if not s:
            return 0
        if s in '+-':
            return 0
        rev = 1
        if s[0] == '+':
            s = s[1:]
        elif s[0] == '-':
            rev = -1
            s = s[1:]
        ans = 0
        k = 1
        for c in s[::-1]:
            if not (c >= '0' and c <= '9'):
                return 0
            else:
                ans += int(c)*k
                k *= 10
        return ans*rev

十、链表两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
https://leetcode.com/problems/add-two-numbers/

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        val1, val2, carrier = 0, 0, 0
        l = ListNode()
        ans = l
        while l1 or l2 or carrier:
            if l1:
                val1 = l1.val
                l1 = l1.next
            else:
                val1 = 0
            if l2:
                val2 = l2.val
                l2 = l2.next
            else:
                val2 = 0
            val = (val1 + val2 + carrier) % 10
            newnode = ListNode(val)
            l.next = newnode
            l = l.next
            carrier = (val1 + val2 + carrier) // 10
        return ans.next

十一、翻转链表

输入一个链表，反转链表后，输出链表的所有元素。
https://leetcode.com/problems/reverse-linked-list/submissions/

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        pre, cur = head, head.next
        pre.next = None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

反转链表的第m到n个元素，然后输出链表的所有元素。
https://leetcode.com/problems/add-two-numbers-ii/

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        count = 1
        dummy = pre = ListNode()
        pre.next = head
        cur = head
        while True:
            if count == m:
                front = pre
                start = cur
                while count <= n:
                    count += 1
                    tmp = cur.next
                    cur.next = pre
                    pre = cur
                    cur = tmp
                front.next = pre
                start.next = cur
                return dummy.next
            count += 1
            pre = pre.next
            cur = cur.next

十二、删除链表中倒数第N个节点

输入一个链表，删除该链表中倒数第N个节点，返回链表的头节点。

十三、删除链表中倒数第N个节点

输入一个链表，删除该链表中倒数第N个节点，返回链表的头节点。
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
快慢指针法。

class Solution:
    def removeNthFromEnd(self, head, n: int) -> ListNode:
        slow, fast = head, head
        for i in range(n):
            fast = fast.next
        if not fast:
            return slow.next
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return head

十四、合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

class Solution:
    def Merge(self, pHead1, pHead2):
        pHead = ListNode(0)
        ans = pHead
        while pHead1 or pHead2:
            if pHead1 and pHead2:
                if pHead1.val < pHead2.val:
                    newNode = ListNode(pHead1.val)
                    pHead1 = pHead1.next
                else:
                    newNode = ListNode(pHead2.val)
                    pHead2 = pHead2.next
                pHead.next = newNode
                pHead = pHead.next
            elif pHead1:
                pHead.next = pHead1
                return ans.next
            elif pHead2:
                pHead.next = pHead2
                return ans.next
        return ans.next

递归写法：

class Solution:
    def Merge(self, pHead1, pHead2):
        if not pHead1:
            return pHead2
        elif not pHead2:
            return pHead1
        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next, pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead2.next, pHead1)
            return pHead2

十五、斐波那契数列

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

class Solution:
    def Fibonacci(self, n):
        if n == 0 or n == 1:
            return n
        dp1, dp2 = 0, 1
        for i in range(2, n+1):
            tmp = dp2
            dp2 += dp1
            dp1 = tmp
        return dp2

十六、二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e
从右上角开始搜索，左边元素比当前元素小，下边元素比当前元素大。

class Solution:
    def Find(self, target, array):
        m, n = 0, len(array[0])-1
        while m <= len(array)-1 and n >= 0:
            if array[m][n] == target:
                return True
            elif array[m][n] > target:
                n -= 1
            else:
                m += 1
        return False

十七、数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。
https://www.nowcoder.com/questionTerminal/1a834e5e3e1a4b7ba251417554e07c00
复杂度 $logn$

class Solution:
    def Power(self, base, exponent):
        if base == 0:
            return 0
        elif exponent == 0:
            return 1
        e = abs(exponent)
        tmp = base
        while e > 1:
            tmp *= tmp
            if e % 2 == 1:
                tmp *= base
                e -= 1
            e //= 2
        if exponent < 0:
            return 1 / tmp
        else:
            return tmp

十八、调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
https://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593

class Solution:
    def reOrderArray(self, array):
        count = 0
        for num in array:
            if num % 2 == 1:
                count += 1
        jishu, oushu = 0, count
        ans = [None for _ in range(len(array))]
        for num in array:
            if num % 2 == 1:
                ans[jishu] = num
                jishu += 1
            else:
                ans[oushu] = num
                oushu += 1
        return ans

十九、用两个栈实现队列

https://www.nowcoder.com/questionTerminal/54275ddae22f475981afa2244dd448c6

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()