leetcode260_singlenumberIII

思路：所有🌲异或完后只剩下两个数的异或，把每个数理解为二进制数，在异或的结果上的每一个1的位置，两个素
总过出现的情况只能是0和1，如果都是0或都是1就不可能， 所有可以将异或结果和每个数二次异或分成两组，
每一个组必然包含单独一个数，异或就可以求出结果；
核心代码：
diff &= -diff; //取最高位的1，任意一个1就可以，注意diff是所有数异或以后的结果
//second pass:
for(int num: nums){
if(num&diff == 0){
a ^= num;
else{
b ^= num;
}
}
return {a, b};
}

lecture9.computerArchiture

L1 split cache
multiple ports mean multiple access
cause larger overhead

eg: avoid hazard, multiple ports

mltiple exclusion and mutiple inclusion:
L1 and L2
L1 or L2

multiple level cache

  1. write through and write back
    readhit: read hit time + miss penalty
    read miss: read hit time + miss penalty
    write hit: write hit time + wirte time to lower level
    wirte miss: write hit time + write time to lower level + read block from lower level

  1. write through plus non-write allocate

  2. write back and write allocate
    read hit: read hit time
    read miss: read hit time + miss penalty plus time to write dirty block if it is dirty

write hit:

Daily Friday

##秋雨绵绵顾自怜 独坐室中狂刷题

##管他日日笙箫起 我自地里刨根底
leetcode304. Range Sum Query 2D- Immutable

Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

dp solution:

Leetcode 474. Ones and Zeroes

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:
The given numbers of 0s and 1s will both not exceed 100
The size of given string array won’t exceed 600.

Example1:
Intput: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
Output: 4
01背包问题

Solution1: Dynamic Programing
类似01背包问题，采用dp[i][j], i表示采用了i个0， j表示j个1， 对于每个string，可以决定采用或者不采用，放入包里，那么决定于
i， j减去当前需要的还能装入的最大值， 所以dp公式： dp[i][j] = max(dp[i-i_need][j-j_need] + 1, dp[i][j]);
因为字符串的顺序是有长有短，不按顺序，所以并不能确定dp[i-i_need][j-j_need]已经更新到最大，所以不能滚动数组操作??（可以）
对于每个字符采用一个新二维矩阵。

Solution2: DP 采用单二维矩阵解法，空间复杂度为O(mn)
更新次序从bottom right往top left更新，每次会在更大容量的包dp[i][j]中从左向右加
1， 如果从左上到右下更新，会重复计算。
核心代码：
for(int i = m; i >= numZeros; i–){
for(int j = n; j >= numsOnes; j–){
memo[i][j] = max(memo[i][j], memo[i-numZeros][j-numOnes]+1);
}
}
return memo[m][n];