LeetCode 刷题总结（二）， 使用Python 实现。该篇题目类型主要是： list, linkedList 还有简单的 tree。

Add Two Numbers

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.

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

Tips: 加法的过程，使用 % 和 整除进行求解，使用linkedList 进行存储。 https://leetcode.com/problems/add-two-numbers/

 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

# Definition for singly-linked list.
# 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
        """

        dummy = cur = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry%10)
            cur = cur.next
            carry //= 10
        return dummy.next

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Tips: 可以使用”两指针“ 方法进行求解，前后两指针相差 N步数。

 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

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

class Solution:
    # 得到list 整个长度，然后去掉指定的结点
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        _len =0
        cur =head
        while cur:
            cur = cur.next
            _len +=1
        if _len ==n: return head.next
        
        cnt =0
        cur =head
        while cur:
            cnt +=1
            if(cnt ==_len -n):
                cur.next =cur.next.next
                break
            cur =cur.next

        return head

c++ 实现

for 循环是可以遍历任何可迭代对象，不止 int i ; i <n; i++

 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len =0;
        for(ListNode * cur = head ; cur ; cur = cur ->next)
            len ++;
        if (len ==n) return head ->next;
        int cnt =0;
        for(ListNode * cur =head; cur ; cur = cur->next)
        {
            cnt ++;
            // 注意remove 某个结点的操作
            if (cnt ==len- n)
            {
                cur ->next =cur->next ->next;
                break;
            }
        }
        return head;
    }
};

Merge Two Sorted Lists

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.

Tips: 归并操作中的”并“ 操作。注意在并操作的时候，while 是与的操作。

 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

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

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy =ListNode(-1)
        head =dummy
        while l1 and l2:
            if l1.val < l2.val:
                head.next =l1
                head =head.next
                l1 =l1.next
            else:
                head.next =l2
                head =head.next
                l2 =l2.next
        if l1:
            head.next =l1
        if l2:
            head.next =l2
        return dummy.next

c++ 实现

 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
34
35
36
37

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 这个是归并排序中的并 操作
        ListNode* dummy =new ListNode(-1);
        ListNode* head =dummy;
        while(l1 && l2)
        {
            if(l1 -> val < l2->val)
            {
                head->next =l1;
                l1 =l1->next;
                head =head->next;
            }        
            else 
            {
                head->next =l2;
                l2 =l2->next;
                head =head->next;
            }
        }
        if(l1)
            head->next =l1;
        if(l2)
            head->next =l2;
        return dummy->next;
        
    }
};

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list’s nodes, only nodes itself may be changed.

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

Tips: 常见的类型，使用三个指针修改指向。经常创建 dummy指针，如果head 可能被改变的话。

dummy 的作用：头结点可能被删除（为了处理这个特殊情况），所以使用dummy 结点。

 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
        ListNode* dummy =new ListNode(0);
        
        dummy ->next = head;
        ListNode* cur =dummy;
        while (cur)
        {
            ListNode * first =cur ->next;
            if (first ==NULL) break;
            ListNode * second =first ->next;
            if( second ==NULL) break;
            // 是按照先进先出的顺序 进行出场的
            cur ->next =second;
            first ->next =second ->next;
            second ->next =first;
            cur =first ;
        }
        return dummy->next;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy =ListNode(-1)
        dummy.next = head
        cur =dummy
        while cur :
            first =cur.next;
            if not first : break
            second =first.next;
            if not second : break
                
            cur.next =second
            first.next =second.next
            second.next  =first
            cur = first
        return dummy.next

Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Tips: 这个是属于循环，字符串处理。

 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 Solution(object):
    
    def doCountAndSay(self, string):
        char =string[0]
        
        num =0
        result =""
        for c in string:
            if char ==c:
                num +=1
            else:
                result += (str(num)+ char)
                char =c
                num =1
        result += (str(num) +char)
        return result
    
    def countAndSay(self, n):
        if 0 ==n:
            return ""
        elif 1== n:
            return "1"
        
        result ='1'
        for i in range(1, n):
            result =self.doCountAndSay(result)
        
        return result

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Tips: 算法比较巧妙，左右两边进行遍历找出”累计“最高点，在O(N) 时间内完成。能装的水，取决于左右两边( neighbor) 的小值- height[i]。

https://leetcode.com/problems/trapping-rain-water/

 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

class Solution(object):

    def trap(self, height):
        if not height:
            return 0
        len_h =len(height)

        leftmax=[0]* len_h
        max_h=0
        for i in range(len_h):
            if height[i] >max_h:
                max_h =height[i]
            leftmax[i] =max_h
        
        rightmax =[0] *len_h
        max_h =0
        for i in range(len_h-1, -1, -1):
            if height[i]> max_h:
                max_h =height[i]
            rightmax[i] =max_h
        
        result =0
        
        for i in range(len_h):
            result += (min(leftmax[i], rightmax[i])- height[i])
        return result

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

使用dp 的思想求解，dp[i] 表示以第$i$个数字为结尾的最大的子数组的和。 那么转移方程是 $dp[i] =max( dp[i-1] + arr[i], arr[i])$ ，对当期的数字分成两个部分，要么是加上当前的数字，要么是不加当前的数字。

（后验推断使用dp，但是没有什么根据）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res =0;
        vector<int> dp(nums.size() );
        dp[0] =nums[0];
        for(int i =1; i< nums.size() ; i ++)
        {
            dp[i] =max(dp[i-1] + nums[i], nums[i]);
            res =max(res, dp[i]);
        }      
        return res;
    }
};

python版本

（注意dp 的递推关系，如果上一个dp[i-1] +nums[i] 是比较小的，那么就重新从 nums[i] 处开始了）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return nums
        n =len(nums)
        dp =[0] *( n)
        dp[0] =nums[0]
        res =nums[0]
        for i in range(1,n):
            dp[i] =max(dp[i-1] + nums[i], nums[i]) # 如果不选上一个，那么就是全新的开始了
            res =max(dp[i], res)
        return res

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

遍历一遍，时间复杂度是 $O(n)$。

···python class Solution { public: vector<vector> insert(vector<vector>& intervals, vector& newInterval) { bool flag =false; // newInterval 是否已经被处理了 vector<vector> res; int n =intervals.size(); for(int i =0; i< n; i++) { if(newInterval[1] < intervals[i][0]) { if( !flag) { res.push_back(newInterval); flag =true; } res.push_back(intervals[i]); } else if (newInterval[0] >intervals[i][1] ) res.push_back(intervals[i]); else { newInterval[0] =min(newInterval[0], intervals[i][0]); newInterval[1] =max(newInterval[1], intervals[i][1]); } } if(!flag) res.push_back(newInterval); return res; } }; ···

python 解法

···python class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: res =[] flag =False for interval in intervals: if interval[1] < newInterval[0]: res.append(interval) elif interval[0] > newInterval[1]: if not flag: res.append(newInterval) flag =True else: newInterval[0] =min(newInterval[0], interval[0]) newInterval[1] =max(newInterval[1], interval[1]) if not flag: res.append(newInterval) return res ···

Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Tips： 细节在于k 可能大于 list 的长度。

 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
34
35
36
37

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

class Solution(object):

    def rotateRight(self, head, k):
        
        if k ==0:
            return  head
        if not head:
            return head
        
        # 头指针
        dummy =ListNode(-1)
        dummy.next =head
        p =dummy
        
        count =0
        
        while p.next:
            p =p.next
            count +=1
        # 指向了头指针，连成了一个环，下一步开始找头指针
        p.next =dummy.next
        step =count -(k% count)
        
        for i in range(step):
            p =p.next
        # 找到了头指针，那么下一个就是尾指针
        head =p.next
        p.next =None
        
        return head

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

组合数学， 从网格的左上角到右下角需要 $m+n -2$ 步，向下是 $m-1$ 步，向右是 $n-1$步，因此是一个经典的组合问题，结果是 $(C n-1) (m+n-2)$， 所以时间复杂度是$O(n)$，空间是 $O(1)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    # 这个总的步数是一定的 m+n -1 ，然后下行和右行也是一定的，
    # 所以这个是模拟的“排列组合” 的思想
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m ==0 or n ==0:
            return 1
        
        up =1
        # 这个是分子
        for i in range(m+n-2, n -1, -1):
            up *=i
        
        down =1
        # 这个是分母
        for j in range(1, m):
            down *= j
        return up/down

基于dp 思想，使用python 实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m ==0 or n==0: return 0
        dp =[[0]* n for _ in range(m)]
        dp[0][0] =1
        for i in range(m):
            for j in range(n):
                if i>0 : dp[i][j] += dp[i-1][j]
                if j >0: dp[i][j] += dp[i][j-1]
        return dp[m-1][n-1]

使用dp 思想

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    #define LL long long
    int uniquePaths(int m, int n) {
        if(m ==0 || n ==0) return 0;
        vector<vector<LL >> dp(m, vector<LL>(n, 0));
        dp[0][0] =1;
        for(int i =0; i< m; i++)
        {
            for(int j =0; j<n; j++)
            {
                if(i >0) dp[i][j] += dp[i-1][j];
                if(j >0) dp[i][j] += dp[i][j-1];
            }
        }
        return dp[m-1][n -1];
    }
};

63. Unique Paths II

这种网格题目，常见的有 dfs，bfs 和动态规划等思路，是可以着重往这方面去考虑的。然后dp 分为定义问题，转移方程和初始化三个部分。 $dp[i][j] $ 表示从 $(0, 0)$ 到 $(i,j )$ 所有的路径总数。转移方程， 如果 $ num[i][j] ==0$ 那么 $dp[i][j] = dp[i-1][j] + dp[i][j-1] $, 如果等于1 （障碍物），那么 $dp[i][j] =0 $。初始化 dp[0][0] = 0, 结果是 $dp[m-1][n-1]$。时间和空间复杂度都是 $O(mn)$

c++ 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    #define LL long long
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        if ( !grid.size() || !grid[0].size() ) return 0;
        int n =grid.size() , m =grid[0].size();
        vector<vector<LL>> dp(n, vector<LL>(m, 0));
        dp[0][0] =1;
        for(int i =0; i< n; i++)
            for(int j =0; j< m; j++)
        {
                if(grid[i][j] == 1)
                    dp[i][j] =0;
                else
                {
                    if(i >0) dp[i][j] += dp[i-1][j];
                    if(j >0) dp[i][j] += dp[i][j-1];
                }
        }
        return dp[n-1][m -1];
    }
};

python 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def uniquePathsWithObstacles(self, nums: List[List[int]]) -> int:
        if len(nums) ==0 or len(nums[0]) ==0: return 0
        n , m =len(nums), len(nums[0])
        dp =[[0] * m  for _ in range(n)]
        dp[0][0] =1
        for i in range(n):
            for j in range(m):
                if nums[i][j] ==1:
                    dp[i][j] =0
                else:
                    if i >0:
                        dp[i][j] += dp[i-1][j]
                    if j >0:
                        dp[i][j] += dp[i][j-1]
        return dp[n-1][m-1]

Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Tips: 快排思想， 中间数字1 当做key index，左右两边分别是left，right index。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution(object):
    """
    0, 1, 2 (red, white, blue)
    """
    def sortColors(self, nums):
        # zero and r record the position of "0" and "2" respectively
        index, two, zero = 0, len(nums) - 1, 0
        while index <= two:
            if nums[index] == 0:
                nums[index], nums[zero] = nums[zero], nums[index]
                index += 1;
                zero += 1
            elif nums[index] == 2:
                nums[index], nums[two] = nums[two], nums[index]
                two -= 1
            else:
                index += 1

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Tips: 常规题，经常出现这样的逻辑， if… while ，如果发现有重复的，那么一直就找到不重复为止。

 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

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

class Solution(object):
    """
    就是在删除节点的时候，如果head 节点也得删除，这个时候
    常常创建一个 dummy 结点
    求解的是distinct 的list
    """
    def deleteDuplicates(self, head):
        dummy =pre =ListNode(0)
        
        dummy.next =head
        
        while head and head.next:
            if head.val ==head.next.val:
                while head and head.next and head.val ==head.next.val:
                    head =head.next
                head =head.next
                pre.next =head
            else:
                # 这个更新很有意思， head =head.next, pre.next =head
                pre =pre.next
                head =head.next
        return dummy.next

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Tips: 新建了两个结点，分别连接小于 x 和不小于 x 的结点，最后两个结点相连。 list 是直接进行交换位置，但是linkedList 不是这样的。

 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

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

class Solution(object):
    # 局部排序，不是全局排序
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        small =l1 =ListNode(0)
        great =l2 =ListNode(0)
        while head:
            
            if head.val <x :
                l1.next =head
                l1 =l1.next
            else:
                l2.next =head
                l2 =l2.next
            head =head.next
        # 这个是一个细节， 最后l2 是需要一个none 进行结束标记
        l2.next =None
        l1.next =great.next
        
        return small.next

206. Reverse Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * pre =nullptr;
        ListNode * cur =head;      
        while(cur)
        {
            ListNode * next =cur->next;
            cur ->next =pre;
            pre = cur;
            cur = next;
        }
        return pre ;
    }
};

python实现

 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

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

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 最好命名是有意义的
        pre =None
        cur =head
        
        while cur:
            
            nex =cur.next
            cur.next =pre
            
            pre =cur
            cur =nex
        return pre

Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list.

Tips: 局部进行reverse，找到该节点，然后迭代进行就可以了。

 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

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

class Solution(object):
    # The idea is simple and intuitive: find linkedlist [m, n], reverse it, then connect m with n+1, connect n with m-1
    def reverseBetween(self, head, m, n):
        
        pre =dummy =ListNode(0)
        dummy.next =head
        
        #cur, pre =head, dummy
        
        for _ in range(m-1):
            #cur =cur.next
            pre =pre.next
        cur =pre.next    
        for _ in range(n-m):
            tmp =cur.next
            cur.next =tmp.next
            tmp.next =pre.next
            pre.next =tmp
        
        return dummy.next

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Tips: 从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution(object):
    # 二叉搜索树，当且仅当中序遍历的时候是单调非减的时候。
    # 数学问题
    
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        arr =[0]*(n+1)
        
        arr[0] =1
        for i in range(1, n+1):
            for j in range(1, i+1):
                # 处理的是左右子树的乘积
                arr[i]  += arr[j-1] *arr[i-j]
        
        return arr[-1]

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.

Tips: 虽然这个说是最多一次买入卖出，但是这个价格变化是”连续“的，所以只要是下一个大于上一个就是可以 += profit 中的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
    # 从代码上来看，毫无算法可言
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices or len(prices) ==1:
            return 0
        profit =0
        
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit += prices[i]-prices[i-1]
                
        return profit

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Tips: 可以进行多次买卖。和上面的区别在于 下一个只要不小于上一个就是可以累加的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution(object):
    # 可以多次买卖， 买一次然后卖一次。不能多次买入
    # 这种就如同寻找的是 增序列。
    
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        total =0
        for i in range(1, len(prices)):
            if prices[i]>= prices[i-1]:
                total += prices[i]-prices[i-1]
        
        return total

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity.

Tips： 这种方法很巧妙，如果x-1 not in，那么去 try x+1，然后计数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums =set(nums) # python 中set 是无序的
        best =0
        for num in nums:
            if num -1 not in nums:
                y = num +1
                while y in nums:
                    y +=1
                best =max(best, y -num)
        return best

Candy

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?

Tips: 因为涉及到 neighbors，所以左右两边进行遍历，因为如果ratings 大的话，那么结果一定得大，所以返回的是较大者。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        # 满足第一个条件，at least one candy
        res =len(ratings) *[1]
        
        # left to right, higher then more candies
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                # 这个是严格的 >
                res[i] = res[i-1] +1
        # right to left, higher then more candy, neighbors
        for i in range(len(ratings)-1, 0, -1):
            if ratings[i-1] > ratings[i]:
                res[i-1] =max(res[i-1], res[i] +1)
        
        return sum(res)

Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Tips: 异或的性质

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution(object):
    # 分分钟 异或就出来了
    # integers, -2 -1 0 1 2 这样的数字
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        standard =0
        # 如果正好是其中的 0 出现一次，也是没有关系的， 因为初始化的 0 和 list 中的单数 0 正好匹配，异或操作之后相同为 0
        # 结果上是没有什么问题的
        for num in nums:
            standard = num^ standard
        return standard

Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Tips：这个 three times不能使用 异或，从二进制的角度进行考虑，以二进制的形式，将数字存储起来，如果是出现了 3次，那么 %3 结果就是0，最后只是剩下了 那个出现一次的数字

 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

class Solution(object):
    # 只是出现的一个的single one， 其他的出现三次
    # var |= value is short for var = var | value
    
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        bit = [0] * 32
        for num in nums:
            
            for i in range(32):
                bit[i] += num >> i & 1 # 这个就是从左往右的顺序，先是进行 >> 运算，然后是 & 运算
                # 可以想象这个重复计算比较多，因为每次都需要 num >> i  进行位运算

        res = 0
        for i, val in enumerate(bit):
            # if the single numble is negative,
            # this case should be considered separately , 补码 和原码的转换关系
            if i == 31 and val % 3:
                res = -((1 << 31) - res)
            else:
                res |= (val % 3) * (1 << i) # | 这个是位操作，更加类似不断的取 1 的过程， 然后和该位置的权重相乘
                
        return res

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

Tips：在剑指offer 上是通过 指针操作进行做题，但是使用 defaultdict 基本上就不用出，使用dict 来处理这种关系，最后返回的是根节点、

 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

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""
# 使用dict 有没有感觉在作弊

class Solution(object):
    # 做过这个
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        import ipdb
        dic = collections.defaultdict(lambda: Node(0, None, None)) # 这个就是给定了一个默认的值, 直接初始化dict 中的value 为这个node
        # dict 的本身就是存储一种node 的关系，所以dict[n].val , next, random 可以这样进行操作
        
        dic[None] = None
        n = head
        while n:
            dic[n].val = n.val
            dic[n].next = dic[n.next]
            dic[n].random = dic[n.random]
            n = n.next
        #ipdb.set_trace()    
        return dic[head]

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Tips：快慢两个指针的问题，给了两种方法来实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next : return False;
        fast =head
        slow =head
        while fast and slow:
            fast = fast.next;
            slow =slow.next;
            if fast : fast =fast.next;  # 这样处理快指针走两步
            else: return False
            if fast == slow: return True
        return False

C++ 实现代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if ( !head || ! head->next ) return false;
        ListNode * fast =head, * slow =head;
        while( fast && slow)
        {
            slow = slow ->next;
            fast = fast ->next;
            if( fast) fast  =fast ->next; // 这里体现fast走两步
            else return false;
            if( fast == slow) return true;
        }
        return false;
    }
};

142. Linked List Cycle II

是上一道题目的延续，如果存在环，那么将slow 置为head，然后slow 和fast 以相同的速度 1 走，知道两者相同为止。

 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
34
35

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if ( !head || !head->next)
            return NULL;
        ListNode * fast =head, *slow = head;
        while ( fast && slow)
        {
            fast =fast ->next;
            slow =slow-> next;
            if( fast) fast  = fast->next;
            else return NULL;
            
            if( fast == slow)
            {
                slow =head;
                while ( slow != fast)
                {
                    slow = slow ->next;
                    fast = fast ->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

python 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next : return None
        fast, slow =head,head
        
        while fast and slow:
            fast = fast.next
            slow =slow.next
            if fast: fast =fast.next
            else: return None
            
            if fast == slow:
                slow =head
                while slow != fast:
                    slow =slow.next
                    fast =fast.next
                return fast
        return None

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You may not modify the values in the list’s nodes, only nodes itself may be changed.

Tips： 从中间断开，后半部分翻转，然后和前半部分轮流连接

 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
34
35
36
37
38
39
40
41
42
43

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

class Solution(object):

    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """

        if not head:
            return

        fast, slow = head.next, head

        # first part has the same or one more node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # reverse the send half
        p = slow.next
        slow.next = None
        node = None  # 类似上一个结点， p 是cur 的结点
        while p:
            nex = p.next
            p.next = node
            node = p
            p = nex

        # combine head part and node part
        p = head
        while node:
            tmp = node.next
            node.next = p.next  # 两个 next 指向操作, 需要next 两次
            p.next = node
            p =p.next.next
            
            node = tmp

** Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

Output: 2 Input: K = 1, N = 2 Explanation: Drop the egg from floor 1. If it breaks, we know with certainty that F = 0. Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1. If it didn’t break, then we know with certainty F = 2. Hence, we needed 2 moves in the worst case to know what F is with certainty.

Tips: 可以查看 solution 中的(讲解)[https://leetcode.com/problems/super-egg-drop/]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 初始化
        counts =0
        for num in nums:
            if counts ==0:
                majority =num
                counts =1
            elif majority ==num:
                counts +=1
            else:
                counts -=1
            
        return majority

** Maximum Product Subarray**

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Tips: 在于左右两遍遍历，分别得到 prefix和 suffix 的乘积。这个速度上比较快在于存储了之前的结果。实现的时候利用了 1 or prefix[i-1] 这种技巧。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        prefix =nums
        suffix =prefix[::-1]
        for i in range(1, len(prefix)):
            prefix[i] *= 1 or prefix[i-1]
            suffix[i] *= 1 or suffix[i-1] 
            
        return max(prefix+ suffix)

** Majority Element**

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

Tips: majority 的counts 的总数是大于其他所有counts相加之和的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        majority =None
        counts =0
        
        for num in nums:
            if not majority or counts ==0:
                majority =num
                counts =1
            elif num ==majority:
                counts +=1
            else:
                counts -=1
        return majority

Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Tips： 对于python 而言，是不存在切分字符串算法的，一步操作。小的细节是 k %len(array) 更加合理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # 这个in-place 操作是不需要 return
        k =k%len(nums) # 这个是一个细节吧
        #nums[:] =nums[-k:] +nums[:k+1] 
        nums[:] =nums[-k:] +nums[:-k] 
        # 左边有时候是nums 就行，有时候必须nums[:] 表示index的操作，因为环境的问题
        # 这种 对称的切分真的是比较好看

** Contains Duplicate**

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Tips: 有很多种方法，比如 dictionary or set，这个简单之处最后返回的是 true or false，不是要找出来。

方法一：使用set，根据length判断。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # 想法一，排序之后判断，
        # 想法二：使用dictionary, 在建立的过程中就可以判断，没有必要建立完之后遍历，from collections import Counter
        # 想法三： 使用set，道理和dictionary 基本上是相同的
        
        return len(nums) !=len(set(nums))

方法二：使用dictionary，不需要建完之后再判断。

···python class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """

    dic ={}
    for num in nums:
        if num in dic:
            return True
        else:
            dic[num] =1
    return False

 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

** Move Zeroes **


> Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

> Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Tips: 双指针问题，pre 指向的是0 ，index是遍历的发现如果不是0，那么进行操作

​```python
class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # in-place 操作
        pre = 0 
        for index in range(0, len(nums)):
            if nums[index]:
                if not nums[pre]:
                    nums[index], nums[pre] =nums[pre], nums[index] 
                pre +=1

** Shuffle an Array**

Shuffle a set of numbers without duplicates.

Tips: 使用库函数randomint， 有 shuffle 和reset 两种操作，前者使用randomint 可以得到一个number，后者使用 list 备份。

 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

class Solution(object):

    def __init__(self, nums):
        self.original =nums[:]
        self.nums =nums
        
    def reset(self):
        
        self.nums =self.original[:] # 这个应该 id() 是不同的
        return self.nums
        
    def shuffle(self):
        tmp =self.nums[:]
        
        for i in range(len(self.nums)):
            rand =random.randint(0, len(tmp)-1)
            self.nums[i] =tmp[rand]
            del tmp[rand]
        return self.nums
        

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

** Intersection of Two Arrays II **

Given two arrays, write a function to compute their intersection.

https://leetcode.com/problems/intersection-of-two-arrays-ii/

Tips: 多看看题意，如果想要映射成dictionary，那么result 就是 min(dict1[i], dict1[j]), 两个dictionary 中values 的最小值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        # 存储dict 然后如果都存在，那么选择values 较小者 为好
        # 说一下几种不同的思路

        dic1 =collections.Counter(nums1)
        res =[]

        for num in nums2:
            if dic1[num] >0:
                res += [num]
                dic1[num] -=1
        return res

** Increasing Triplet Subsequence **

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Input: [1,2,3,4,5] Output: true

Tips: 首先学会在python 中表示最大数字(float(‘inf’)), 然后这个技巧相当于选择排序中一次遍历选择最小的那个。代码比较简洁哈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        
        first = second = float('inf')
        for n in nums:
            if n <= first:
                first = n
            elif n <= second:
                second = n
            else:
                return True
        return False

** Product of Array Except Self**

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Tips:左右两遍，这个是一维的还是比较nice，换成 m*n 也是基本的思路吧。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 我记得使用一个数组存储起来中间的结果，然后进行操作的
        
        len_n =len(nums)
        res =[1] *len_n
        
        # from left to right
        for i in range(1, len_n):
            res[i] =res[i-1] * nums[i-1]
        
        tmp =1
        # from right to left
        for i in range(len_n-2, -1, -1):
            tmp *= nums[i+1]
            res[i] *= tmp
        
        return res

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

使用快排的思想，注意时间复杂度的分析。递归时候每层都是$O(n)$，但不是左右两部分都进行递归，所以在每次递归一层平均长度会减半。所以是时间复杂度是 $n + n/2 +n /4 +… +1 =O(n)$。

c++ 解法

 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

class Solution {
public:
    int partition(vector<int> & nums, int l , int r)
    {
        int key =nums[r];
        while(l <r)
        {
            while(l <r && nums[l] >= key) l ++;
            nums[r] =nums[l];
            while(l <r && nums[r] <=key) r --;
            nums[l] =nums[r];
                
        }
        nums[r] =key;
        return l;
        
    }
    int findKthLargest(vector<int>& nums, int k) {
        
        int l =0, r =nums.size() -1;
        
        while (true)
        {
            int pos = partition(nums, l, r);
            
            if( pos ==k -1) return nums[pos];
            else if(pos > k-1) r =pos -1;
            else l = pos +1;
        }
        return -1;
        
    }
};

python解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def partition(self, nums, l, r):
        key =nums[r]
        while l <r:
            while l <r and nums[l] >= key: l +=1
            nums[r] =nums[l]
            while l < r and nums[r] <= key: r -=1
            nums[l] =nums[r]
        nums[r] =key
        return l
        
    def findKthLargest(self, nums: List[int], k: int) -> int:
        l, r =0, len(nums) -1
        while True:
            pos =self.partition(nums, l , r)
            if pos ==k -1: return nums[pos]
            elif pos >k -1: r =pos -1
            else: l =pos +1
        return -1

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

Tips: 需要维持两个stack， 一个是日常的，一个是min_stack, 在push or pop 的过程中需要日常性维护 min_stack .

 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
34
35
36
37
38
39
40
41
42

class MinStack:
    # 难点 最小栈的动态维护
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack =[]
        self.min = []
        
    def push(self, x: int) -> None:
        if not self.min:
            self.min.append(x)
        else:
            # 是可以有冗余的
            if x <= self.min[-1]:
                self.min.append(x)
        self.stack.append(x)
        
    def pop(self) -> None:
        tmp =self.stack.pop()
        if tmp == self.min[-1]:
            self.min.pop()
            
    def top(self) -> int:
        if self.stack:
            return self.stack[-1]
        else:
            return None


    def getMin(self) -> int:
        if self.min:
            return self.min[-1]
        else:
            return None
        
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

** Top K Frequent Elements**

Given a non-empty array of integers, return the k most frequent elements.

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Tips: 如果是使用 dictionary 进行计数，那么直接调用 counter 是一个不错的选择； 下面是超级nice的代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution(object):
    # 一种很简单的方法，就是放到dictionary 中，然后根据values从大到小排序，然后返回相应的keys
    # python 中的 sort() 函数默认是从小到大进行排序的
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        from collections import Counter # 本质上就是一个dictionary
        freq =Counter(nums) # 这个dictionary， 然后访问的时候freq 操作的是键，然后freq[x] 是值
        
        #counters =sorted(counters, key =counters[1], reverse =True)
        uniques=sorted(freq,key=lambda x:freq[x],reverse=True)  # 最后返回是一个list，只是按照value 进行排序，返回的是key的列表
        
        return uniques[:k]

4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of $-2^{28} $ to$ 2^{28} - 1 $ and the result is guaranteed to be at most $2^{31} - 1$.

Tips: 思路和 2 sum 是一样，放到dictionary 中去。defaultdict 和dict 的唯一差别在于前者不用记性 key in dict 的判断。

 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

class Solution(object):
        
    def fourSumCount(self, A, B, C, D):
        
        from collections import defaultdict
        
        length, dic, res =len(A), defaultdict(int), 0
        
        for a in A:
            for b in B:
                dic[a+b] +=1
                """
                if a+b not in dic:
                    dic[a+b] =1
                else:
                    dic[a+b] +=1
                """
        
        for c in C:
            for d in D:
                
                if -(c+d) in dic:
                    res += dic[-(c+d)]
        
        return res

** Sliding Window Maximum **

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Tips: 滑动窗口，然后窗口中的max(). 谁能想得到 python 是擅长处理 list，然后max() 函数就解决了呢

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if nums ==[]:
            return ()
        res =[]
        for i in range(len(nums)-k +1):
            res.append(max(nums[i:i+k]))
        
        return res

** The Skyline Problem**

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Tips: 关键点就是记录： 轮廓上升和轮廓下降的点，分别对应着 left 的上升和 right 的下降。评论区讲解，虽然比较难看懂

https://leetcode.com/problems/the-skyline-problem/

 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
34

from heapq import heappush, heappop

class Solution(object):

    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """

        events =[ (left, -height, right) for left, right, height in buildings]

        events += list((right, 0, 0) for _, right, _ in buildings)

        events.sort()
        # 先是按照left 升序排序，然后是 right 降序排序( 这个就是为什么时候 -right)
        res =[[0, 0]]

        # 最小堆，保存当前最高的轮廓 (-Height, right)， 使用-H 转换成最大堆，R 的作用是记录轮廓的有效长度
        heap =[(0, float('inf'))]
        
        for  left, height, right in events:
            
            # 如果轮廓上升
            if height: 
                heappush(heap, (height, right))
                
            while heap[0][1] <=left:
                heappop(heap)
            
            if res[-1][1] != -heap[0][0]:
                res += [[left, -heap[0][0]]]
        return res[1:]

** Wiggle Sort II **

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Tips: 算法题目被 python 中的lsit 操作给毁了, 可以学习以下 list[::-1], list[::2], 这种是模式化的操作，不是偶然。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        
        #nums.sort()
        #half =len(nums)/2
        #nums[::2], nums[1::2] =nums[:half][::-1], nums[half:][::-1]
        
        nums.sort()
        
        half = len(nums[::2]) # 注意这个是 half 必须是这样写的
        # 这里面倒过来的原因， 前半个永远不大于后半个，所以这样能保证 波动
        nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]

Find Peak Element

A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.

Tips: 二分查找， 如果是两个 if 那么就是两个步骤，如果 if else 那么就是一种选择。给定的条件中相邻的元素是不相同的。找到一个解进行了。。

https://leetcode.com/problems/find-peak-element/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if not nums:
            return -1
        if len(nums) ==1:
            return 0
        left, right =0, len(nums)-1
        
        while left < right:
            
            mid =(left +right) /2
            if nums[mid] > nums[mid+1]:
                right =mid
            elif nums[mid] < nums[mid+1]:
                left =mid +1
        return left

** Find the Duplicate Number**

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Tips: 有两种思路。一种是二分法，一种是两个 pointer 的方法。后者类似linked list 中的操作。好好看看代码， fast =nums[nums[fast]] 这个操作就是 fast =fast.next.next 有木有很神奇的样子。

···python class Solution(object): # 感觉这个从时间和空间复杂度上限制的好多呀，如果满足这两个维度的，一般是先进行排序，O（nlgn） 时间，然后遍历找出重复的数字 # 基本上有两种思路，一种是 index(faster, slower point)， 一种是二分法 # 根据 indics 是有序的，然后使用二分查找 # The array is not sorted - but the indices of the array are sorted - #Insight '''

def findDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    if len(nums) == 0:
        return 0
    low = 0
    high = len(nums)-1
    # 需要访问两个指针
    while low < high:
        mid = low + int((high-low)>>1)
        count = 0
        for x in nums:
            if x <= mid:
                count = count + 1
        if count > mid:
            high = mid
        else:
            low = mid+1
    return low
'''
# 这两种方法的根本依据是  长度为n 包含n+1 个整数，并且只有一个 duplicate
def findDuplicate(self, nums):
    slow = fast = finder = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            while finder != slow:
                finder = nums[finder]
                slow = nums[slow]
            return finder

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

** Count of Smaller Numbers After Self**

> You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

> Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Tips: 这个本身的应用还是挺有意思的。python 中的库函数bisort (binary sort) 了解一下。逆序遍历，找到合适的位置，插进去，然后index 计数。

​```python
class Solution(object):
    # The problem is equal to find each number's inversion count. Actually there are three kinds of solutions: BST, mergeSort, and BITree. While the first two answer's time complexity is O(nlogn), and BITree time comlexity is O( nlog(maximumNum) ).
    # 太难了
    # 两种解法
    '''

    def merge(self,left,right,res):
        i,j=0,0
        new_array=[]
        while i<len(left) and j<len(right):
            if left[i][1]>right[j][1]:
                new_array+=[left[i]]
                res[left[i][0]]+=len(right)-j
                i+=1
            else:
                new_array+=[right[j]]
                j+=1
        new_array+=left[i:]
        new_array+=right[j:]
        return new_array

    def merge_sort(self,nums,res):
        if len(nums)<2:
            return nums
        mid=len(nums)//2
        left=self.merge_sort(nums[:mid],res)
        right=self.merge_sort(nums[mid:],res)
        return self.merge(left,right,res)

    def countSmaller(self, nums):
        res=[0]*len(nums)
        self.merge_sort([(i,num) for i,num in enumerate(nums)],res)
        
        return res
    
    '''
    def countSmaller(self, nums):

        count,sorted=[],[]
        for num in nums[::-1]:
            index=bisect.bisect_left(sorted,num)
            sorted.insert(index,num)
            count+=[index]
        return count[::-1]

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity.

解法是非常巧妙。数组中的数字是遍历常数遍，时间复杂度是 $O(n)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums =set(nums)
        
        best =0
        # 这种方式真的很简洁
        for x in nums:
            if x-1 not in nums:
                y =x+1
                while y in nums:
                    y +=1
                best =max(best, y-x)
        
        return best

** House Robber**

Tips: dp 的思想运用到极致就是这个样子。使用两个变量句可以搞定。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
    """
    f(0) = nums[0]
    f(1) = max(num[0], num[1])
    f(k) = max( f(k-2) + nums[k], f(k-1) )
    """
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # dp 有时候就能这样优化到使用两个变量
        last, now =0, 0
        for num in nums:
            last, now =now, max(last +num, now)
        return now

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Tips: f(i) 表示以 nums[i]为结尾的 longest encreasing subsequence( 第二个for 对比的对象是 f[:i] 使用j 进行遍历 )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    # 求解最值 唯一解都是可以使用这样的方式的哦
    # 不能使用 in 那种骚操作了， 只能踏踏实实的 dp
    
    # 这个版本的dp 没有优化好
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if not nums: return 0
        dp = [1] * len(nums)
        """

        """
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

解法一：动态规划 $O(n^2)$，使用 $dp[i]$ 表示以 $nums[i] $结尾的最长递增子序列的长度，那么递推方程是 $dp[i] =max(dp[j] +1)$， 其中 $1 \leq j<i$， 并且 $nums[j] < nums[i]$。因为 $dp[i]$本身定义的就是前 i 的子序列的最大程度，所以需要遍历之前的所有结果，那么这样的算法复杂度是 $O(n^2)$。空间复杂度是$O(n)$。

c++ 版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() ==0)
            return 0;
        vector<int> dp(nums.size(), 1);
        int res =1;
        for(int i =1; i< nums.size() ; i++)
        {
            for(int j =0; j < i; j ++)
                if(nums[i] > nums[j])
                    dp[i] =max( dp[i], dp[j] +1);
            res =max(res, dp[i]);
        }
        return res;
    }
};

错误解法, 下面这种解法的转移方程就是不正确的。

 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 {
public:
    // dp[i] 表示前i 个字符最长的上升子序列的长度
    // dp[i] = dp[i-1] + 1 if nums[i] > nums[i -1]
    // dp[i] =dp[i-1]
    // 初始化 dp[0] =1
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() ==0) return 0;
        
        int n =nums.size();
        vector<int> dp(n, 0);
        dp[0] =1;
        int res =dp[0];
        
        for(int i =1; i< n; i++)
        {
            if(nums[i] > nums[i-1]) 
                dp[i] =dp[i-1] +1;
            else
                dp[i] =dp[i-1];
            res =max(res, dp[i]);
        }
        return res;
    }
};

解法二： 使用二分查找优化，最后的时间复杂度是 $O(nlogn)$

**Coin Change **

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Tips: dp问题

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

from sys import maxint
class Solution(object):    

        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        '''
        # 这种方法不行
        if len(coins) ==1:
            if amount % coins[0] ==0:
                return amount /coins[0]
            else:
                return -1
        coins.sort(reverse =True)
        res =0
        for i in range(len(coins)):
            res += amount /coins[i]
            amount %= coins[i]
        return res 
   
    # table 作为dp， table[i] 表示前i 个数字使用数量最少的硬币能够 表示
    # 多看几遍就能理解了
    def coinChange(self, coins, amount):
        table = [0]*(amount + 1)
        for i in range(1, amount+1):
            minimum = maxint # 有好几种对于最小值和最大的初始化了
            for j in coins:
                if i >= j and table[i-j] != -1:
                    minimum = min(minimum, table[i-j] + 1)
                table[i] = -1 if minimum == maxint else minimum
        return table[amount]
        '''   
    # python3 不能使用python2,python2 能使用 python3? 
    def coinChange(self, coins, amount):
        table = [0 ] *(amount + 1)
        for i in range(1, amount +1):
            #minimum =maxint
            minimum =float('inf')

            for j in coins:
                if i >= j and table[ i -j] != -1:
                    minimum = min(minimum, table[ i -j] + 1)
                table[i] = -1 if minimum == float('inf') else minimum

        return table[amount]

16. 3Sum Closest

算法思想类似 3Sum, 首先将nums 排序，然后给定 i，初始化 l 和r ，然后枚举 nums[i] + nums[l] + nums[r] == target。算法复杂度是$O(n^2)$。使用c++ 实现如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // 最后的时间复杂度是 $O(n^2)$
        int ans = nums[0] + nums[1] + nums[2];
        sort(nums.begin(), nums.end());
        for(int i =0; i< nums.size(); i++)
        {
            int l = i +1, r =nums.size() -1;
            while (l <r)
            {
                if( abs(nums[i] + nums[l] + nums[r] - target) < abs(ans - target))
                    ans =nums[i] + nums[l] + nums[r];
                
                if( nums[i] + nums[l] + nums[r] == target) 
                    return target;
                else if (nums[i] + nums[l] + nums[r] < target)
                    l +=1;
                else r -=1;
            }
        }
        return ans;
    }
};

455. Assign Cookies

思路：先排序，然后使用双指针进行比对，属于贪心算法。时间复杂度是$O(nlogn)$。

c++ 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {

        sort(g.begin(), g.end() );
        sort(s.begin(), s.end());
        int count =0;
        for(int i =0, j =0; i < g.size() && j < s.size() ; j++)
        {
            if (g[i] <= s[j])
            {
                i ++;
                count ++;
            }
        }
        return count ;   
    }
};

python 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i, j, count =0, 0, 0
        while i < len(g) and j < len(s):
            
            if g[i] <= s[j]:
                i +=1
                count +=1
            
            j +=1
        return count