[Q1] 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:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]. Solution
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
idx = {}
for l,x in enumerate(nums):
if target - x in idx:
return [idx[target-x], l]
idx[x]=l
问题：可能存在两个数相同的情况，而index（）函数对于重复元素只可返回第一个下标。
解决：使用字典
[Q2] 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:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807. Solutions:
https://leetcode.com/problems/add-two-numbers/discuss/1016/Clear-python-code-straight-forward
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
carry = 0
l = l3 = ListNode(0)
while l1 or l2 or carry:
cur1 = cur2 = 0 # avoid when l1 goes to end before l2
if l1:
cur1 = l1.val # current value
l1 = l1.next # go to next node
if l2:
cur2 = l2.val
l2 = l2.next
carry,cur3 = divmod(cur1+cur2+carry,10)
l3.next = ListNode(cur3)
l3 = l3.next
return l.next
[Q3] Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is"abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is"b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: 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. Solution:
if s[j]s[j] have a duplicate in the range [i, j)[i,j) with index j'j′, we don't need to increase ii little by little. We can skip all the elements in the range [i, j'][i,j′] and let ii to be j' + 1j′+1 directly.
创建左节点i和右节点j，扫描窗口，若s【i:j】内有与s【j】相同的数，且该数位置为j`，则直接将i跳至j`，而j+1
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
i,j = 0,1
maxL,L = 0,0 # window length
if(len(s)<=1):
return len(s)
while i<len(s) and j<len(s):
if s[j] not in s[i:j]:
j = j+1
else:
i = i+1
maxL = max(maxL,j-i)
return maxL