首页 > 代码库 > 强化班ladder

强化班ladder

2024-09-30 20:41:01   215人阅读

@2017.06.04

Follow up in Code Interview

  • 401 - kth-smallest-number-in-sorted-matrix
    • 排序数组，即每一行每一列都是排好序的
    • 类似于之前做的那道题，对这种排序数组，是从左上角往右下角看的。
    • 每次pop一个最小值直到找到kth，所以用堆。
    • 重刷呀
    • --- heap堆 & matrix矩阵 ---
    • from heapq import *
class Solution:
    # @param matrix: a matrix of integers
    # @param k: an integer
    # @return: the kth smallest number in the matrix
    def kthSmallest(self, matrix, k):
        # write your code here
        if not matrix or not matrix[0] or k <= 0:
            return
        rowNum, colNum = len(matrix), len(matrix[0])
        if rowNum * colNum < k:
            return
        kth, heap, visited = 0, [], set([(0, 0)])
        heappush(heap, (matrix[0][0], 0, 0))
        xPath, yPath = [1, 0], [0, 1]  # go right or go down to get the next one
        while kth < k - 1 and heap:
            val, row, col = heappop(heap)
            kth += 1
            for i in range(2):
                x = row + xPath[i]
                y = col + yPath[i]
                if x < rowNum and y < colNum and (x, y) not in visited:
                    heappush(heap, (matrix[x][y], x, y))
                    visited.add((x, y))
        return heappop(heap)[0]
  • 406 - minimum-size-subarray-sum
    • 窗口型指针问题。最好还是用 for i in range(): while j 的模板
    • 因为i，j都是一直向右移动(不会回退)，所以时间复杂度是O(2 * n)的
    • 并不是所有subarray sum的题都是用prefixSum前缀和
    • 还要注意这道题如果array里面有负数，就不能实现这种O(n)的指针移动啦，具体可以再思考下。
    • --- TwoPointers两根指针 ---
    • btw，看到chanllenge里有说可以试着实现O(nlogn)的算法，我想了可以利用prefixSum + BinarySearch的方式实现。也就是对每一个前缀和为x的位置，去二分查找其前面的最右边的小于 x - s的位置，即可。
    • 重刷呀
    • class Solution:
     # @param nums: a list of integers
     # @param s: an integer
     # @return: an integer representing the minimum size of subarray
    def minimumSize(self, nums, s):
        # write your code here
        if not nums or s <= 0:
            return -1
        j, subSum, length = 0, 0, sys.maxint
        for i in range(len(nums)):
            while j < len(nums) and subSum < s:
                subSum += nums[j]
                j += 1
            if subSum >= s and j - i < length:
                length = j - i
            subSum -= nums[i]
        return -1 if length == sys.maxint else length
  • 384 - longest-substring-without-repeating-characters
    • 这个题也属于窗口类指针问题。
    • 因为只有256个ascii字符，所以可以直接用charAt数组，而不用hash。
    • 这题我没用for while的模板，因为j >= len(s)就可以直接退出了。
    • --- TwoPointers两根指针 ---
    • class Solution:
    # @param s: a string
    # @return: an integer
    def lengthOfLongestSubstring(self, s):
        # write your code here
        if not s:
            return 0
        cnt, i, j, ans = 0, 0, 0, 1
        charAt = [0] * 256
        while j < len(s):
            while j < len(s) and not charAt[ord(s[j])]:
                cnt += 1
                charAt[ord(s[j])] += 1
                j += 1
            ans = max(ans, j - i)
            charAt[ord(s[i])] -= 1
            i += 1
        return ans
  • 386 - longest-substring-with-at-most-k-distinct-characters
    • 重刷呀(必须)
    • 在(s[j] in hashTable or distinctCount < k)这里犯了错，我第一遍的时候写成了while j < len(s) and distinctCount <= k，这导致我需要这样更新ans：ans = max(ans, j - i - 1) if distinctCount > k else max(ans, j - i). 这就是因为不知道退出while的时候到底是因为distinctCount > k or j >= len(s)，所以ans要分情况计算，这种情况很难想出来，所以倒不如用第一种写法。
    • --- TwoPointers两根指针 & HashTable哈希表 ---
    • class Solution:
    # @param s : A string
    # @return : An integer
    def lengthOfLongestSubstringKDistinct(self, s, k):
        # write your code here
        if not s or k <= 0:
            return 0
        i, j, distinctCount, ans = 0, 0, 0, 1
        hashTable = {}
        while j < len(s):
            while j < len(s) and (s[j] in hashTable or distinctCount < k):
                if s[j] in hashTable:
                    hashTable[s[j]] += 1
                    j += 1
                else:
                    hashTable[s[j]] = 1
                    j += 1
                    distinctCount += 1
            ans = max(ans, j - i)
            hashTable[s[i]] -= 1
            if not hashTable[s[i]]:
                hashTable.pop(s[i])
                distinctCount -= 1
            i += 1
        return ans
  • 465 - kth-smallest-sum-in-two-sorted-arrays
    • 本质上跟401是一样的，你可以吧这两个数组的组合看成是一个矩阵呀。
    • --- TwoPoniters两根指针 ---
    • from heapq import *
class Solution:
    # @param {int[]} A an integer arrays sorted in ascending order
    # @param {int[]} B an integer arrays sorted in ascending order
    # @param {int} k an integer
    # @return {int} an integer
    def kthSmallestSum(self, A, B, k):
        # Write your code here
        if not A or not B or k <= 0 or k > len(A) * len(B):
            return
        heap = [(A[0] + B[0], 0, 0)]
        APath, BPath = [0, 1], [1, 0]
        visited = set((0, 0))
        kth = 0
        while heap and kth < k - 1:
            val, indA, indB = heappop(heap)
            kth += 1
            for i in range(2):
                newA, newB = indA + APath[i], indB + BPath[i]
                if newA < len(A) and newB < len(B) and (newA, newB) not in visited:
                    heappush(heap, (A[newA] + B[newB], newA, newB))
                    visited.add((newA, newB))
        return heappop(heap)[0]

 

 

 

 

 

 

 

 

 

 

强化班ladder


联系
我们