Leetcode zunxiang 19
数组/字符串
624. 数组列表中的最大距离
class Solution:
def maxDistance(self, arrays: List[List[int]]) -> int:
ans = 0
mn, mx = inf, -inf
for a in arrays:
ans = max(ans, a[-1] - mn, mx - a[0])
mn = min(mn, a[0])
mx = max(mx, a[-1])
return ans
可以用递推的思路理解
280. 摆动排序
给你一个的整数数组 nums, 将该数组重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]...
输入数组总是有一个有效的答案。
示例 1:
示例 2:
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 104- 输入的
nums保证至少有一个答案。
进阶：你能在 O(n) 时间复杂度下解决这个问题吗？
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
nums.sort()
for i in range(1, len(nums) - 1, 2):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
贪心做法（需要仔细观察过程）：
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
for i in range(len(nums) - 1):
if ((i % 2 == 0 and nums[i] > nums[i + 1]) or
(i % 2 == 1 and nums[i] < nums[i + 1])):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
1056. 易混淆数
给定一个数字 N，当它满足以下条件的时候返回 true：
原数字旋转 180° 以后可以得到新的数字。
如 0, 1, 6, 8, 9 旋转 180° 以后，得到了新的数字 0, 1, 9, 8, 6 。
2, 3, 4, 5, 7 旋转 180° 后，得到的不是数字。
易混淆数 (confusing number) 在旋转180°以后，可以得到和原来不同的数，且新数字的每一位都是有效的。
示例 1：
示例 2：
示例 3：
示例 4：
提示：
0 <= N <= 10^9- 可以忽略掉旋转后得到的前导零，例如，如果我们旋转后得到
0008那么该数字就是8。'
翻转是旋转的意思！！！
class Solution:
def confusingNumber(self, n: int) -> bool:
num = []
num_map = {'6': '9', '9': '6'}
for i in str(n):
if int(i) in [6, 9]:
num.append(num_map[i])
elif int(i) in [2, 3, 4, 5, 7]:
return False
else:
num.append(i)
if int("".join(reversed(num))) == n:
return False
return True