Contents

ARST打卡第190周[190/521]

Algorithm

lc1739_放置盒子

找规律,看下面的代码和题解

二分法和找规律法其实是类似的,不过多了一个求和公式,使得效率更好了一些,方法三则是更近一步,直接把方程给解出来了,然后效率就更高。 有兴趣的看题解: 作者:力扣官方题解 链接:https://leetcode.cn/problems/building-boxes/solutions/2030450/fang-zhi-he-zi-by-leetcode-solution-7ah2/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* 
2022年12月25日14:33:41 感觉像是一个找规律的题目
思路:
尽量少的地面,也就是优先靠着墙角,然后能堆高就必须堆高。
因为高度最高为n,而只有n个立方体,按照上面的规律肯定不用考虑放不下的问题。
然后就是找规律
1-3 --> n
4 --> 3
5 --> 4
6 --> 5
7 --> 5
8-10 --> 6

所以是这样:
1. 下层1-2-3-4-5地慢慢累加,也就是1-3-6-10
2. 每次累加后,上面堆叠量可以承载前面一个前缀和的值,也即是3时上面承载1,6时上面承载3+1(二次累加和)

2022年12月25日14:49:20 感觉找规律不方便把中间态公式化,还是尝试dp模拟放置过程吧,
但是n为1e9,不能遍历到1e9..学习下题解怎么找到的规律吧

看了一下,题解通过数学列式得出规律,其实和我前面思路一样,但是我没有持续想下去...
*/
func minimumBoxes(n int) int {
    cur, i, j := 1, 1, 1
    for n > cur {
        n -= cur
        i++
        // 累加值,相当于一开始减去顶层,然后减去第二层
        cur += i
    }
    cur = 1
    for n > cur {
        n -= cur
        j++
        // 这里一个个添加边缘的时候的规律,前头加一个,后头加2个成为一个堆,再后头又加两个,但上层又有一个,
        // 所以1,2,3,4---想象成楼梯一开始只有一级,复制一个切面有2级,再一个切面就是3级
        cur++
    }
    return (i-1)*i/2 + j
}

Review

You Don’t Actually Know What Your Future Self Wants | Shankar Vedantam | TED

许多年后,你可能不再是当下的你,但是你却可以塑造未来的自己,就像你活着的意义可以自己赋予一样。

因此可以做如下三件事情去塑造未来的自己:

  1. 花时间做自己的业余兴趣,职业梦想相关的探索,去看对应领域的专家怎么做,而不是把所有的时间花在家人身上。保持对外界的好奇心。
  2. 当我们自信表达现在的观点的时候,可能未来的自己都会是觉得反对观点的,所以请保持谦逊。
  3. 对于生活中的挑战性的机会,今天没办法做到,也许明天有办法做到,所以勇敢一点。

Tips

由浅入深聊聊Golang的sync.Map

Share-sync.Map中amended和Delete删除中nil和expunged的理解

结论

amended: 意思是被修改过的,为true就是表明dirty和readOnly中的map的数据不相同了 readOnly中的map数据为nil: 就是正常的Delete()操作会让readOnly中的map数据值为nil,key还在 readOnly中的map数据被标记为expunged(擦去;删掉): 就是只有在readOnly生成dirty数据时,如果遇到readOnly中标记为nil的值,则标记为expunged,并且不放在dirty中,没有对应key和值

因为一个readOnly数据被抹去分为2种情况:

  1. 情况一(dirty提升为readOnly的map):
    1. 在readOnly中标记key对应的值为nil,dirty中数据的key直接被删除
    2. 在readOnly中的miss命中率太低了,然后dirty_map提升为readOnly中的map,readOnly中的nil值key被抹去(之前之前的dirty的key已经被删除掉了)
  2. 情况二(readOnly先生成dirty,之后再被dirty替换):
    1. 在readOnly中标记key对应的值为nil,dirty中数据的key直接被删除
    2. 插入过程引发的readOnly刷新未删除的数据到dirty(此时会将已经删除标记为nil的数据标记为expunged)(expunged状态可以在Store存储的时候恢复为nil)
    3. 等到后面miss命中率太低,然后dirty_map提升为readOnly的map,去除掉相对应的key值

从上面可以看出,nil状态下,dirty中可能有对应的key值。而expunged状态下,dirty绝对没有对应的key值,除非在增(改)的时候添加对应的key到dirty中,此时也会相对应地把expunged状态转化为nil状态

sync.Map介绍与参考文章

由浅入深聊聊Golang的sync.Map

理解的hack过程

Delete()为什么没有更改amended的状态

感觉这两个状态的理解要理解全部实现,发现删除Delete()是没有更改amended的状态的!!!这样的话,就会造成dirty和readOnly数据不一致(先暂时如此假设,后面会证实为错误,其实是对先前的一些定义没有深入理解),但是可能amended还是false

那么两次删除同一个数据,第一次readOlny标记为nil删除掉数据,第二次,!ok 而且还amended为false,那就导致dirty中存在数据

之后再反复读这个数据,一直miss..然后再dirty同步到readOnly,那岂不是没删除掉???

一定是哪里理解有偏差

理解了,因为readOnly和dirty中的entry指向同一片地址,所以第一次删除一个数据后,不用修改掉amended,还是完全一致的

所以得出结论是,amended在删,查的时候都不会发生变化,只有在增(改)的时候发生变化

但是同样还有这个问题就是,如果增加一个值后,连续删除这个值两次,那么就会第一次dirty中有值,第二次dirty中没有值,当然这时候readOnly是nil,但是其实是科学的,得出的结论就是nil状态下,dirty中可能有对应的key值

看了go1.18的源码就更加清晰了,源码中确定了无论dirty中是否有对应的值,也即是证明了有可能有值,有可能没有值,然后都让miss增加,因为走的是先readOnly再dirty的最长查找路径,所以需要尽快把dirty提升到readOnly上面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// LoadAndDelete deletes the value for a key, returning the previous value if any.
// The loaded result reports whether the key was present.
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            delete(m.dirty, key)
            // Regardless of whether the entry was present, record a miss: this key
            // will take the slow path until the dirty map is promoted to the read
            // map.
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if ok {
        return e.delete()
    }
    return nil, false
}

// Delete deletes the value for a key.
func (m *Map) Delete(key any) {
    m.LoadAndDelete(key)
}