Leetcode summary of 20190908-20190915

Posted by chunyang on September 15, 2019

Summary

Solved problems list

  • Kth Smallest Element in a Sorted Matrix
  • All Nodes Distance K in Binary Tree
  • Total Hamming Distance
  • Binary Search Tree Iterator
  • Binary Tree Level Order Traversal
  • Maximum Length of Pair Chain
  • Kth Largest Element in an Array

Several other things interrupted this week.

  • Team building: CS like game
    • It is really funny and we are tired. Besides everyone got a little drunk at the supper that night.
  • Mid-autumn festival

Highlight

Total Hamming Distance

At the first sight, it seems that it is an easy problem. But a naive solution will take O(n^2) time complexity. Recall that Single Number problem, which every number appears three times except one. That problem needs some bit manipulations. This problem’s solution is similar. In order to reduce the complexity, the distance in one bit is the number of zero multiplied by the number of one.

Kth Largest Element in an Array

We can solve it by sorting the array and return size - K element. The time complexity is O(nlogn). It is the complexity of the sorting operation.

The complexity can be reduced to O(n) using the method we use in quick sort, partition. After each partition, we divide the array into three groups: elements less than the pivot, element equal to the pivot, elements larger than the pivot. K can be reduced to a smaller number according to this information.

Maximum Length of Pair Chain

Customized sort.

Kth Smallest Element in a Sorted Matrix

Be careful with the existing condition. It occurs to me that this problem is like merge K sorted list. We use a prority_queue to track each row and pop the smallest element each time until K reachs zero. This solution does not take advantage of the information: each column is sorted.


Creative Commons License
This work is licensed under a CC A-S 4.0 International License.