TOP 100 57 - 64

169. 多数元素

我的思路1

sort，然后取[n / 2] 位置的，就是大于1/2个数的元素

我的思路2

使用哈希表

unordered_map<int, int> um;
for (int i = 0; i < nums.size(); ++i) {
    if (!um.count(nums[i])) {
        um[nums[i]] = 1;
    }
    else {
        um[nums[i]]++;
    }
}
for (auto& iter : um) {
    if (iter.second > nums.size() / 2) {
        return iter.first;
    }
}
return -1;

其实可以在第一个for循环内就完成cnt的事.完成简化,也不需要使用count.简化如下

for (int i = 0; i < nums.size(); ++i) {
    um[nums[i]]++;
    if (um[nums[i]] > nums.size() / 2) {
        return nums[i];
    }
}

题解思路1

摩尔投票算法

int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums.size(); ++i) {
    if (count == 0) {
        candidate = nums[i];
    }
    if (nums[i] == candidate) {
        count++;
    }
    else {
        count--;
    }
}
return candidate;

记一个当前值,一个当前值的count,当前值和其后一个值打架,不同count--,相同值count++.count为0时退位换新人上,个数大于n / 2的众数一定能赢到最后

198. 打家劫舍

我的思路

• 动态规划
• 滚动数组

200. 岛屿数量

我的思路

使用深度优先遍历把岛屿上的1都变成0.
计算1的数量

207. 课程表

有向图拓扑排序

题解思路1 BFS

计算入度
1.入度为0进入队列
2.将入度为0的后序节点入度减1,若为0,则push进队列
3.若队列为空,计算经由队列的元素数量,若等于coursenum,则为true
问题:如果456有环呢?
那么5的入度为2,在前驱元素的后面的元素入度减1的时候就不为0,就进不了队列,cnt就会小于coursenum,false
图里我没画箭头,箭头由上往下

vector<int> indeg(numCourses);
vector<vector<int> > edges(numCourses);

for (const auto& vec : prerequisites) {
    //当前课程的入度++;
    indeg[vec[0]]++;
    //当前课程vec[0]的被存入先修课程vec[1]的后修表中
    edges[vec[1]].push_back(vec[0]);
}
queue<int> q;
for (int i = 0; i <numCourses; ++i) {
    if (indeg[i] == 0) {
        //存入入度为0的i课程
        q.push(i);
    }
}
//设置一个计数变量看是否所有的课程都通过了队列
int cnt = 0;
while (!q.empty()) {
    cnt++;
    //取入度为0的队头
    int u = q.front();
    //遍历入度为0的课程的后面的课程,让它们的入度减一
    for (const int& v : edges[u]) {
        indeg[v]--;
        //如果入度为0,就入队列
        if (indeg[v] == 0) {
            q.push(v);
        }
    }
    //把队头给pop
    q.pop();
}
return cnt == numCourses;

215. 数组中的第K个最大元素

我的思路

sort

sort(nums.begin(), nums.end());
return nums[nums.size() - k];

我猜应该是基于快排(因为昨天刚看见)

题解思路:堆

维护动态数据的最大最小值,可以考虑堆
建立容量为k的最大值堆
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
1.建立大根堆，抛掉k - 1个nums[0],调整大根堆。最后nums[0]就是第k个最大元素
2.如何建立？ 从 (heapsize - 1) - 1)开始向前maxHeapify
3.如何maxHeapify,交换左右子节点的较大值给父节点,再对那个节点的左右子节点进行maxHeapify(节点值为之前父节点的值).