LintCode_新手必编程50题（4-6阶段）解答与分析

阶段4 字符串与循环

1. 转换字符串到整数（容易版）
   emmmm，有点简单粗暴，python自带int()读取字符串

def stringToInteger(self, target):
	# write your code here
    return int(target)

2. 大小写转换II
   join
   chr(ord©
   2.3.5都是一个题型， 仔细品味～

def lowercaseToUppercase2(self, str):
    # write your code here
	return "".join(chr(ord(c)-32) if "a" <= c <= "z" else c for c in str)

3. 转换成小写字母

def toLowerCase(self, str):
	# Write your code here
    return "".join(chr(ord(c)+32) if "A" <= c <= "Z" else c for c in str)

4. 两字符串和

def SumofTwoStrings(self, A, B):
	# write your code here
    if not A: #如果A为空就输出B
        return B 
    if not B:
        return A
    if not A and not B:
        return ""

    ans = ""
	if len(A) < len(B):
        A, B = B, A  # 长的字符串记为A
	offset = len(A) - len(B)
    ans = A[:offset]
    for i in range(len(B)):
        ans += str(int(A[offset + i]) + int(B[i]))
    return ans

5. 首字母大写

def capitalizesFirst(self, s):
 	# Write your code here
	n = len(s)
	s1 = list(s)
	if s1[0] >= 'a' and s1[0] <= 'z':
		s1[0] = chr(ord(s1[0]) - 32)
	for i in range(1, n):
	if s1[i-1] == ' ' and s1[i] != " ":
		s1[i] = chr(ord(s1[i]) - 32)
	return "".join(s1)

6. 回文数
   这里也许有人会熟悉，阶段3中也有一题相似，但是注意那题要求是“返回非负整数n的***二进制表示形式***是否是回文”，而本题是***数本身是否为回文数***，因此本题不需要二进制转化～～～

def isPalindrome(self, num):
    # write your code here
    return str(num) == str(num)[::-1]

7. 最长单词

def longestWords(self, dictionary):
    # write your code here
    maxLength = max(len(w) for w in dictionary)
    return [w for w in dictionary if len(w) == maxLength]

8. 最后一个单词的长度

def lengthOfLastWord(self, s):
	# write your code here
    return len(s.strip().split(' ')[-1])

9. 最大字母

def key(self, c):
	if c >= 'a' and c <= 'z':
    	return ord(c) - ord('a')
    else:
    	return 26 + ord(c) - ord('A')
    	
def largestLetter(self, s):
	# write your code here
    num = [0] * 60
    for i in s:
    	k = self.key(i)
    	num[k] += 1
    	ans = "NO";
    for i in range(25,-1,-1):
    	if num[i] and num[i + 26]:
	        ans = chr(ord('A')+i);
            break;
	return ans;

11. 字符串查找
    给出两个方法，由于本题时间复杂度给的宽裕，第一种简单粗暴匹配为O(MN)

def strStr(self, source, target):
        #获取两个字符串的长度
        sourceLen = len(source)
        targetLen = len(target)
        #注意特判，若target长度为0则答案为0
        if targetLen==0:
            return 0

        #若target长度大于source，则不可能匹配
        if targetLen>sourceLen:
            return -1

        for i in range(sourceLen - targetLen + 1):
            #k表示比对时source中所指向的字符
            k = i
            for j in range(targetLen):
                if source[k]==target[j]:
                    #最后一个字符匹配完成，输出答案
                    if j==targetLen-1:
                        return i
                    k+=1
                #其中一个字符无法匹配，直接退出做下一次循环
                else:
                    break
        return -1

第二种方法是KMP算法思想
在KMP算法中，对于每一个模式串，会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数，因此为O(n)。

def strStr(self, source, target):
	# Write your code here
    return_tem = -1
    if len(target) > len(source):
        return return_tem
    if target == '':
        return 0
    tem = 0
    for source_index in range(len(source) + 1):
        if len(source) - source_index < len(target):
            return -1
        for index in range(tem,len(target)):
            source_item = source[source_index + index]
            target_item = target[index]
            if source_item != target_item:
                tem = 0
                break
            else:
                tem = tem + 1
        if tem == len(target)
            return_tem = source_index
            break
    return return_tem

def kmpSearch(self, source, target):
'''
KMP算法：
1. 若source[i] == source[j]匹配成功,或j=-1 i++ j++
2. 若source[i] != source[j]匹配失败, j = next[j]
3. next数组通过pmt获得
4. pmt的时间复杂度为O(n),遍历source的复杂度业务O(n)，所以KMP的时间复杂度O(n)
'''
	source_length = len(source)
    target_length = len(target)
    nexts = self.pwt_next(target)   
    if len(target) > len(source):
        return -1
    if target == '':
        return 0
    i,j = 0,0
    while i<source_length and j < target_length:
        if j == -1 or source[i] == target[j]:
            i += 1
            j += 1
        else:
            j = nexts[j] 
    if j != target_length:
    	return -1
    return i - j 

def pwt_next(self,target):
'''
KMP算法关键是获取next数组
next数组中的值，是字符串的前缀集合与后缀集合的交集中最长元素的长度。
'''	
	nexts = [0 for i in range(len(target)+1)]
    nexts[0] = -1
    # i循环计数 j
    i,j = 1,-1
    while i < len(target):
    	if j == -1 or target[i] == target[j]:
        	i += 1
            j += 1
            nexts[i] = j
        else:
            j = nexts[j]
    return nexts

12. 旋转字符串
    同样地，本题与阶段3翻转数组类似，但⚠️注意那题是***逆序输出***，本题是***（原地旋转）原始顺序输出***！

def rotateString(self, s, offset):
	# write your code here
    if len(s) > 0:
    	offset = offset % len(s)    
    temp = (s + s)[len(s) - offset : 2 * len(s) - offset]
    for i in range(len(temp)):
    	s[i] = temp[i]

阶段5 栈与队列

1. 二阶阶乘

def doubleFactorial(self, n):
	# Write your code here
	if n <= 2:
		return n
   	return n * self.doubleFactorial(n-2)

2. 实现栈

def __init__(self):
	self.stack = []
	
def push(self, x):
	# write your code here
	self.stack.append(x)
	
"""
@return: nothing
"""
def pop(self):
	# write your code here
    return self.stack.pop()

"""
@return: An integer
"""
def top(self):
	# write your code here
    return self.stack[-1]
 
"""
@return: True if the stack is empty
"""
def isEmpty(self):
	# write your code here 
    if len(self.stack) == 0:
    	return True
    else:
        return False

3. 队列维护

class LinkedNode: # 先定义LinkedNode
    def __init__(self, val):
        self.val = val
        self.next = None
        
class MyQueue:
    """
    @param: item: An integer
    @return: nothing
    """
    def __init__(self):
        self.head = LinkedNode(-1) # 虚拟节点
        self.h = self.head # 头节点
    
    def enqueue(self, item):
        node = LinkedNode(item)
        self.head.next = node
        self.head = node

    """
    @return: An integer
    """
    def dequeue(self):
        val = self.h.next.val
        self.h = self.h.next
        return val

4. 有效的括号序列
   这题思路较巧妙，细品～～

def isValidParentheses(self, s):
	# write your code here
    stack = []
    for c in s: #若为括号左侧，便将括号右侧进栈
   		if c == '(' :
            stack.append(')')
        if c == '[' :
            stack.append(']')
        if c == '{' :
            stack.append('}') 
        # 若为括号右侧且其不在栈顶，便为不合法的     
        if c == ')' or c == ']' or c == '}':
           if not stack or c != stack.pop():
                return False                
    return not stack

5. 小括号匹配
   ⚠️注意与上一题的区别！
   该问题取决于左边括号的数量一直>=0， 不然说明有个右括号没有左括号去匹配。 然后最后左括号数量必须是0， 说明左括号数量正好匹配。

def matchParentheses(self, string):
    # write your code here
	matched = 0
	for parenthese in string:
		if parenthese == '(':
            matched += 1
        else:
            matched -= 1
        if matched < 0:
           return False
    return matched == 0 #表示

阶段6 简单递归

1. 斐波那契数列

def fibonacci(self, n):
        # write your code here
        if n<= 1:
          return 0
        first, second = 0, 1
        for i in range(2, n):
          first, second = second, first+second
        return second

2. 二叉树的后序遍历
   后序遍历是左右根。 因此孩子一定要在栈的顶部方向，根节点一定要压在栈的底部方向。
   和中序遍历主要不同是1) 父节点和右孩子出入栈顺序不一样。需要先让右孩子入栈出栈完，父节点才能出栈 2) 添加了一个标记，用于标记这个节点处理过没有。

def stack_left_line(self, node, stack):
	while node:
		stack.append([node, False])
        node = node.left
    
def postorderTraversal(self, root):
	# write your code here
	if not root:
        return []
      
    res = []    
    stack=[]    
    self.stack_left_line(root, stack)

    while stack:
    	node, judged = stack[-1]
        if not judged and node.right:
        	stack[-1][-1] = True
        	self.stack_left_line(node.right, stack)
        else:        
        	res.append(stack.pop()[0].val)
        	
	return res 

3. 二叉树的中序遍历

def inorderTraversal(self, root):
	# write your code here
	if not root:
    	return []
       
	result = []
    stack = []
        
    while root:
    	stack.append(root) 
        root = root.left # 1.添加所有最左边节点到栈
        
    while stack:
        curNode = stack.pop() # 2.pop stack然后添加到结果
        result.append(curNode.val)
            
    if curNode.right: # 3.查找当前node的右边节点是否为空，
        curNode = curNode.right
        while curNode:
        	stack.append(curNode)
            curNode = curNode.left
    
    return result

4. 二叉树的前序遍历
   有点类似BFS的写法，只不过是用stack而不是queue。

def preorderTraversal(self, root):
	# write your code here
    if root is None:
		return []
    stack = [root] # 1.把root入栈
    result = []
    while stack:
    	node = stack.pop() # 2.出栈的元素同时放进结果队列 
        result.append(node.val)
        if node.right: 
        	stack.append(node.right) # 3.先把右儿子节点入栈
        if node.left:
            stack.append(node.left) # 4.再把左儿子节点入栈，这
   return result