1.[String to Integer]http://www.lintcode.com/en/problem/string-to-integer/
solution:注意符号位（即首位）
class Solution:
"""
@param str: A string
@return: An integer
"""
def stringToInteger(self, str):
# write your code here
sig = 1
start = 0
if str[0] == '-':
sig = -1
start = 1
num = 0
for idx in range(start, len(str)):
num = num * 10 + ord(str[idx]) - ord('0')
return num * sig
2.[Implement Queue by Linked List]http://www.lintcode.com/en/problem/implement-queue-by-linked-list/
solutin:画图，dummy
"""
class ListNode:
def __int__(self, val):
self.val = val
self.next = None
"""
class MyQueue:
def __init__(self):
# do intializaiton if neccessary
self.dummy = ListNode(-1)
self.tail = self.dummy
"""
@param: item: An integer
@return: nothing
"""
def enqueue(self, item):
# write your code here
node = ListNode(item)
self.tail.next = node
self.tail = node
"""
@return: An integer
"""
def dequeue(self):
# write your code here
item = self.dummy.next.val
self.dummy.next = self.dummy.next.next
if self.dummy.next is None:
self.tail = self.dummy
return item
def empty(self):
return self.dummy.next is None
3.[Valid Parentheses]https://leetcode.com/problems/valid-parentheses/description/
solution:见注释，用栈来做
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
# 压栈
for c in s:
if c in ['(', '[', '{']:
stack.append(c)
else:
# 栈需非空
if len(stack) == 0:
return False
# 判断栈顶是否匹配
if stack[-1] == '(' and c != ')':
return False
if stack[-1] == '[' and c != ']':
return False
if stack[-1] == '{' and c != '}':
return False
# 弹栈
stack.pop()
return len(stack) == 0
4.[Rotate String]http://www.lintcode.com/en/problem/rotate-string/
solution:见注释，注意不是Reverse String
class Solution:
"""
@param str: An array of char
@param offset: An integer
@return: nothing
"""
def rotateString(self, str, offset):
"""
# write your code here
# abcdefgabcdefg
# start = len(str) - offset(这里的start指的是坐标，下同)
# end = start + len(str) - 1 = len(str) - offset + len(str) -1
# = 2len(str) - offset - 1
# str * 2[start : end + 1]
# str * 2[len(str) - offset: 2len(str) - offset ]
"""
if offset > len(str) and len(str) > 0:
offset = offset % len(str)
temp = (str * 2)[len(str) - offset: 2 * len(str) - offset ]
# reference，需要逐步修改
for idx in range(len(temp)):
str[idx] = temp[idx]
5.[Romve Element]https://leetcode.com/problems/remove-element/description/
solution:双指针，最左边开始的元素如果等于目标值，与最右边的元素互换，并且将最右边的指针减一。如果不等于，就把左指针加一。最后返回的结果为右指针加一
@ 容易理解的Java版本
class Solution {
public int removeElement(int[] nums, int val) {
int i = 0;
int j = nums.length - 1;
while (i <= j) {
if (nums[i] == val) {
nums[i] = nums[j];
j--;
} else {
i++;
}
}
return j + 1;
}
}
@ Python版本
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
j = len(nums) - 1
for i in range(len(nums) - 1, -1, -1):
if nums[i] == val:
nums[i], nums[j] = nums[j], nums[i]
j -= 1
return j + 1
6.递归一：所有叶子节点值的和
[Binary Tree Leaf Sum]http://www.lintcode.com/en/problem/binary-tree-leaf-sum/
solution:拆分为左右子树。另外此题也可用DFS来做
class Solution:
"""
@param: root: the root of the binary tree
@return: An integer
"""
def leafSum(self, root):
# write your code here
if root is None:
return 0
if root.left is None and root.right is None:
return root.val
return self.leafSum(root.left) + self.leafSum(root.right)
7.递归二：根节点到所有叶子节点路径
[Binary Tree Paths]https://leetcode.com/problems/binary-tree-paths/description/
solution：递归，注意边界条件还有循环方式
class Solution:
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if root is None:
return []
if root.left is None and root.right is None:
return [str(root.val)]
return [str(root.val) + '->' + l for l in self.binaryTreePaths(root.left) + self.binaryTreePaths(root.right)]
8.递归三：判断两颗树是不是完全同构
[Identical Binary Tree]http://www.lintcode.com/en/problem/identical-binary-tree/#
solution:根节点相同，左右子树相同
class Solution:
"""
@param: a: the root of binary tree a.
@param: b: the root of binary tree b.
@return: true if they are identical, or false.
"""
def isIdentical(self, a, b):
# write your code here
if a is None and b is None:
return True
if a is None and b is not None:
return False
if a is not None and b is None:
return False
return a.val == b.val and self.isIdentical(a.left, b.left) and \
self.isIdentical(a.right, b.right)
网友评论