前言：好久没上lintcode了，今天一登，发现有好多新题。先刷几十道玩玩。

Palindrome Permutation

链接： http://lintcode.com/zh-cn/problem/palindrome-permutation/
描述：Given a string, determine if a permutation of the string could form a palindrome.
解析： 如果想组成回文串，每个字母的个数一定得是偶数，只有中间字母可以是奇数个。所以，把所有的字母的个数统计一下，做下奇偶判断就可以了。
代码：

from collections import Counter


class Solution:
    """
    @param s: the given string
    @return: if a permutation of the string could form a palindrome
    """

    def canPermutePalindrome(self, s):
        '''
            Given s = "code", return False.
    Given s = "aab", return True.
    Given s = "carerac", return True.
        '''
        arr = Counter(s).values()  # 每个字母的个数
        return sum(map(lambda c: 1 if c % 2 == 1 else 0, arr)) < 2

数据分割

链接：http://lintcode.com/zh-cn/problem/data-segmentation/
描述：给出一个字符串 str,你需要按顺序提取出该字符串的符号和单词。
样例
给出 str = "(hi (i am)bye)"，返回 ["(","hi","(","i","am",")","bye",")"]。

解释：
将符号和单词分割。
给出 str = "#ok yes"，返回 ["#","ok","yes"]。

解释：
将符号和单词分割。
给出 str = "##s"，返回 ["#","#","s"]。

解释：
将符号和单词分割。

解析： 一个一个的遍历，遇到字母时，累加。遇到符号时，判断是不是空格，如果是空格，怎么处理，如果是其他符号，该怎么处理。

class Solution:
    """
    @param str: The input string
    @return: The answer
    """

    def dataSegmentation(self, string):
        res = []
        curChars = ""
        for char in string:
            if char.isalpha():
                curChars += char
            else:
                if curChars:
                    res.append(curChars)
                    curChars = ""
                if char!=" ":
                    res.append(char)

        if curChars:
            res.append(curChars)
        return res

重排

链接：http://lintcode.com/zh-cn/problem/rearrange/
描述： 给一列数组要求重排，必须所有偶数位上的数都小于所有奇数位上的数。同时，偶数位上的数也按照升序排序，奇数位上的也按照升序排序。
样例：
给出array = [-1,0,1,-1,5,10], 返回 [-1,1,-1,5,0,10]。
解释：
[[-1,1,-1,5,0,10]满足条件。

给出array = [2,0,1,-1,5,10], 返回 [-1,2,0,5,1,10]。
解释：
[-1,2,0,5,1,10]满足条件。

解析：数组的长度是奇数时，会出现多出一个数的情况，注意处理。
代码：

from math import ceil


class Solution:
    """
    @param nums: the num arrays
    @return: the num arrays after rearranging
    """

    def rearrange(self, nums):
        # Write your code here
        # 如果nums的长度为奇数怎么办，为偶数怎么办
        nums.sort()
        left = nums[:ceil(len(nums) / 2)]
        right = nums[ceil(len(nums) / 2):]

        res = []
        while right:
            res.append(left.pop(0))
            res.append(right.pop(0))
        if left:  # 如果nums长度为奇数的时候，会剩下一个数
            res.append(left[0])
        return res

螺旋矩阵

链接：http://lintcode.com/zh-cn/problem/spiral-array/
描述：给出整数 n, 返回一个大小为 n * n 的螺旋矩阵

样例
给出 n = 3
则螺旋矩阵为:

[
[1,2,3]
[8,9,4]
[7,6,5]
]
给出 n = 5
则螺旋矩阵为:

[
[1,2,3,4,5]
[16,17,18,19,6]
[15,24,25,20,7]
[14,23,22,21,8]
[13,12,11,10,9]
]
解析：一层一层的从外往里推，每一层有四个方向，从左到右，从上到下，从右到左，从下到上。
代码：

class Solution:
    """
    @param n: a Integer
    @return: a spiral array
    """

    def spiralArray(self, n):
        res = [[0 for i in range(n)] for j in range(n)]
        count, rowIndex1, rowIndex2, colIndex1, colIndex2, rowNum = 1, 0, n - 1, n - 1, 0, n
        while rowNum >= 1:
            for i in range(colIndex2, colIndex1 + 1):
                res[rowIndex1][i] = count
                count += 1
            rowIndex1 += 1

            for i in range(rowIndex1, rowIndex2 + 1):
                res[i][colIndex1] = count
                count += 1
            colIndex1 -= 1

            for i in range(colIndex1, colIndex2 - 1, -1):
                res[rowIndex2][i] = count
                count += 1
            rowIndex2 -= 1

            for i in range(rowIndex2, rowIndex1 - 1, -1):
                res[i][colIndex2] = count
                count += 1
            colIndex2 += 1

            rowNum -= 2
        return res

Palindromic Substrings

链接： http://lintcode.com/zh-cn/problem/palindromic-substrings/
描述：Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

样例
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

使用暴力枚举法，没想到通过了。
代码：

class Solution:
    """
    @param str: s string
    @return: return an integer, denote the number of the palindromic substrings
    """

    def countPalindromicSubstrings(self, string):
        # write your code here
        res = 0
        for i in range(0, len(string)):
            for j in range(i + 1, len(string) + 1):
                if string[i:j] == string[i:j][::-1]:
                    res += 1
        return res

查找矩阵

链接： http://lintcode.com/zh-cn/problem/find-elements-in-matrix/
描述： 给一矩阵, 找到矩阵中每一行都出现的元素. 你可以假设矩阵中只有一个满足条件的元素.

样例
给一矩阵:
[
[2,5,3],
[3,2,1],
[1,3,5]
]
返回 3

代码（暴力搜索。。没想到过了）

class Solution:
    """
    @param Matrix: the input
    @return: the element which appears every row
    """

    def FindElements(self, matrix):
        # write your code here
        for i in matrix[0]:
            res = True
            for line in matrix[1:]:
                if i not in line:
                    res = False
                    break
            if res:
                return i

Valid Word Square

题目链接
Given a sequence of words, check whether it forms a valid word square.
A sequence of words forms a valid word square if the k^th row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

Given
[
"abcd",
"bnrt",
"crmy",
"dtye"
]
return true

Explanation:
The first row and first column both read "abcd".
The second row and second column both read "bnrt".
The third row and third column both read "crmy".
The fourth row and fourth column both read "dtye".

Therefore, it is a valid word square.

代码:

class Solution:
    """
    @param words: a list of string
    @return: a boolean
    """

    def validWordSquare(self, words):
        # Write your code here
        try:
            for i in range(0, len(words[0])):
                for j in range(i, len(words[0])):
                    if words[i][j] != words[j][i]:
                        return False
            return True
        except:
            return False

Kth Prime Number

http://lintcode.com/zh-cn/problem/kth-prime-number/
描述： 给出质数n，输出它是第几个质数。
代码：

class Solution:
    """
    @param n: the number
    @return: the rank of the number
    """

    def kthPrime(self, n):
        # write your code here

        import math

        def isPrime(n):
            if n <= 1:
                return False
            for i in range(2, int(math.sqrt(n)) + 1):
                if n % i == 0:
                    return False
            return True

        res = [2]
        start = 3

        while res[-1]!=n:
            if isPrime(start):
                res.append(start)
            start += 2

        return len(res)

找到映射序列

http://lintcode.com/zh-cn/problem/find-anagram-mappings/
样例
给定A =[12, 28, 46, 32, 50]和B =[50, 12, 32, 46, 28]，返回[1, 4, 3, 2, 0]。

解释:
P[0] = 1，因为A的第0个元素出现在B[1]， P[1] = 4，因为A的第一个元素出现在B[4]，以此类推。

class Solution:
    """
    @param A: lists A
    @param B: lists B
    @return: the index mapping
    """
    def anagramMappings(self, A, B):
        # Write your code here
        return list(map(lambda c:B.index(c), A))

相反的顺序存储

http://lintcode.com/zh-cn/problem/reverse-order-storage/
描述：给出一个链表，并将链表的值以in reverse order存储到数组中。

注意事项
您不能change原始链表的结构。

样例
给定1 -> 2 -> 3 -> null，返回[3,2,1]。
代码

class Solution:
    """
    @param head: the given linked list
    @return: the array that store the values in reverse order
    """

    def reverseStore(self, head):
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res[::-1]

滑动窗口内数的和

class Solution:
    """
    @param nums: a list of integers.
    @param k: length of window.
    @return: the sum of the element inside the window at each moving.
    """

    def winSum(self, nums, k):
        # write your code here
        if not nums:
            return []
        start = sum(nums[:k])
        res = [start]
        for i in range(1, len(nums) - k + 1):
            start = start + (nums[i + k - 1] - nums[i - 1])
            res.append(start)
        return res