前言
算法作为编程基本能力的体现，虽然日常工作很少使用到算法，但是面试大厂往往都会包含这一部分，因此，作为平时的基础积累，决定创建算法练习模块进行练习和总结。找一个像Leetcode，codeforces提供在线练习算法的网站，看题，思考，编码，验证，再查看别人的思路，总结。
题目: 941. Valid Mountain Array
题目大意：
给出一个数组，判断是否为山峰数组，如下：
条件：
1.数组A长度要大于等于3
2.存在0<i<A.length-1,使得：
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]
Example 1:
Input: [2,1]
Output: false
Example 2:
Input: [3,5,5]
Output: false
Example 3:
Input: [0,3,2,1]
Output: true
题目解析：
给出一个数组是否为山峰数组（两边低，中间高），需要分别在数组头尾两边向中间进行检索出最大值
最终判断这两个最大值是否相等
时间复杂度为o(n)
class Solution:
def validMountainArray(self, A):
"""
:type A: List[int]
:rtype: bool
"""
if len(A) < 3: return False
start, end, length = 0, len(A) - 1, len(A)
while start + 1 < length and A[start] < A[start + 1]:
start += 1
while end > 0 and A[end] < A[end - 1]:
end -= 1
return 0 < start == end < length - 1
题目: 942. DI String Match
题目链接
题目大意：
给出只包含'D'和'I'的字符串S，D代表降序，I代表升序，按照S每个字符代表的升降顺序来返回[0,1...N]符合该顺序的数据，如下：
条件：
1.1 <= S.length <= 10000
2.S只包含D和I的任意字符串
Example 1:
Input: "IDID"
Output: [0,4,1,3,2]
Example 2:
Input: "III"
Output: [0,1,2,3]
Example 3:
Input: "DDI"
Output: [3,2,0,1]
题目解析：
按照指定顺序返回数组，必须考虑：
1.确定数组长度为字符串S的长度加1
2.建立一个空数组res
2.两个数字之间的有效排序：
a.升序，取最大数字的元素依次插入res数组中
b.降序，取最小数字的元素依次插入res数组中
c.剩下的直接插入尾部
核心思想：当为"D"，把最大数据插入数组，为"I"，把最小数据插入数组
时间复杂度为o(n)
class Solution:
def diStringMatch(self, S):
"""
:type S: str
:rtype: List[int]
"""
ls = list(range(len(S) + 1))
res = []
for i in S:
if i == 'D':
res.append(ls.pop())
else:
res.append(ls.pop(0))
return res + ls
class Solution1:
def diStringMatch(self, S):
"""
:type S: str
:rtype: List[int]
"""
l, r, res = 0, len(S), []
for i in S:
if i == "D":
res.append(r)
r -= 1
else:
res.append(l)
l += 1
return res + [l]
题目: 1. Two Sum
题目链接
题目大意：
给出一个整型数组，找出两个数字之和为给定target值对应的下标index，如下：
条件：
给出的的target只有两个唯一的数字之和
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题目解析：
1.找个两个值的之和等于某个值，需要遍历数组
2.使用反向思维，先把target减去第一个元素差放在hash表，再判断剩下的元素是否与hash表中的值相等
核心思想：使用hash表，使用键值对进行存储数组值(key)和下标值(value)
时间复杂度为o(n)
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) <= 0: return False
map = {}
for i in range(0, len(nums)):
if nums[i] not in map:
map[target - nums[i]] = i
else:
return [map[nums[i]], i]
网友评论