[Leetcode] Two Sum

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis

  • 用一个hash表来围护每个数和其对应的index
    • 如果有重复的数字,则overwrite, 即保留最后出现的index
  • 然后遍历所有的数,如果 (target – 当前数)在哈希表中,且俩数的index不一样,则找到解了
  • 复杂度
    • Time: O(n)
    • Space: O(n)

Code

Reference
[1] https://leetcode.com/problems/two-sum/

[Leetcode] Reverse Words in a String

Problem

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Analysis

  • 首先split string by space
  • 然后 append word in reverse order
  • 注意 如果当前非空,在append下一个word之前,需要append空格

Code


Reference

[Code Interview] Count number of ones

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