LeetCode

LeetCode

1.Two Sum

Q:Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路:建立字典,key为值,val为值所对应位置

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
tag = {}
for i in range(len(nums)):
if nums[i] in tag:
return[tag[nums[i]],i]
else:
tag[target-nums[i]]=i

2.Add Two Numbers

Q:You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路:很简单

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
takeover = 0
root = n = ListNode(0)
while l1 or l2 or takeover:
if l1:
takeover += l1.val
l1 = l1.next
if l2:
takeover += l2.val
l2 = l2.next
takeover, val = divmod(takeover, 10)
# 以下两行可以写成
# n.next = n = ListNode(val)
n.next = ListNode(val)
n = n.next
return root.next

3.Longest Substring Without Repeating Characters

Q:Given a string, find the length of the longest substring without repeating characters.

Example:

1
2
3
4
5
Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路:建立字典key为值,val为该值最后一次出现的位置,用指针pre指向每次寻找的子串的开头位置

注意:自己思路是对的,但是错在没考虑嵌套重复如 abcddoua 遍历到第二个d时候重复pre指向第二个d 而遍历到第二个a时pre指向第一个a后的b,显然错的(即pre应该始终在字典回溯值之前,pre只能向后移动)

Code

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLongestSubstringonglen(s):
usedchar = {}
maxlen = 0
pre = 0
for i in range(len(s)):
if s[i] in usedchar and pre <= usedchar[s[i]]:
pre = usedchar[s[i]] + 1
else:
maxlen = max(maxlen, i-pre+1)
usedchar[s[i]] = i
return maxlen

5. Longest Palindromic Substring

Q:Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

1
2
3
4
5
Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

思路:

①for遍历选中心元素,找齐所有中心元素(第一个while 向后 找出所有与所选中心元素重复的元素)

② l r 指示回文边界,向两遍扩展

注意:

①l r 始终指向有效边界(闭区间,考虑边界值仍然是回文区域)

②注意边界情况判断,如第一个while循环判定条件有两个,应该把边界判断放在前面,要不会出现index越界

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def longestPalindrome(s):
if len(s) <= 2:
return s
maxlen = real_l = real_r = 0
for i in range(len(s) - 1):
l, r, pos = i, i, i+1
while ( pos <= len(s) - 1) and s[r] == s[pos]:
r = pos
pos += 1
while (l >= 1 and r < (len(s) - 1)) and s[l - 1] == s[r + 1]:
l -= 1
r += 1
if r - l + 1 > maxlen:
maxlen = r - l + 1
real_l = l
real_r = r
return s[real_l:real_r+1]

7. Reverse Integer

Q:Given a 32-bit signed integer, reverse digits of an integer.

Example:

1
2
3
4
5
6
Input: 123
Output: 321
Input: -123
Output: -321
Input: 120
Output: 21

思路:

①flag表示符号判断正数1负数-1

②将int转为字符串形式,[::-1]表示字符串反转

③bit_length表示位数的判断

注意:

注意对大数的判断

Code

1
2
3
4
def reverse(x):
flag = (x>0)-(x<0)
val = flag*int(str(abs(x))[::-1])
return val*(val.bit_length()<32)

8. String to Integer (atoi)

Q:Implement atoi to convert a string to an integer.

Example:

1
2


思路:此题太乱没做,总结答案

  1. str.strip()用于移除首位指定字符串

  2. str.isdigit()判断字符是否是数值

  3. ord()将字符转换为ASCII码 chr()将ASCII码转为字符如ord(‘a’)

    -> 97 chr(97) -> ‘a’4. 字符串跟数值问题注意overflow问题,这里是有符号函数所以max=231-1 min=-231

注意:

注意对大数的判断

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def myAtoi(self, s):
"""
:type str: str
:rtype: int
"""
###better to do strip before sanity check (although 8ms slower):

if len(s) == 0: return 0
ls = list(s.strip())

sign = -1 if ls[0] == '-' else 1
if ls[0] in ['-', '+']: del ls[0]
ret, i = 0, 0
while i < len(ls) and ls[i].isdigit():
ret = ret * 10 + ord(ls[i]) - ord('0')
i += 1
return max(-2 ** 31, min(sign * ret, 2 ** 31 - 1))

9. Palindrome Number

Q:Determine whether an integer is a palindrome. Do this without extra space.

Example:

1
2


思路:

1.负数不是回文数、非零且末位为零不是回文数

2.用数字一半部分来比较避免了翻转数字overflow问题(赞)

注意:

注意对大数的处理(用数字一半部分作比较)

Code

1
2
3
4
5
6
7
8
9
10
11
12
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0 or (x % 10 == 0 and x != 0):
return False
res = 0
while x > res:
res = res * 10 + x % 10
x = x // 10
return (x == res or x == res // 10)

11.Container With Most Water

Q:Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Example:

1
2


思路:分析此题可以得到一个解题基础:最终得到的两块挡板左挡板L和右挡板R,L左边的所有挡板一定短于L,R右边的所有挡板一定短于R。据此,可以从轴两遍开始向内遍历,每次记录最值,并且下次从较短的挡板继续向内遍历。

注意:

注意对python 中用while True: if XX: break 来代替do while

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def maxArea( height):
"""
:type height: List[int]
:rtype: int
"""
l = 0
r = len(height) - 1
l_h = height[l]
r_h = height[r]
val = maxval = min(l_h, r_h) * (r - l)
while (l < r):
if l_h <= r_h:
while True:
l += 1
if height[l] > l_h or l >= r:
if r > l:
l_h = height[l]
break
elif l_h > r_h:
while True:
r -= 1
if height[r] > r_h or l >= r:
if r > l:
r_h = height[r]
break
val = min(l_h, r_h) * (r - l)
if val > maxval:
maxval = val
return maxval

14.Longest Common Prefix

Q:Write a function to find the longest common prefix string amongst an array of strings.

Example:

1
找到字符串们的最长前缀

思路:关于zip()以及zip(* )的用法

前者相当于压缩到一个list中,后者相当于分开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a=[1,2,3]
b=[4,5,6,7]
c=[8,9,10,11,12]
zz=zip(a,b,c)
print(zz)

x,y,z=zip(*zz)
print(x)
print(y)
print(z)

输出:
[(1, 4, 8), (2, 5, 9), (3, 6, 10)]
(1, 2, 3)
(4, 5, 6)
(8, 9, 10)

Code

1
2
3
4
5
6
7
8
9
10
11
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ''
for i, group in enumerate(zip(*strs)):
if len(set(group)) != 1:
return strs[0][:i]
return min(strs)

15.3 Sum

Q:Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

思路:开头 排序 为了跳过重复元素(用dup记录上一元素)遍历一次用twosum函数返回(twosum函数也要去重)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums = sorted(nums)
result = []
dup = -999
for i in range(len(nums)-1):
if nums[i] != dup:
result.extend(self.twosum(nums[i],nums[i+1:],nums[i]*-1))
dup = nums[i]
return result
def twosum(self,p,arr,val):
box = set()
threesum = []
for i in range(len(arr)):
if (val-arr[i] in box):
temp = sorted([p,arr[i],val-arr[i]])
if temp not in threesum:
threesum.append(temp)
else:
box.add(arr[i])
return threesum

16.3 Sum Closest

Q:Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路:排序后根据大小查找

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
close = nums[0]+nums[1]+nums[2]
for i in range(len(nums)-1):
j = i+1
k = len(nums)-1
while j<k:
sum = nums[i]+nums[j]+nums[k]
if sum == target:
return sum
if abs(target-sum) < abs(target-close):
close = sum
if sum < target:
j += 1
elif sum > target:
k -= 1
return close

17.Letter Combinations of a Phone Numbert

Q:Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Example:

1
2
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

思路:递归思想 字符串拼接用 +

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
mapping = {'0': ' ', '1': '', '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl'
, '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
if len(digits) == 0:
return []
if len(digits) == 1:
return list(mapping[digits[0]])
pre_comb = self.letterCombinations(digits[:-1])
last = mapping[digits[-1]]
return [s + v for s in pre_comb for v in last]

18.4 Sum

Q:Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

思路:列表之间的拼接用 ‘+’先两层嵌套for循环将所有两两组合之和求出来,再用twosum思想

去重

保证每个元素只添加一次(通过变量保存下标而不是值)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
dic = {}
result = []
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
twosum = nums[i] + nums[j]
if target - twosum in dic:
for two in range(len(dic[target - twosum])):
thisfour = sorted([nums[i], nums[j]] +
[nums[dic[target - twosum][two][0]], nums[dic[target - twosum][two][1]]])
# and前条件用于去重;and后条件用于去除元素是否重复利用
if thisfour not in result and len(set([i, j]) | set(dic[target - twosum][two])) == 4:
result.append(thisfour)
if twosum not in dic:
dic[twosum] = [[i, j]]
else:
dic[twosum].append([i, j])
return result

19.Remove Nth Node From End of List

Q:Given a linked list, remove the nth node from the end of list and return its head.

Note:
Given n will always be valid.
Try to do this in one pass.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

思路:构造一个长度为n的滑窗,滑到最后注意判断如果删除了第一个元素(此时post.next = null)应返回head.next

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
pre = head
post = head
for i in range(n):
post = post.next
# 注意这一步,如果删除的是head,直接返回head.next
if not post:
return head.next
while post.next:
pre = pre.next
post = post.next
pre.next = pre.next.next
return head

20. Valid Parentheses

Q:Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not..

Example:

1
2


思路:not valid 只有三种情况,找准这三种情况的特点注意一手对ord()的应用

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for i in range(len(s)):
if s[i] in ['(','{','[']:
stack = stack + [s[i]]
else:
if len(stack)==0: # 右括号比左括号多的情况
return False
if ord(s[i])-ord(stack[-1])!= 1 and ord(s[i])-ord(stack[-1])!= 2: #左右括号不对称的情况
return False
else:
stack = stack[:-1]
if len(stack) == 0:
return True
else: # 左括号比右括号多的情况
return False

21. Merge Two Sorted Lists

Q:Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

思路:

1.正常思路,用and终止while,l1 或 l2 的尾巴可以一并加上

2.递归思想找准结束条件,链表一个一个拼接

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 第一种做法
def mergeTwoLists( l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
head = p = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l1 or l2 #加上小尾巴
return head.next
# 递归做法
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2

22.Generate Parentheses

Q:Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

Example:

1
2
3
4
5
6
7
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路:

不带返回值的递归(用于添加或者修改),递归生成每个str

Left right 分别为左右括号的计数器

Init_str为目前生成的字符串

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution22:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if not n:
return []
left, right, init_str = n, n, ''
result = []
self.generate(left,right,init_str,result)
return result
def generate(self,left,right,init_str,result):
if not left and not right:
result.append(init_str)
return
if left:
self.generate(left-1,right,init_str+'(',result)
#left < right 为添加右括号条件
if right and left < right:
self.generate(left,right-1,init_str+')',result)

24.wap Nodes in Pairs

Q:Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Example:

1
2
input:1->2->3->4
output:2->1->4->3.

思路:基本操作,但是遇到return head报错,return init.next就正确,没找到原因

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
init = ListNode(0)
pre = init
pre.next = head
while pre.next and pre.next.next:
p = pre.next
post = p.next
p.next = post.next
post.next = p
pre.next = post
if not p.next:
break
else:
pre = p
p = p.next
post = p.next
return init.next

24.wap Nodes in Pairs

Q:Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Example:

1
2
input:1->2->3->4
output:2->1->4->3.

思路:基本操作,但是遇到return head报错,return init.next就正确,没找到原因

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
init = ListNode(0)
pre = init
pre.next = head
while pre.next and pre.next.next:
p = pre.next
post = p.next
p.next = post.next
post.next = p
pre.next = post
if not p.next:
break
else:
pre = p
p = p.next
post = p.next
return init.next

26.Remove Duplicates from Sorted Array

Q:Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

1
2
3
4
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

思路:简单题,在数组内删除重复元素,两个指针write、read,修改时候

A[write + 1] = A[read]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution26(object):
def removeDuplicates(self, A):
"""
:type nums: List[int]
:rtype: int
"""
if not A:
return 0
if len(A) == 1:
return 1
write = 0
read = 1
while read < len(A):
if A[write] != A[read]:
# 修改重复元素的方法
A[write + 1] = A[read]
write += 1
read += 1
else:
read += 1
A = A[:write + 1]
return len(A)

27.Remove Element

Q:Given an array and a value, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

1
2
3
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

思路:简单的双指针

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution27:
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
if not nums:
return 0
read = write =0
while read < len(nums):
if nums[read] != val:
nums[write] = nums[read]
write += 1
read += 1
nums = nums[:write]
return len(nums)

29.Divide Two Integers

Q:Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Example:

1
2


思路:不会位运算,看了discussion此题两个while循环,第一个为结束条件,第二个循环每次减去除数的1、2、4、8……倍,结束第二个循环继续从一倍开始。减完回到第一个循环的判定条件判断是否需要再进行第二个while,相当于指数高效的记录倍数

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution29:
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
positive = (dividend < 0) is (divisor < 0)
dividend, divisor = abs(dividend), abs(divisor)
res = 0
while dividend >= divisor:
temp, i = divisor, 1
while dividend >= temp:
dividend -= temp
res += i
temp <<= 1
i <<= 1
if not positive:
res = -res
return min(max(-2 ** 31,res), 2**31-1)

31.Next Permutation

Q:Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

从这几个数组合中找到下一个比他大的数

Example:

1
2
3
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

思路:较简单,尽可能更改最后几位,并且从后往前如果一直是递增则就是这几个数的最大排列如4321,从后找到第一个非递增的数字p(如1245763中的5),然后将此数字与之后数字中 大于它且最接近于它 的数字(6)交换,交换后将该位置之后的数字升序排列(1246357)该题要求在原数组中修改,因此我把之后按升序拍了的数组建立一个临时数组temp_list,用for循环写入原数组

list.sort() 和 sorted(list)的区别

1
2
3
4
5
6
7
8
a = [3,2,1]
list.sort()就地修改无返回值 sorted(list)返回新列表,对所有可迭代对象均有效
print(a.sort()) -> None
print(sorted(a)) -> [1,2,3]
a.sort() print(a) -> [1,2,3]
#对于切片列表:
a[1:].sort() print(a) ->[3,2,1] 无效
print(sorted(a[1:])) ->[1,2]

注意:

①找与p交换的数字时从后往前找可以避免index越界问题

②考虑有重复数字问题

③while遍历时候考虑左右边界问题(如while p and 条件 ->此为不超过左边界)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution31:
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if not nums:
return None
p = len(nums) - 1
# while p用以阻止左边界越界
while p and nums[p-1] >= nums[p]:
p -= 1
if p == 0:
nums.sort()
return None
else:
p = p - 1
post = len(nums) - 1
# while post用以阻止左边界越界,同时从后往前找防止右边界越界
while post and nums[post]<=nums[p]:
post -= 1
temp = nums[p]
nums[p] = nums[post]
nums[post] = temp
temp_list = sorted(nums[p+1:])
for i in range(p+1,len(nums)):
nums[i] = temp_list[i-p-1]
return None

33.Search in Rotated Sorted Array

Q:Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Example:

1
2


思路:在排序或类排序数组中查找首先想到二分法此题因为不需要考虑重复元素,较为简单,列出所有情况来即可,我的代码比较繁琐,边界值判定条件应该可以统一一下,懒得改了因为最后的6种判定条件互斥,所以用 抑或^ 或者 or 都行分情况讨论如图(类似高中数学题)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution33:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 1 and nums[0] == target:
return 0
left = 0
right = len(nums)-1
while left < right:
mid = (left +right) // 2
if nums[left] == target:
return left
if nums[right] == target:
return right
if nums[mid] == target:
return mid
if (nums[mid]>target and target > nums[right])^(nums[right]>nums[mid] and nums[mid]>target
)^(target>nums[right] and nums[right]>nums[mid]):
right = mid - 1
else:
left = mid + 1
return -1

34.Search for a Range

Q:Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example:

1
2
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

思路:很简单,因为是排序数组,所以先用二分法查找target,在从这个位置往两边扩展

注意:

①类似while pre>0 and nums[pre] == target: 中判断while结束后的pre是否指向target(有可能因为边界条件跳出循环,并且边界仍满足target)来判断pre是否 -1

②第一个while l<=r: 中‘=’存在不构成死循环的原因如果l=r且指向target接下来会return,如果l=r不指向target之后对于mid与target判定仍会跳出循环

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution34:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums or (len(nums)==1 and nums[0] != target):
return [-1,-1]
l = 0
r = len(nums) - 1
if l == r and nums[0]==target:
return [0,0]
while l <= r:
mid = (l+r) // 2
if nums[mid] == target:
pre = post = mid
while pre>0 and nums[pre] == target:
pre -= 1
while post<len(nums)-1 and nums[post] == target:
post += 1
if nums[pre] != target:
pre += 1
if nums[post] != target:
post -= 1
return [pre, post]
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return [-1, -1]

35.Search Insert Position

Q:Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example:

1
2
3
4
5
6
7
8
Input: [1,3,5,6], 5
Output: 2
Input: [1,3,5,6], 2
Output: 1
Input: [1,3,5,6], 7
Output: 4
Input: [1,3,5,6], 0
Output: 0

思路:没什么好说的,排序数列二分查找,注意边界值问题及while中的等号问题while 中 加’=’保证在无target的情况,mid在连续两位中的右边一位

注意:target>max情况

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution35:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums or (len(nums)==1 and nums[0]>=target):
return 0
if len(nums)==1 and nums[0]<target:
return 1
l = 0
r = len(nums)-1
while l <= r: # 加‘=’保证在无target的情况,mid在连续两位中的右边一位
mid = (l + r) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid + 1
else:
r = mid - 1
if nums[mid]>target:
return mid
else: # target>max情况
return mid+1

**

0%