371. Sum of Two Integers

Topic: Bit manipulation

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = -2, b = 3
Output: 1

Approach1

????????????

def getSum(a: int, b: int) -> int:
    a &= 0xFFFFFFFF
    b &= 0xFFFFFFFF
    while b:
        carry = a & b
        a ^= b
        b = ((carry) << 1) & 0xFFFFFFFF
        # print((a, b))
    return a if a < 0x80000000 else ~(a^0xFFFFFFFF)

387. First Unique Character in a String

Topic: String, Hash Table

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Approach1

my

def firstUniqChar(s: str) -> int:
    cnt = collections.Counter(s)
    for k,v in cnt.items():
        # print(k,v)
        if v == 1:
            return s.index(k)
    return -1

Approach2

1. 已知字符串由小写字母构成，则遍历a-z
2. 分别从目标的字符串头和字符串尾查找对应字母的索引；如果两索引相等，则说明是单一字符
3. 从该索引和此前遍历记录的最小索引中选出新的最小索引

4. 遍历结束后，最小索引即为进行26次遍历返回的最小索引值

   def firstUniqChar(s: str) -> int:
   # 先假设最小索引为最后的字符索引
   min_unique_char_index = len(s)
   
   # 已知字符串由小写字母构成，则遍历a-z
   for c in "abcdefghijklmnopqrstuvwxyz":
       i = s.find(c)
       # 分别从目标的字符串头和字符串尾查找对应字母的索引；如果两索引相等，则说明是单一字符
       if i != -1 and i == s.rfind(c):
           # 更新最新的最小索引
           min_unique_char_index = min(min_unique_char_index, i)
   
   # 如果返回值不为最后字符的索引，则返回最小索引值
   # 否则，根据题意，返回-1
   return min_unique_char_index if min_unique_char_index != len(s) else -1

时间复杂度：O(N) - 常数级别的遍历; 内嵌函数®find一般情况下为O(N) 空间复杂度：O(1)

412. Fizz Buzz

Topic:

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”. 3的倍数输出fizz, 5的倍数输出buzz, 3和5的倍数输出fizzbuzz

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

Approach1

my

def fizzBuzz(n: int) -> List[str]:
    res = []
    for i in range(1,n+1):
        if i % 3 == 0 and i % 5 == 0:
            res.append('FizzBuzz')
        elif i % 3 == 0:
            res.append('Fizz')
        elif i % 5 == 0:
            res.append('Buzz')
        else:
            res.append(str(i))
    return res