刷题打卡+写论文

June-5-2020 to June-30-2020
刷题+写论文打卡.

Day1. DP周
'''
A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. The result may be large, so return it modulo 1000000007.
Example1:
Input: n = 3
Output: 4
Example2:
Input: n = 5
Output: 13
Note:
1 <= n <= 1000000
'''

Python解法
Basic1:
def TripleHop(x):
    if x < 0:
        return 0    #主要考察剩余量 x = x-n
    if x == 0:
        return 1    #如果减完n步之后,剩余量f(x-n)是0的话,那就只有当前一种路径,无需再走,因此只有一种选择了.
    if x == 1:
        return 1    #减去各种n之后,最终的终止条件只有三种, 1,正好为0 无需再动 2.剩余量为1步,那么再走一步就可以.3.为负数,此路不通,忽略不计.
    return TripleHop(x - 1) + TripleHop(x - 2) + TripleHop(x - 3)
Brute force.这个方法是从最后的target出发,先考虑最后一步,距离目标只有一次迈步时的三种情况.
时间复杂度: O(3^n)[每一次调用都有三个branchs,指数增长].

Solution 2
Memoization Solution DP, bottom-up

class Solution:
    def waysToStep(self, n: int) -> int:
        dp = [0]*(n+1)
        if n == 0:
            return 1
        if n == 1:
            return 1
        if n == 2:
            return 2
        a = 1
        b = 1
        c = 2
        for i in range(3,n+1):
            tmp = a+b+c
            a = b
            b = c
            c = tmp
            if c > 1000000007:
                c = c % 1000000007
        return c

class Solution:
    def waysToStep(self, x: int) -> int:
        memo = [-1] * (x + 1)

        if x < 0:
            return 0
        memo[0] = 1
        if x >= 1:
            memo[1] = 1
        if x >= 2:
            memo[2] = memo[1] + memo[0]

        if x > 2:
            for i in range(3, x + 1):
                memo = memo[i - 1] + memo[i - 2] + memo[i - 3]

        return memo[x]

借助了DP的思想.因为在做f(x-n)时减去不同的n时,会有交集和重复计算.因此,把计算过的数值按照index
存储起来可以重复利用,不需要每次都重新计算,可以提高运行速度.
时间复杂度是: O(n) 空间复杂度O(n).

可能存在的问题是: 如果给出的x的数值过大,可选的方案数值大小有可能会overflow the bounds of an integer.会有溢出问题.

解决方案:
The result may be large, so return it modulo 1000000007.
至于为什么是 10^9 + 7 解释在此:https://www.quora.com/What-exact ... ogramming-web-sites

(10^9 + 7 ) is a prime number. To be more precise, it is the first 10-digit prime number.
1000000007的取值意义:It can make  sure to print your answer modulo (10^9 +7) ensures that it fits the maximum value your system is capable of storing in standard allotted space, preventing “integer overflow”,

class Solution:
    def waysToStep(self, x: int) -> int:
        memo = [-1] * (x + 1)

        if x < 0:
            return 0
        memo[0] = 1
        if x >= 1:
            memo[1] = 1
        if x >= 2:
            memo[2] = memo[1] + memo[0]

        if x > 2:
            for i in range(3, x + 1):
                memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3]
                if memo[i] > 1000000007:
                    memo[i] = memo[i] % 1000000007
        return memo[x
[/i][/i][/i][/i]

Day 3 快递延迟,屏幕没有送到...烦躁
'''
A magic index in an array A[0...n-1] is defined to be an index such that A[i] = i.
Given a sorted array of distinct integers, write a method to find a magic index,
if one exists, in array A. If not, return -1. If there are more than one magic index,
return the smallest one.

Example1:

Input: nums = [0, 2, 3, 4, 5]
Output: 0
Example2:

Input: nums = [1, 1, 1]
Output: 1
Note:

1 <= nums.length <= 1000000
'''


class Solution:
    def findMagicIndex(self, nums: List[int]) -> int:
        index = []

        for i in range(len(nums)):
            if nums[i] == i:
                index.append(i)

        if not index:
            return -1

        return min(index)

    def findMagicIndex2(self, nums: List[int]) -> int:

        for i in range(len(nums)):
            if nums[i]==i:
                return i
        return -1

Brute force方法有点简单,难以置信是个DP问题.
时间复杂度:O(n)
题目里有两个条件. Condition1: sorted array. Condition2: distinct integers.
自此还不太理解 这俩条件是干啥用的...

'''
Follow Up: What if values are not distinct? 有重复?啥意义....
'''

Explain:

对于有序数值,A[i] = i 表示i位置和A序列的第i个数值一样,是一种对齐形式. 有序的情况下,可以用来优化
对齐检查, 如果A[i] < i, 那么产生对齐的位置一定在i位置往后 i+1位置之后.
可以用二分查找来优化.O(logN).


class Solution {
private:
    void binary_search(vector<int>& nums, int left, int right, int& ret){
        // 这里做一个剪枝
        if(ret != -1 && ret<left) return;
        if(left <= right){
            int mid = left + (right - left) / 2;
            // 如果找到目标的索引，需要尝试能否找到更小的索引值
            if(nums[mid] == mid){
                if(ret == -1) ret = mid;
                else if(mid < ret) ret = mid;
                binary_search(nums, left, mid - 1, ret);
            // 如果mid不符合要求，则需要在mid两边继续查找
            }else{
                binary_search(nums, left, mid - 1, ret);
                binary_search(nums, mid + 1, right, ret);
            }
        }
    }
public:
    int findMagicIndex(vector<int>& nums) {
        // 2. 二分法
        int ret = -1;
        binary_search(nums, 0, nums.size()-1, ret);
        return ret;
    }
};

‘’‘
Follow up: What if the elements are not distinct?
’‘’

Day2
'''
Imagine a robot sitting on the upper left corner of grid with r rows and c columns.
The robot can only move in two directions, right and down, but certain cells are "off limits"
such that the robot cannot step on them.
Design an algorithm to find a path for the robot from the top left to the bottom right.

"off limits" and empty grid are represented by 1 and 0 respectively.

Return a valid path, consisting of row number and column number of grids in the path.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: [[0,0],[0,1],[0,2],[1,2],[2,2]]
Note:

r, c <= 100
'''
这题可以用bottom-up的解法, 先看target位置(r,c),想要到达(r,c)可以先到达(r,c-1)或者(r-1,c).
可选步子只有向右和向下,因此想要到达任意位置都遵循这个准则[想要到达(r,c)可以先到达(r,c-1)或者(r-1,c)].然后输出是一条可行路径.

#Solution with recursion O(2^r+c)
def getPath(maze):
    if maze == None or len(maze) == 0:
        return None
    path = []
    if isPath(maze, len(maze)-1, len(maze[0])-1, path):
        return path
    return None

def isPath(maze, row, col, path):
    #if out of bounds or not available, return
    if col < 0 or row < 0 or not maze[row][col]:
        return False

    isAtOrigin = (row == 0) and (col == 0)

    #if there's a path from the start to here, add my location
    if isAtOrigin or isPath(maze, row, col-1, path) or isPath(maze, row-1, col,path):
        point = (row,col)
        path.append(point)
        return True

    return False
   
这个方法的时间复杂度O(2^r+c). 这其中的路线上会有一些重复的部分,可以作为优化的突破点.
可以考虑记录下已经访问过的节点(判定过失败的节点),使用dp的方法来做优化.

def isPathMemoized(maze, row, col, path, failedPoints):   #增加failedPoints
    #If out of bounds or not availabe, return
    if col < 0 or row < 0 or not maze[row][col]:
        return False

    point = (row,col)

    # if we've already visisted this cell, return
    if point in failedPoints:
        return False

    isAtOrigin = (row == 0) and (col == 0)

    #If there's a path from start to my current location, add my location
    if isAtOrigin or isPathMemoized(maze, row, col-1, path, failedPoints) or isPathMemoized(maze, row-1, col, path, failedPoints):
        path.append(point)
        return True

    failedPoints.append(point) #failedPoints 增加元素
    return False

时间复杂度 O(XY),每个元素只访问一次.[疑问:XY是什么?为啥不是rc了?]

有兴趣一起刷题吗？  如果有的话，留一个微信号呗~  java的

zurich.hill 发表于 2020-6-10 03:53
有兴趣一起刷题吗？  如果有的话，留一个微信号呗~  java的

好的呀~ 我私信你

CtCi 第八章 第三题的python测试用例有问题....

'''
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.
'''

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        def prefix(strs, index):
            check_prefix = strs[0][:index]
            for index in range(1, len(strs)):
                if not strs[index].startswith(check_prefix):
                    return False
            return True


        if not strs:
            return ""

        minLength = float('inf')
        for string in strs:
            minLength = min(minLength, len(string))

        low, high = 0, minLength

        while low <= high:
            mid = (low+high)/2
            if (prefix(strs, mid)):
                low = mid + 1
            else:
                high = mid - 1

        return strs[0][:(low+high)/2]

Day5
数组遍历框架，典型的线性迭代结构：

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}



链表遍历框架，兼具迭代和递归结构：

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next)
}





二叉树遍历框架，典型的非线性递归遍历结构：

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left)
    traverse(root.right)
}

树的框架
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}



二叉树框架可以扩展为 N 叉树的遍历框架：

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child)
}

'''
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);
Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I
'''




class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s

        zigzag = ['' for x in range(numRows)]

        row, step = 0,1

        for item in s:
            
            zigzag[row] += item

            if row == 0:
                step =1
            elif row == numRows -1:
                step = -1
            row += step

        return ''.join(zigzag)