Category Archives: Coding

Coding category

[Code Interview] Count number of ones

Posted on by
Reply

Problem

Counting the number of 1 bits in the binary representation of a given integer.  

Analysis

Method 1: 

  • shift the number right by one bit each time, and check whether the right-most bit is 1
    • If yes, count++

Method 2:

    • if n is not 0, count++
    • assign n = n & (n-1), repeat until n is 0

    Time complexity
    • method 1: theta(n)
    • method 2: O(n)

    Code



    Reference

    [Leetcode] Rotate image

    Posted on by
    Reply

    Problem

    You are given an n x n 2D matrix representing an image.
    Rotate the image by 90 degrees (clockwise).
    Follow up:
    Could you do this in-place?

    Analysis

    对于一个n*n的矩阵，可以像剥洋葱一样对每一层进行rotate，一共有n/2层

    对于每一层，采用 matrix[i][j] = matrix[n-1-j][i] 进行 in-place的rotation

    时间复杂度: O(n^2)
    空间复杂度: O(n^2)

    Code

    [Leetcode] Peek Iterator

    Posted on by
    Reply

    Problem:

    Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().

     Example:
    Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].
    Call next() gets you 1, the first element in the list.
    Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
    You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

    Analysis:

    Iterator接口只提供了next() 和 hasNext() 函数

    • next(), 取下一个元素，同时指针移到下下个元素
    • hasNext(), 返回是否还有下一个元素

    然后 peek() 函数只取下一个元素，而并不真正移动指针。即，peek如果多次连续被调用，返回的值应该不变 (一直是当前元素)。因此可以用next函数来取下一个元素，并将其cache，所以如果peek多次被调用，只需要返回cache中的值即可。

    具体实现如下

    • peek()
      • 如果cache有效，直接返回cache中的值。
      • 否则，调用next函数取下一个元素放在cache中，并将cache设为有效
    • next()
      • 如果cache有效，则返回cache中的值，并将cache置为失效
      • 否则，直接调用next函数
    • hasNext()
      • 如果cache有效，则直接返回true
      • 否则，直接调用hasNext函数

    Code: