记录CS106b学习过程，至今依然记得分形和像素沙堆带给我的感动与震撼，

assignment5 combine

之前的思路都没用记录下来

测试了自己写的combine，然后...

cpp

Vector<DataPoint> combine(const Vector<Vector<DataPoint>>& sequences) {
    /* TODO: Delete the next few lines and implement this. */

    if (sequences.size() == 0) return {};
    if (sequences.size() == 1) return sequences[0];
    int mid = sequences.size() / 2;
    Vector<Vector<DataPoint>> left = sequences.subList(0, mid);
    Vector<Vector<DataPoint>> right = sequences.subList(mid);


    return merge(combine(left), combine(right));
}
Vector<DataPoint> merge(const Vector<DataPoint>& a, const Vector<DataPoint>& b){
    Vector<DataPoint> result;
    int i = 0, j = 0;

    // 比较并合并
    for (; i < a.size() && j < b.size(); ) {
        if (a[i].weight <= b[j].weight) {
            result.add(a[i]);
            i++;
        } else {
            result.add(b[j]);
            j++;
        }
    }

    // 处理a剩下的元素
    while (i < a.size()) {
        result.add(a[i]);
        i++;
    }

    // 处理b剩下的元素
    while (j < b.size()) {
        result.add(b[j]);
        j++;
    }

    return result;
}

当时看到题目就很迷惑，什么测试案例给的什么东西啊...然后发现是用一种教幼儿园小朋友的方式把几个数列集合串起来，，，给数字起名字了，然后用datapoint包个名字，其实比较像一个帮派(vector)里每个人和每个人的资产排个等级，另一个帮派排个等级这样，然后合并果断想如何插入啊，然后就是查文档问题...实际并不是貌似是cs50讲过的什么排序来着，反正就是喊人上去一点点摆那个场景记得倒挺清楚的，于是立刻就去写了，发现不会写，重新看题目，知道该如何排序了，但具体落实到代码实现依然毫无思路，就，两个两个vector分组，然后把它们合并到一块去》但是很奇怪，我应该判断从左到右，数字是否根据两组而定？大于左边小于右边就插入这个数。。。吗？然后一层层递归现在考虑最简单的情况：只有两个序列，每个序列都只有一个元素。就是直接连成{1，2}啊，它大小已经排好了？...还要比较序列之间的大小...但是如果是插空的那种还需要递归是吗？...裂开再递归，判断两者第一个数字，输出小的小就可以了，但是分组这个活也需要我写代码吗？先把4个序列分成两组：第一组: [{1}, {3}] 第二组: [{2}, {4}] ..不是，我在想分组这个过程难道不还是要把大小比一遍再放入lefthalf和righthalf吗？...分组只看位置，不看内容：

输入: [{1}, {3}, {2}, {4}]
        ↑    ↑    ↑    ↑
        0    1    2    3     ← 只看下标位置

分组：
- 左半：下标0,1 → [{1}, {3}]  
- 右半：下标2,3 → [{2}, {4}]

完全不关心 {1} 和 {3} 谁大谁小，也不关心 {2} 和 {4} 谁大谁小。排序发生在递归合并的时候：

左半 [{1}, {3}] 
     ↓ (递归调用combine)
合并 {1} 和 {3} → 得到 {1,3}

右半 [{2}, {4}]
     ↓ (递归调用combine)  
合并 {2} 和 {4} → 得到 {2,4}

那如果是4123咋办？...不对，它序列里会自动排好序。。 ...大概想通过程了，那递归就基础情况就是如果只剩下两个序列return 小的那一列，然后再分成个数相同的两列。基础情况：

cpp

if (lists.size() == 0) return {};
if (lists.size() == 1) return lists[0];

我觉得我这种分组计算写的好麻烦...?

cpp

    for(Vector<DataPoint> p : sequences){
        left.add(p);
        if(count == mid)
            break            
    }

实际可以这样：

cpp

Vector<Vector<DataPoint>> left = sequences.subList(0, mid);
Vector<Vector<DataPoint>> right = sequences.subList(mid);

分成两半但是仍然不知道下一步该如何行进？明明想的是只有输出小的那一个就行，，，if比较吗？而且这是个序列集合...?

cpp

Vector<DataPoint> combine(const Vector<Vector<DataPoint>>& sequences) {
    /* TODO: Delete the next few lines and implement this. */

    if (sequences.size() == 0) return {};
    if (sequences.size() == 1) return sequences[0];
    int mid = sequences.size() / 2;
    Vector<Vector<DataPoint>> left = sequences.subList(0, mid);
    Vector<Vector<DataPoint>> right = sequences.subList(mid);


    return combine(left) + combine(right);
}

combine(left) 返回一个有序序列，combine(right) 返回一个有序序列，但 + 只是把它们连接起来，不是按顺序合并比较 A[左手指的位置] 和 B[右手指的位置]：

1 < 2 → 把1加入结果，左手指向右移动一位
现在左手指着3，右手指着2
3 > 2 → 把2加入结果，右手指向右移动一位
现在左手指着3，右手指着4
3 < 4 → 把3加入结果，左手指向右移动一位 ... 以此类推不知道什么鬼啊，只能想出很逆天的for（int i）就是用 for (int i) 这种循环，但需要两个索引： for里面是不能这么写吗？for((int i = 0; i < a.size() ;i++ ) && (int j = 0; j < b.size(); j++)) 确实不能。

cpp

int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
    // 比较逻辑
    i++; 或 j++;  // 手动控制移动
}

cpp

Vector<DataPoint> combine(const Vector<Vector<DataPoint>>& sequences) {
    /* TODO: Delete the next few lines and implement this. */

    if (sequences.size() == 0) return {};
    if (sequences.size() == 1) return sequences[0];
    int mid = sequences.size() / 2;
    Vector<Vector<DataPoint>> left = sequences.subList(0, mid);
    Vector<Vector<DataPoint>> right = sequences.subList(mid);


    return merge(combine(left), combine(right));
}
Vector<DataPoint> merge(const Vector<DataPoint>& a,const Vector<DataPoint>& b){
    Vector<DataPoint> result;
    int i = 0, j = 0;
    for (; i < a.size() && j < b.size(); ) {
        if (a[i].weight <= b[j].weight) {
            result.add(a[i]);
            i++;
        } else {
            result.add(b[j]);
            j++;
        }
    }
    return result;

}

没有处理剩余元素。

a = [1, 3, 5] b = [2, 4]

merge过程： i=0,j=0: 1<2 → 输出1, i=1 i=1,j=0: 3>2 → 输出2, j=1
i=1,j=1: 3<4 → 输出3, i=2 i=2,j=1: 循环结束（i=2 == a.size()）

但b还有剩余：[4] 没有输出 ...在循环外面if一个如果a/b不为空就把最后的加上去就可以了。。最后就可以（嗯。

然后时间复杂度大概是这样... ·把所有元素扔进大数组 + 排序 → O(n log n) ·维护一个大数组，逐个插入新序列 → O(nk)

题目给的思路：递归深度：log₂k

每次递归都把k个序列分成两半

k=8 → 4 → 2 → 1 (3层)

k=1024 → 10层

每层工作量：O(n)

每层都要归并所有n个元素

但归并是O(n)操作

总时间：O(n) × O(log k) = O(n log k)

binary heap/heap

。。。写完以上其实又写完了binary heap。。。然后又能写千字小作文了。。。。想出binary heap二叉树和数组转换机制的是家里请高人了吗？。。哎等等，我不一定要用assignment计数，嗯对。因为逐渐写cs106b的情况就是不知道它要问什么但是可以一口气都写完（离谱。。回过头才发现自己都写过了。。。。

不是哥们我跟你们说这个太好笑了啊。。。。我笑死了已经哈哈哈哈哈哈哈哈哈哈

以下是大型造轮现场，

cpp

HeapPQueue::HeapPQueue() {
    /* TODO: Implement this. */
    elems = new DataPoint[INITIAL_SIZE];
    allocatedSize = INITIAL_SIZE;
    logicalSize = 0;

}

HeapPQueue::~HeapPQueue() {
    /* TODO: Implement this. */
    delete[] elems;
}

int HeapPQueue::size() const {
    /* TODO: Delete the next line and implement this. */
    return logicalSize;
}

bool HeapPQueue::isEmpty() const {
    /* TODO: Delete the next line and implement this. */
    return logicalSize == 0;
}

void HeapPQueue::enqueue(const DataPoint& data) {
    /* TODO: Delete the next line and implement this. */
    if (logicalSize + 1 >= allocatedSize) {
        DataPoint* newMemory = new DataPoint[allocatedSize * 2];

        for (int i = 1; i <= logicalSize; i++)
            newMemory[i] = elems[i];


        delete[] elems;           // 释放旧的
        elems = newMemory;        // 指向新的
        allocatedSize *= 2;
    }


    logicalSize++;
    elems[logicalSize] = data;

    int i = logicalSize;
    while(i > 1){
        int pi = i/2;
        if(elems[i].weight < elems[pi].weight){
            DataPoint temp = elems[i];
            elems[i] = elems[pi];
            elems[pi] = temp;

            i = pi;
        }
        else
            break;
    }


}

DataPoint HeapPQueue::peek() const {
    /* TODO: Delete the next line and implement this. */
    if (isEmpty()) error("");

    return elems[1];
}

其实在写dequeue时想过用等比数列求和的某种神金思路来找规律判断是否把移上去的弄到最后一层....乐。

cpp

DataPoint HeapPQueue::dequeue() {
    /* TODO: Delete the next line and implement this. */
    if (isEmpty()) error("");

    DataPoint result = elems[1];
    if (logicalSize == 1) {
        logicalSize--;
        return result;
    }

    elems[1] = elems[logicalSize];
    logicalSize--;
    int i = 1;

    while (true) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int smallest = i;

        if (left <= logicalSize &&
            elems[left].weight < elems[smallest].weight) {
            smallest = left;
        }
        if (right <= logicalSize &&
            elems[right].weight < elems[smallest].weight) {
            smallest = right;
        }

        if (smallest == i) {
            break;
        }

        DataPoint temp = elems[i];
        elems[i] = elems[smallest];
        elems[smallest] = temp;
        i = smallest;
    }

    return result;
}

bool isInLastLayer(int index, int logicalSize) {
    if (logicalSize == 0) return true;
    if (logicalSize == 1) return true;

    int h = 0;
    int capacity = 0;
    while (capacity < logicalSize) {
        h++;
        capacity = (1 << h) - 1;
    }

    int nodesInPreviousLayers = (1 << (h-1)) - 1;
    return index > nodesInPreviousLayers;
}

昨晚算了一下时间，感觉我大一上搞完cs106b和games101等等几个目标说紧也有点紧，说松也比较松，加油吧。不过上次搞小组作业的qt小程序貌似就已经弄出来一个小cs106b大作业了。。。？？离谱哎。。。哦，这也是一段传奇经历，回头开个新post写吧。

突然想起我哪个作业写的好像是UTF-8的编码原理（貌似是？术语可能用不着）来着，突然又想把那个翻出来看，但实际上好像就是处理了一下小数算... 好开心好开心(｡◕ˇ∀ˇ◕)

hashtable

学习过程想做成按照日期的调整目录之类的，点击后可以自动跳转到那一天，感觉自己是有高强度写博客需求的。。。我服了。。。自行看下面：

cpp

bool LinearProbingHashTable::insert(const string& elem) {
    /* TODO: Delete this comment and the next lines, then implement this function. */
    if(numElements == numSlots) return false;
    int s = hashFn(elem);
    int p = -1;
    for(int i = 0; i < numSlots; i++){
        int c = (s + i) % numSlots;

        if(elems[c].type == SlotType::FILLED && elems[c].value == elem)
            return false;

        else if(elems[c].type == SlotType::EMPTY){
            elems[c].value = elem;
            elems[c].type = SlotType::FILLED;
            numElements++;
            return true;
        }
        else if(elems[c].type == SlotType::TOMBSTONE){
            p = c;
            for(int j = i; j < numSlots ; j++){
                int c1 = (s + j) % numSlots;
                if(elems[c1].type == SlotType::FILLED && elems[c1].value == elem)
                    return false;
            }
            elems[c].value = elem;
            elems[c].type = SlotType::FILLED;
            numElements++;
            return true;
        }
    }
    return false;
}

。我是墓碑僵尸。。。。。就是坑次坑次搞半天发现我最后禁用的测试案例没开。。（这个时候以为自己写的是错的就放弃去想其他办法了。实际上面for循环那个可以通过测试，虽然说也是O(n^2)的复杂度然后改半天改成下面。虽然期间也有我的逆天逻辑链条。。

`This is linear probing HashTable.`

cpp

bool LinearProbingHashTable::insert(const string& elem) {
    /* TODO: Delete this comment and the next lines, then implement this function. */
    if(numElements == numSlots) return false;
    int s = hashFn(elem);
    int p = -1;
    for(int i = 0; i < numSlots; i++){
        int c = (s + i) % numSlots;

        if(elems[c].type == SlotType::FILLED && elems[c].value == elem)
            return false;

        if(p == -1 && elems[c].type == SlotType::TOMBSTONE)
            p = c;

        if(elems[c].type == SlotType::EMPTY){
            int z = (p != -1)? p : c;
            elems[z].value = elem;
            elems[z].type = SlotType::FILLED;
            numElements++;
            return true;
        }

    }


    if(p != -1 ){
        elems[p].value = elem;
        elems[p].type = SlotType::FILLED;
        numElements++;
        return true;
    }
    return false;
}

`RobinHood HashTable`

其实从表面机制实现起来感觉甚至比上一个线性哈希要容易，但是实际上已经被自己和claude逼疯，正好闲下来整理一下（实际代码是昨天水课快魔女化时弄完，逐渐失去对算法的兴趣（目移。

cpp

bool RobinHoodHashTable::remove(const string& elem) {
    int dpos = -1;
    for (int i = 0; i < numSlots; i++) {
        if (elems[i].distance != EMPTY_SLOT && elems[i].value == elem) {
            dpos = i;
            break;
        }
    }
    if (dpos == -1) return false;

    int c = dpos;
    while (true) {
        int n = (c + 1) % numSlots;

        if (elems[n].distance == EMPTY_SLOT || elems[n].distance == 0)
            break;

        elems[c] = elems[n];
        elems[c].distance--;

        c = n;
    }

    elems[c].distance = EMPTY_SLOT;
    numElements--;
    return true;
}

i think。。

11.05

下去去开了A8发现刚开始有些rpg味道，，简单指针+if-else吗？...还没去细化因为写着写着睡着了

assignment5 combine ​

binary heap/heap ​

hashtable ​

This is linear probing HashTable. ​