前K个高频元素 (掌握程度：低) [面试未做出]#
想到是桶排序了，但是具体的部分未实现出来，然后面试官还不知道这个解法，下去还是得重点看一下
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
int maxCnt = 0;
for (int x : nums) {
cnt[x]++;
maxCnt = max(maxCnt, cnt[x]);
}
vector<vector<int>> buckets(maxCnt + 1);
for (auto& [x, count] : cnt) {
buckets[count].push_back(x);
}
vector<int> ans;
for (int i = maxCnt; i >= 0 && ans.size() < k; i--) {
for (int num : buckets[i]) {
ans.push_back(num);
if (ans.size() == k) break;
}
}
return ans;
}
};func topKFrequent(words []string, k int) []int {
feq := map[string]int{}
maxCnt := 0
for _, word := range words {
feq[word]++
maxCnt = max(maxCnt, feq[word])
}
buckets := make([][]string, maxCnt + 1)
for word, cnt := range feq {
buckets[cnt] = append(buckets[cnt], word)
}
res := []string{}
for i := maxCnt; i >= 0 && len(res) < k; i-- {
for _, word := range buckets[i] {
res = append(res, word)
if len(res) == k {
break
}
}
}
return res;
}排序链表 (掌握程度： 中) 面试边界处理没处理好导致挂#
package main
import (
"fmt"
)
type ListNode struct {
val int
next *ListNode
}
func merge2List(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for (l1 != nil && l2 != nil) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next
} else {
cur.next = l2
l2 = l2.next
}
cur = cur.next
}
if (l1 != nil) {
cur.next = l1
} else {
cur.next = l2
}
return dummy.next
}
func sortList(head *ListNode) *ListNode {
if (head == nil || head.next == nil) {
return nil
}
fast := head;
slow := head;
for (fast != nil && fast.next != nil) {
fast = fast.next.next
slow = slow.next
}
newHead := slow.next;
slow.next = nil;
left := sortList(head)
right := sortList(newHead)
return merge2List(left, right)
}
func printList(head *ListNode) {
cur := head
for (cur != nil) {
fmt.Println(cur.val)
cur = cur.next
}
}
func main() {
node1 := &ListNode{
val: -1,
next: nil,
}
node2 := &ListNode{
val: 5,
next: nil,
}
node3 := &ListNode{
val: 3,
next: nil,
}
node4 := &ListNode{
val: 4,
next: nil,
}
node5 := &ListNode{
val: 0,
next: nil,
}
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
head := sortList(node1)
printList(head)
fmt.Printf("%s", "hello world")
}#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 合并两个有序链表
ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* cur = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy.next;
}
// 归并排序
ListNode* sortList(ListNode* head) {
if (!head || !head->next) {
return head;
}
// 快慢指针找中点
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next;
slow->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
return mergeTwoList(left, right);
}
// 打印链表
void printList(ListNode* head) {
while (head) {
cout << head->val;
if (head->next) cout << " ";
head = head->next;
}
cout << endl;
}
int main() {
int n;
cin >> n;
if (n == 0) return 0;
ListNode* head = nullptr;
ListNode* tail = nullptr;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ListNode* node = new ListNode(x);
if (!head) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
head = sortList(head);
printList(head);
return 0;
}二叉搜索树中第 K 小的元素 (掌握程度：低) 这么简单的一道题都错了，全部都写来了中序遍历寻找，结果因为k没有引用导致挂了#
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int dfs(TreeNode* node, int& k) {
if (node == nullptr) return 0;
int left = dfs(node->left, k);
if (left != 0) return left;
k--;
if (k == 0) return node->val;
return dfs(node->right, k);
}
int BSTkthSmallest(TreeNode* root, int k) {
return dfs(root, k);
}
int main() {
// char str[3];
// std::cin>>str;
// 3
// 1 5
std::cout << "hello world" << std::endl;
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(1);
root->right = new TreeNode(4);
cout << BSTkthSmallest(root, 2);
return 0;
}