leetcode 每日5题

1、Two Sum 【 difficulty:Easy 】

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].

解题思路

1、将设定一个字典类型（Hash table），存一项的差值及原始下标，如2 存储为 7 ：0
2、遍历次数组，将符合条件数据进行返回；

源码如下：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        data={}
        for i,num in enumerate(nums):
            if num in data.keys():
                print(i,data[num])
            else:
                data[target-num]=i

执行结果如下：

 Run Code Result:
 Your input
 [3,2,4]6
 Your answer
 [1,2]
 Expected answer
 [1,2]
 Show Diff
 Runtime: 53 ms

2、Add Two Numbers 【 difficulty:Medium 】

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.

 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 Output: 7 -> 0 -> 8

解题思路

1、对单链表的考察
建立一个单链表模块，其主要性质如下：

# Definition for singly-linked list.
class ListNode(object): #定义单链表单个模块
    def __init__(self, x):
        self.val = x
        self.next = None

p=ListNode(1)
p.next=ListNode(2)
print(p.val,p.next.val,p.next.next)

### result ###

1 2 None

其解题源码如下：

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        if l1==None or l2==None: #判断l1、l2是否存在
            return l1,l2
        carry = 0
        root = n = ListNode(0)
        while l1 or l2 or carry:
            v1 = v2 = 0
            if l1:
                v1 = l1.val
                l1 = l1.next
            if l2:
                v2 = l2.val
                l2 = l2.next
            carry, val = divmod(v1+v2+carry, 10)  
            #divmod 返回一个数组（取整数，余数）
            n.next = ListNode(val)
            n = n.next
        return root.next

3. Longest Substring Without Repeating Characters

【 difficulty:Medium 】

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

 Examples:

 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.

解题思路

采用数据结构：对HashMap[字典结构]进行构造，时间复杂度为o(n)

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        data = {}  # [length,str]
        start=0
        maxlen=0
        for i,char in enumerate(s):
            if char in data:
                start = data[char] + 1
            else:
                maxlen = max(maxlen, i - start+1)
                
            data[char]=i

        return(maxlen)

4. Median of Two Sorted Arrays

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //归并排序
        
        int i=0,j=0,k=0,len=nums1.length+nums2.length;
        int addlist[]=new int[len];
        while((i<nums1.length)&&(j<nums2.length)){
            if(nums1[i]>nums2[j]){
                addlist[k]=nums2[j];
                k++;
                j++;
            }
    
            else{
                addlist[k]=nums1[i];
                k++;
                i++;
            }
        }
        while(j<nums2.length)
        {

            addlist[k]=nums2[j];
                k++;
                j++;
        }
        while(i<nums1.length)
        
        {
             addlist[k]=nums1[i];
                k++;
                i++;
        }
        
        if(len%2==0){
            return (addlist[len/2-1]+addlist[len/2])/2.0;
        }
        else
            return addlist[len/2];
     
    }
}
// 采用归并排序方法，时间复杂度为0（m+n），空间复杂度为0（m+n）
-----
//第二种采用 分治法，进行解决
package Merror;

//分治法，找到第 k/2-1大 ，然后返回数值；
        /* 试想一下，当要找两者的中间值，只需将两者的中间值作比较，若a/2>b/2，则代表 中值一定在 b/2-b 和 0-a/2之间，否则相反；
        故可以采用迭代方法进行解决；
      对于基偶性，可以取巧，不用进行判断；
      例如偶数可以巧用  int l = (m + n + 1) / 2;
                                     int r = (m + n + 2) / 2;
      分别取两次值，然后取平均值即可；
         */
class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
    }

    public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
        if (aStart > A.length - 1) return B[bStart + k - 1];
        if (bStart > B.length - 1) return A[aStart + k - 1];
        if (k == 1) return Math.min(A[aStart], B[bStart]);

        int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
        if (aStart + k / 2 - 1 < A.length) aMid = A[aStart + k / 2 - 1];
        if (bStart + k / 2 - 1 < B.length) bMid = B[bStart + k / 2 - 1];

        if (aMid < bMid)
            return getkth(A, aStart + k / 2, B, bStart, k - k / 2);// Check: aRight + bLeft
        else
            return getkth(A, aStart, B, bStart + k / 2, k - k / 2);// Check: bRight + aLeft
    }
}

5、 Majority Element

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start,maxth=1,nums[0]
        for i in range(1,len(nums)):
            if start==0:
                start=1
                maxth=nums[i]
            elif maxth==nums[i]:
                start+=1
            else:
                start-=1
        return maxth