leetcode简单题 day3
- 【198】打家劫舍——动态规划
- 【206】反转链表——链表
- 【226】翻转二叉树——二叉树
- 【234】回文链表——链表
- 【283】移动零
第198题，打家劫舍
计划偷窃沿街的房屋，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
- 输入：[2, 7, 9, 3, 2, 6,1]
- 2 9 2 1
- 2 9 6 √
- 2 3 6
- 2 4 1
- 2 2 1
- 7 3 6
- 7 2 1
- 7 6
解答：动态规划
计算一个rob list，保存截止到第i家时最高的偷窃金额
- 从第三家开始：面对第i家，如果偷——num i + f i-2；如果不偷——f i-1，max做出权衡
- 如果<=2家：max
- 如果没有：return 0
## 动态规划
def rob(nums):
n = len(nums)
if n == 0 :
return 0
elif n <= 2:
return max(nums)
else:
amount = [0] * n
amount[0] = nums[0]
amount[1] = max(nums[0], nums[1])
for i in range(2, n):
amount[i] = max(amount[i - 2] + nums[i], amount[i-1])
print(amount)
return amount.pop()
rob([])
rob([3, 1])
rob([2, 1, 1, 2])
rob([2, 7, 9, 3, 2, 6, 1])
0
3
[2, 2, 3, 4]
4
[2, 7, 11, 11, 13, 17, 17]
17
第206题，翻转链表
- 输入: 1->2->3->4->5->NULL
- 输出: 5->4->3->2->1->NULL
解答：栈
# 解答
def reverseList(head):
if (head == None) or (head.next == None):
return head
node = head
node_list = []
# 顺序遍历
while node:
node_list.append(node)
node = node.next
n = len(node_list)
# 倒序设置next
for i in range(1, n):
node_list[n-i].next = node_list[n-1-i]
node_list[0].next = None
return node_list.pop()
# 测试：
# 定义链表
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5
node5,reverseList(node1)
(<__main__.ListNode at 0x1026fbfd0>, <__main__.ListNode at 0x1026fbfd0>)
第226题，翻转二叉树
解答：简单递归
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def invertTree(self, root: TreeNode) -> TreeNode:
# 停止条件
if root == None:
return None
left_child = root.left
right_child = root.right
root.left = self.invertTree(right_child)
root.right = self.invertTree(left_child)
return root
第234题，回文链表
- 输入: 1->2->2->1
- 输出: true
直白解法
def isPalindrome(head):
node = head
nodelist = []
while node:
nodelist.append(node)
node = node.next
result = True
while (len(nodelist)>=2) and result:
first = nodelist.pop(0)
last = nodelist.pop()
if not first.val == last.val:
result = False
#if len(nodelist) > 0 :
# result = False
return result
第283题，移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
直白解法
#### 要求：必须在原数组上操作，不能拷贝额外的数组。
nums = [1,3,12,0,0,4,5,12]
n = len(nums)
for i in range(n):
if nums[i] == 0 and i< n-1:
for j in range(i+1, n):
if nums[j] != 0:
break
nums[i] = nums[j]
nums[j] = 0
print(nums)
[1, 3, 12, 4, 5, 12, 0, 0]
参考题解：利用pop和append
nums = [1,3,12,0,0,4,5,12]
n = len(nums)
zero_num = 0
for i in range(n):
idx = i - zero_num
if nums[idx] == 0:
nums.pop(idx)
nums.append(0)
zero_num += 1
print(nums)
0
0
[1, 3, 12, 4, 5, 12, 0, 0]