日常算法练习(一) Leetcode

前言

算法作为编程基本能力的体现，虽然日常工作很少使用到算法，但是面试大厂往往都会包含这一部分，因此，作为平时的基础积累，决定创建算法练习模块进行练习和总结。找一个像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]