Leetcode

按位与、或、异或等二进制运算方法

与 & AND

运算规则

0 & 0 = 0

0 & 1 = 0

1 & 0 = 0

1 & 1 = 1

Example

Calculate 3 & 5:

3: 0011

5: 0101

3&5: 0001

负数

负数按补码参与按位与运算。

或 | OR

运算规则

0 | 0 = 0

0 | 1 = 1

1 | 0 = 0

1 | 1 = 1

Example

Calculate 3 | 5:

3: 0011

5: 0101

3|5: 0111

异或 ^ XOR

运算规则

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 0

1 ^ 1 = 0

Example

Calculate 3 ^ 5:

3: 0011

5: 0101

3^5: 0110

取反 ~ NOT

运算规则

~ 0 = 1

~ 1 = 0

左移 <<，右移 >>

运算规则

按二进制左/右移 N位

Example

1 << 3

1
2
	0001 << 3 
=	1000

10 >> 2

1
2
	1010 >> 2 
=	0010

EX: Leetcode371. Sum of Two Integers

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

Example:
Given a = 1 and b = 2, return 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # 该用法适用于JAVA, C++，但Python负数使用有问题
    def getSum2(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        if b == 0:
            return a

        temp = a ^b
        carry = (a &b )<< 1

        return self.getSum(temp, carry)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 用mask解决负数问题
   def getSum(self, a, b):
       """
       :type a: int
       :type b: int
       :rtype: int
       """
       MAX = 0x7FFFFFFF
       MIN = 0x80000000
       mask = 0xFFFFFFFF

       while b !=0:
           a, b = (a^b) & mask, ((a&b)<<1) & mask

       return a if a <= MAX else ~(a ^ mask)
Leetcode

136. Single Number

136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4

Method1: 排序

分析：要求Run time O(N), Space Complexity: O(1)

==> 考虑Sort the array

Note： Step = 2时，要考虑最后一个数是否可取，确认范围

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()

        for i in range(0, len(nums) - 1, 2):
            if nums[i] != nums[i + 1]:
                return nums[i]

        return nums[-1]

Methos2：Bit Manipulation(XOR)

分析：

  1. $a ⊕ 0 = a$
  2. $a ⊕ a = 0$
  3. $a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b$

计算nums里面每一个num ⊕ 运算的结果，最后的值就是the Single number

1
2
3
4
5
6
7
8
9
10
11
12
def singleNumber2(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    a = 0

    for i in nums:
        a ^= i

    return a
Leetcode

XOR ^

XOR 异或

一般表示

$a⊕b$

In Python/ C++

a^b

运算性质

  1. 交换律 ：$A ⊕ B = B ⊕ A$
  2. 结合律：$A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C$
  3. 恒等律：$A ⊕ 0 = A$
  4. 归零率：$A ⊕ A = 0$
  5. 推论：$(B ⊕ A) ⊕ B = A ⊕ (B ⊕ B) = A ⊕ 0 = A$
Python

Sorting with lambda

Sorting list/Dic with lambda

1. Sort a List

sorted

1
sorted(iterable[,key][,reverse])

细节

list.sort()—> sort the list

sorted(list)—> return a sorted list

1
2
3
4
5
6
7
8
9
10
11
12
# Original list
L = ['c','a','b']

l2 = sorted(list)
# return a sorted list, but original list is not changed
# L2:['a', 'b', 'c']

l3 = sorted(list,reverse = True)
# L3: ['c','b','a']

L.sort()
# L itself has been sorted

2. Sort a dict?

Actually you cannot sort a dictionary, itself has no order.

But you can return a new sorted list

Example:

1
2
3
4
5
6
7
8
9
10
11
12
dic = {'c':1, 'b':2,'a':3}

L1 = sorted(dic)
# L1: ['a', 'b', 'c']
# sorted by key values and return to a list of keys

L2 = sorted(dic.values())
# L2:[1,2,3]

L3 = sorted(dic.items())
# L3: [('a', 3), ('b', 2), ('c', 1)]
# Return the list of the item tuples

2. Use lambda

Sort a list

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
L = [
    {'x': 3, 'y': 2, 'z': 1},
    {'x': 2, 'y': 1, 'z': 3},
    {'x': 1, 'y': 3, 'z': 2},
]

#此处dic的意义：Every element in the list
L2 = sorted(L,key = lambda dic:dic['y'])
# L2: [{'x': 2, 'y': 1, 'z': 3}, {'x': 3, 'y': 2, 'z': 1}, {'x': 1, 'y': 3, 'z': 2}]

L.sort(key=lambda dic: dic[z])
# L: 


# 用Method
>>> def getKey(item):
...     return item[0]
>>> l = [[2, 3], [6, 7], [3, 34], [24, 64], [1, 43]]
>>> sorted(l, key=getKey)
[[1, 43], [2, 3], [3, 34], [6, 7], [24, 64]]

Sort a dict (return a list)

Example

1
2
3
4
5
6
7
8
9
dic = {
    'a': {'x': 3, 'y': 2, 'z': 1},
    'b': {'x': 2, 'y': 1, 'z': 3},
    'c': {'x': 1, 'y': 3, 'z': 2},
}

L = sorted(dic, key = lambda k: dic[k]['y'])
# 推测：k是指every key value
# L:['b', 'a', 'c']
Hexo

Hexo操作

常规使用

1. 定位到即将使用的文件夹

1
$ cd /Users/yukizhong/Dropbox/02_Coding/Local_Blog

2. Create a new post

1
$ hexo new "My New Post"

More info: Writing

3. Generate static files

1
$ hexo generate

More info: Generating

4. Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Run server

1
$ hexo server

More info: Server

文档使用细节

1. Add multiple tags

在文档开头定义中：

1
tags: [tag1, tag2, tag3]

2. Locate the Category

将Blog放在Python下：

1
category: Python

详细指南

https://madongqiang2201.github.io/2016/07/21/Mac%E4%B8%8BHexo%EF%BC%8Bgithub-pages%E6%90%AD%E5%BB%BA%E9%9D%99%E6%80%81%E5%8D%9A%E5%AE%A2/

出现的问题

1. hexo s Error

Error: Port 4000 has been used. Try other port instead.

Command: sudo hexo s -p 5000

2. 上传失败 hexo d

ERROR

1
fatal: unable to access 'https://github.com/.../': Could not resolve host: github.com

问题：不该用代理的时候用了代理，最简单粗暴：断了VPN

Java

Set Example

Set Example

1
2
3
4
5
6
7
8
9
10
11
public class Contains_Duplicate_II_219 {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        for (int i=0; i<nums.length;i++){
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
            if (set.size()>k) set.remove(nums[i-k]);
        }
        return false;
    }
}
Java

ArrayList Example

Basic Use Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (numRows == 0) return ans;
        List<Integer> row1 = new ArrayList<Integer>();
        row1.add(1);
        ans.add(row1);
        if (numRows == 1) return ans;

        for (int i = 1; i < numRows; i++){
            List<Integer> theRow = new ArrayList<>();
            List<Integer> prevRow = ans.get(i-1);
            theRow.add(1);
            for (int j = 1;j<i;j++) {
                theRow.add(prevRow.get(j-1) + prevRow.get(j));
            }
            theRow.add(1);
            ans.add(theRow);
        }
        return ans;
    }
}