一起刷Leetcode第一篇，数组和字典的妙用

HuangWeiAI

发布于 2020-07-27 15:00:09

3610

发布于 2020-07-27 15:00:09

文章被收录于专栏：浊酒清味浊酒清味

引言

LeetCode作为一种资源，不得不说，是迄今为止用来改进面试式算法问题最有效的工具。 LeetCode收录了许多互联网公司的算法题目，被称为刷题神器。它扫遍全球，囊括中外，成为大家面试算法工程师以及程序员相关工作必刷的题库。

我们这个系列是刷Leetcode的经典题目，通过算法分析和知识总结来和大家分享如何在实际中运用Python。希望可以和大家一起进步和成长。

知识点总览

1、列表相关知识

2、字典相关知识

3、if语句以及for循环

4、数据结构：栈

两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出
和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。
但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法

根据题目描述，我们可以想到一个最简单的解题方式是用两个循环，但是需要两个循环“错开”，比如说第一个循环下标为a；第二个下表为b；那么b要大于a，以此来保证不重复利用元素：

class Solution(object): # my first solution
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for a in range(len(nums)):
            for b in range(a+1,len(nums)):
                if nums[a] + nums[b] == target:
                    output = [a,b]
                    return output
                    break

当然我们还有更多的解题思路，比如只用一次循环，然后借助Python中的字典在循环的过程记录下数值以及对应的索引，从而加速算法：

class Solution1(object): # best solution
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dct = {}
        for i, n in enumerate(nums):
            if target - n in dct:
                return [dct[target - n], i]
            dct[n] = i

注意字典存储的方式将数字存在key中，而将数字对应的索引存在value中。

原题链接：https://leetcode-cn.com/problems/two-sum/

有效的括号

题目描述

给定一个只包含字符'('，')'，'{'，'}'，'['和']'的字符串，
确定输入字符串是否有效。

输入字符串在以下情况下有效:开括号必须由相同类型的括号关闭。
左括号必须按正确的顺序关闭。
注意，空字符串也被认为是有效的。

示例1:

输入:“()”
输出:真

示例2:
输入:“()(){}”
输出:真

示例3:
输入:“()”
输出:假

示例4:
输入:“(())”
输出:假

示例5:
输入:“{[]}”
输出:真

解法

对于这道题，大家如果学过数据结构就知道可以用“栈”来解决。在Python中我们可以字典来模拟这个栈：

class Solution(object): # my first solution
    def twoSum(self, s):
        """
        :type s: str
        :rtype: bool
        """
        socre = {'(':1,')':-1,'{':2,'}':-2,'[':3,']':-3 }
        shed = []
        for a_str in s:
            if len(shed)>0:
                if socre[a_str] == -socre[shed[len(shed)-1]]:
                    shed.pop(len(shed)-1)                          
                else:
                    shed.append(a_str)
            else:
                shed.append(a_str)
        if len(shed) == 0:
            return True
        else:
            return False

原题链接： https://leetcode.com/problems/valid-parentheses/description/

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-05-29，如有侵权请联系 cloudcommunity@tencent.com 删除

python