657. 机器人能否返回原点
- 思路
- example
- 计数
R - L == 0 and U - D == 0 (分别判断）
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def judgeCircle(self, moves: str) -> bool:
n = len(moves)
R, L, U, D = 0, 0, 0, 0
for i in range(n):
if moves[i] == 'U':
U += 1
elif moves[i] == 'D':
D += 1
elif moves[i] == 'R':
R += 1
elif moves[i] == 'L':
L += 1
if U-D == 0 and R-L == 0:
return True
else:
return False
- 模拟
class Solution:
def judgeCircle(self, moves: str) -> bool:
x, y = 0, 0 # current position
for i in range(len(moves)):
if (moves[i] == 'U'):
y += 1
if (moves[i] == 'D'):
y -= 1
if (moves[i] == 'L'):
x += 1
if (moves[i] == 'R'):
x -= 1
return x == 0 and y == 0
31. 下一个排列
- 思路
- example
- 找规律
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
- 两步
- 倒序遍历，找到index i, j 使得nums[j] > nums[i]
- i+1到末尾 排序
- 要求原地修改
- 复杂度. 时间：
, 空间:
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(nums, left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
n = len(nums)
for i in range(n-1, -1, -1):
for j in range(n-1, i, -1):
if nums[j] > nums[i]:
nums[i], nums[j] = nums[j], nums[i]
reverse(nums, i+1, n-1)
return
reverse(nums, 0, n-1)
- time: O(n) 两遍扫描
将左边较小数与右边较大数 交换
较小数尽量靠右，较大数尽量靠左
交换后，把原来较小数位置之后的按升序排列
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(nums, left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
n = len(nums)
i = n - 2
while i >= 0:
if nums[i] < nums[i+1]:
break
else:
i -= 1
if i >= 0: # i could be -1
j = n - 1
while j > i:
if nums[i] < nums[j]:
nums[i], nums[j] = nums[j], nums[i]
break
else:
j -= 1
reverse(nums, i+1, n-1)
463. 岛屿的周长
-
思路
- example
-
遍历，判断
复杂度. 时间：O(mn), 空间: O(1)
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
total, adjacent = 0, 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
total += 1
if j > 0 and grid[i][j-1] == 1: # 左边
adjacent += 1
if i > 0 and grid[i-1][j] == 1: # 上边
adjacent += 1
return 4 * total - 2 * adjacent
