Object: Binary Tree

Depth First Traversals:

(a) Inorder (Left, Root, Right) : 4 2 5 1 3

(b) Preorder (Root, Left, Right) : 1 2 4 5 3

(c) Postorder (Left, Right, Root) : 4 5 2 3 1

判断是否为字母, 数字 isalnum() isalpha() isnumeric()

Syntax

1
2
3
4
5

# 判断是否整个string都由alpha and numbers 组成
str.isalnum()

# 判断是否整个string
str.isalpha()

Return Type

Boolean

Ex:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# No space in string
>>> str = "this2018"
>>> str.isalnum()
True

# Space in string
>>> str = "this is..."
>>> str.isalnum()
False

# Check isalpha()
>>> str = "this2018"
>>> str.isalpha()
False

Remove all elements from a linked list of integers that have value val.

Example:

1 2 3

> Input: 1->2->6->3->4->5->6, val = 6 > Output: 1->2->3->4->5 >

思路

pre —> 通过检验的Node

dummy —> 标记head pre, 防止head消失

Note：val相等的情况有可能连续出现，所以只有已验证 != val, 才能pre = pre.next

Note2: 如果写while pre.next, 前面要有while pre

​ 所以: while pre and pre.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        pre = dummy = ListNode(-1)
        dummy.next = head
        
        while pre and pre.next:
            if pre.next.val == val:
                pre.next = pre.next.next
            else:
                pre = pre.next
        
        return dummy.next

原思路 （Time Exceed）

遍历 0—> x, 直到遇到 sqrt(x)

1
2
3
4
5
6
7
8
9

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        for i in range(x+1):
            if (i+1)**2 > x:
                return i

Improvement

Use Binary Search, 降低搜索时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:

    # dfs
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """

        def dfs (start,end):

            # int(float) method, 去小数点后面的数
            mid = int((start + end)/2)

            if mid **2 > x:
                return dfs(start,mid-1)
            else:
                if (mid+1) ** 2 > x:
                    return mid
                else:
                    return dfs(mid+1,end)

        return dfs(0,x)

Float —> Int

Method1: int()

1. int()不需要import math
2. int() 直接舍弃小数点后位数

1
2
3
4
5
6

>>> int(3.5)
3
>>> int(3.8)
3
>>> int(3.1)
3

Method2: math.ceil(), math.floor()

1. You need to import math
2. math.ceil() return 最大值
3. math.floor() return 最小值

1
2
3
4
5

>>> import math
>>> math.ceil(3.1)
4
>>> math.floor(3.5)
3

Method 3: round

1. 语法

1

round(x [, n])

2. 返回值

浮点数x的四舍五入值， 默认返回整数

3. 问题

round遇到5时，并不一定是四舍五入，受计算机精度影响

EX：

1
2
3
4
5
6

>>> round(3.6)
4
>>> round(3.1)
3
>>> round(3.5)
# 可能是3，也可能是4

float 精度转换

Method: round()

1
2
3
4
5
6
7

>>> round(2.333334,2)
2.33
>>> round(2.333334,1)
2.3
>>> round(2.333334,0)
2.0
# Note, when n == 0，return a float

Problem

In python:

1
2
3
4

>>> import math
>>> math.log(243,3)
4.999999999999999
# Expected: 5

Solution

1. 1 2 3

   >>> import math >>> math.log10(243)/math.log10(3) 5

2. 1 2 3 4 5 6 7 8 9

   >>> import math >>> x = math.log(243,3) # Judge whether an int >>> judge = (round(x)-x) < 0.0000001 True # get the Int value >>> round(x)

1. ord() 和chr(), unichr()相反

   ord('A') : ‘A ‘ —> 65

   ord(u'\u2020') : return 8224

   chr(65) : 65 —> A

2. ASCII code for ‘A’ is 65, ‘a’ is 97

1
2
3
4
5
6
7
8
9
10
11

>>> ord('A')
65

>>> ord('a')
97

>>> chr(65)
'A'

>>> chr(97)
'a'

3. Note:

   if {A:1, B:2, ….}

   ord('A')-64

   注意最开始A为65，如果设定A为1，则 - 64

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1:

1 2 3 4

> Input: 11 > Output: 3 > Explanation: Integer 11 has binary representation 00000000000000000000000000001011 >

Example 2:

1 2 3 4

> Input: 128 > Output: 1 > Explanation: Integer 128 has binary representation 00000000000000000000000010000000 >

Method1

1
2
3
4
5
6
7

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        return bin(n).count("1")

Method2

思路：

Int一共32为，每位数字检验是否为1

具体操作：检验最后一个数字，检验完右移，一共32次

Code

1
2
3
4
5
6
7

class Solution(object):
    def hammingWeight2(self, n):
        ans = 0
        for i in range(32):
            ans += n & 1
            n >>= 1
        return ans

Method3

原理：

N = N & (N-1)可以消除N的二进制表示的最后一个1

Code

1
2
3
4
5
6
7

class Solution(object):
	def hammingWeight3(self, n):
        count = 0
        while n != 0:
            n = n & (n-1)
            count +=1
        return count

476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

1 2 3 4

> Input: 5 > Output: 2 > Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. >

Example 2:

1 2 3 4

> Input: 1 > Output: 0 > Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0. >

Method1:

阶段1

1 ^ 1 = 0

0 ^ 1 = 1

==> 11111 ^ 10101 = 01010 —> The answer

==> Target: Establish 1111111 (len == num的二进制数字）

阶段2

n = len(bin(num))-2 设定num的二进制长度n 为 6

6个1: $111111 —> 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5= 2^6 -1$

1
2
3
4
5

class Solution:
	def findComplement(self, num):
        n = len(bin(num))-2
        temp = 2**n -1
        return num ^ temp

Method2:

Step1. 翻转, Target

设定为5

Step2

Target: …..111000

1
2
3

mask = ~0
for i in range(len(bin(num))-2):
    mask << 1

Solution

1
2
3
4
5
6
7
8
9

class Solution:
	def findComplement(self, num):
		# Find mask
        mask = ~0
        for i in range(len(bin(num))-2):
            mask <<= 1
            
		# Get ans
        return ~num ^ mask

二进制十进制转换

1. 十进制—>二进制 bin() 函数 in Python

Input type: int/ long int

Return type: String

将int/ long int 转换为：二进制表示的String, 数字前面+ “0b”, 表示二进制

1
2
3

S = bin(2)
# S = '0b10'
#'0b'-->表示二进制， '10'-->2的二进制表示方法

用法

既然返回值为String，就可以用String的方式来使用

EX：ans = bin(2^3).count("1")

bin(2^3) —> 0b111

"0b111".count("1")—>3

2. 二进制 —> 十进制: int(,)函数 in Python

int(String 二进制表示，2)

The Input String can directly be the number, or the bin() represents

1
2
3
4
5

I1 = int('11',2)
# I1 = 3

I1 = int('0b11',2)
# I1 = 3

EX: Leetcode 461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

1 2 3 4 5 6 7 8 9 10 11

> Input: x = 1, y = 4 > > Output: 2 > > Explanation: > 1 (0 0 0 1) > 4 (0 1 0 0) > ↑ ↑ > > The above arrows point to positions where the corresponding bits are different. >

1
2
3
4
5
6
7
8

class Solution:
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x^y).count("1")