1 .山脈數組的巔峰索引

信息

我們把符合下列屬性的數組 A 稱作山脈：

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]
給定一個確定為山脈的數組，返回任何滿足 A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] 的 i 的值。

示例 1：

輸入：[0,1,0]
輸出：1
示例 2：

輸入：[0,2,1,0]
輸出：1

提示：

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定義的山脈

答案

class Solution(object):def peakIndexInMountainArray(self, A):""":type A: List[int]:rtype: int"""return A.index(max(A))

2.兩個數組的交集

信息

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4]
說明:

輸出結果中的每個元素一定是唯一的。
我們可以不考慮輸出結果的順序。

答案

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""dic = {}p=[]for num in nums1:if num not in dic:dic[num] = 0for num in nums2:if num in dic:p.append(num)del dic[num]return p

3. 二分查找

信息

有序的數組nums:

答案

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left ,right = 0, len(nums)-1while left <= right:mid=(left + right)/2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1               return -1

4 .在數組中是否存在兩個數，使其和等于target

信息

給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等于目標數。

函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。

說明:

返回的下標值（index1 和 index2）不是從零開始的。
你可以假設每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。
示例:

輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標數 9 。因此 index1 = 1, index2 = 2 。

答案

class Solution(object):def twoSum(self, numbers, target):""":type numbers: List[int]:type target: int:rtype: List[int]"""low,high = 0,len(numbers)-1while(low < high):if (numbers[low] + numbers[high] == target):return [low+1, high+1]elif numbers[low] + numbers[high] <target:low = low + 1else:high = high - 1

5.搜索插入位置

信息

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。

你可以假設數組中無重復元素。

示例 1:

輸入: [1,3,5,6], 5
輸出: 2
示例 2:

輸入: [1,3,5,6], 2
輸出: 1
示例 3:

輸入: [1,3,5,6], 7
輸出: 4
示例 4:

輸入: [1,3,5,6], 0
輸出: 0

答案

class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""low,high = 0,len(nums)while low <high:mid = low + (low+high)//2if nums[mid] > target:high=midelif nums[mid] <target:low=mid+1else:return midreturn low

6. 找到兩個數組的交集

信息

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：

輸出結果中每個元素出現的次數，應與元素在兩個數組中出現的次數一致。
我們可以不考慮輸出結果的順序。
進階:

如果給定的數組已經排好序呢？你將如何優化你的算法？
如果 nums1 的大小比 nums2 小很多，哪種方法更優？
如果 nums2 的元素存儲在磁盤上，磁盤內存是有限的，并且你不能一次加載所有的元素到內存中，你該怎么辦？