wenjin1997/leetcode

Leetcode刷题笔记

1.两数之和/Two Sum

题目描述

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

题解思路

两层遍历，先固定循环指标i,指标i遍历整个数组，再选取循环指标j，指标j从i+1遍历到数组最后，如果指标i和指标j所对应的数字相加为目标值target，则返回下标，否则继续遍历。
代码：two_sum.py

7.整数反转/Reverse Integer

题目描述

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
注意：假设我们的环境只能存储得下32位的有符号整数，则其数值范围为[−2^31^,2^31^−1]。请根据这个假设，如果反转后整数溢出，那么就返回0。

题解思路

分非负数和负数两种情况，先进行反转，先对绝对值转化，转化为为字符串后进行字符串反转,再转化为整数，反转后判断是否溢出，溢出则返回0.
代码：reverse_integer.py

字符串切片及翻转

>>> a = '0123456'
>>> a[1:5]
'1234'

a[1:5]表示的是对字符串a进行切片，取第1位到第四位，注意这里不包含最后一位，也就是第5位元素。

>>> a = '0123456'
>>> a[1:5:2]
'13'

a[1:5:2]表示对第1~5位切片，步长为2。

>>> a = '0123456'
>>> a[::-1]
'6543210'

a[::-1]表示的是对字符串a从头到尾进行切片，步长为-1，由此也就实现了字符串的翻转。

13.罗马数字转整数/Roman to Integer

题解思路

此题方法是用字典，在字典中，键值分为两种，一种是单字符，如'I'，另一种是双字符，如'IV'。接着是将所给的字符串与字典中的键值匹配，优先匹配双字符，再匹配单字符。
在具体实现时，遍历一遍所给字符串，优先判断是否匹配到双字符，如果匹配到双字符，则下一次遍历的指标需要+2，否则则是匹配到单字符，遍历指标+1就够了。
代码：roman_to_integer.py

14.最长公共前缀/Longest Common Element

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。

题解思路

步1：如果所给列表为空，返回空字符串。
步2：遍历整个列表，找到字符串长度最小的元素。目的是防止后续循环中超过字符串的长度。
步3：两层循环，外层是取指标i在最小字符串的长度的范围内，内层是遍历整个列表，比较列表中每个字符串的第i个字符与最小长度字符串的第i个字符，如果循环结束后都一致，则加到目标返回字符串后。
步4：循环结束后，返回目标字符串。
代码：longest_common_element.py

169.多数元素/Majority Element

题目描述

给定一个大小为n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

排序法

将数组中的元素按递增或递减方式排序，根据题中已知条件，多数元素在数组中出现次数大于⌊n/2⌋的元素，因此排序后⌊n/2⌋下标的元素是多数元素。注：官方解题方法
代码：majority_element.py