Open Timothyoung97 opened 3 months ago
Cyclic Redundancy Check (CRC32) MAC Address
Also provides details IP of:
TCP (Transmission Control Protocol) and UDP (User Datagram Protocol) are two widely used transport layer protocols in computer networks. Here are the main differences between TCP and UDP:
Connection-Oriented vs. Connectionless: TCP is a connection-oriented protocol. It establishes a connection between the sender and receiver before transmitting data, ensuring reliable and ordered delivery of data packets. UDP is a connectionless protocol. It does not establish a connection before sending data and does not guarantee delivery or order of data packets. UDP is often used for real-time applications where speed is more important than reliability.
Reliability: TCP provides reliable delivery of data. It includes features like error checking, retransmission of lost packets, and flow control to ensure all data is successfully delivered in order. UDP does not guarantee reliable delivery. It does not perform error checking or retransmission of lost packets, so it is possible for packets to be lost or arrive out of order.
Packet Structure: TCP uses a packet structure with additional headers for sequence numbers, acknowledgment numbers, checksums, and other control information to manage the connection and ensure reliability. UDP has a simpler packet structure with minimal overhead. It includes source port, destination port, length, and checksum fields, but does not include sequence numbers or acknowledgment mechanisms.
Flow Control and Congestion Control: TCP implements flow control and congestion control mechanisms to manage the rate of data transmission and avoid network congestion. UDP does not have built-in flow control or congestion control. Applications using UDP need to implement their own flow control mechanisms if necessary.
Usage: TCP is commonly used for applications that require reliable and ordered delivery of data, such as web browsing, email, file transfer (FTP), and streaming media. UDP is used for real-time applications where low latency and speed are critical, such as online gaming, video streaming, VoIP (Voice over IP), DNS (Domain Name System), and SNMP (Simple Network Management Protocol).
In summary, TCP provides reliable, ordered, and connection-oriented communication with additional overhead and mechanisms for error recovery and flow control. UDP, on the other hand, offers faster and connectionless communication with minimal overhead but lacks reliability and error recovery mechanisms. The choice between TCP and UDP depends on the specific requirements of the application, such as the importance of reliability, latency, and speed.
Here are some common examples of port numbers and their typical usage:
Port 80 (HTTP): Used for HTTP (Hypertext Transfer Protocol) traffic, which is the protocol used for serving web pages. When you access a website using a web browser, the browser communicates with the web server over port 80 by default.
Port 443 (HTTPS): Used for HTTPS (Hypertext Transfer Protocol Secure) traffic, which is the secure version of HTTP. HTTPS encrypts the data transferred between the client (browser) and the server, providing a secure communication channel. It's commonly used for online transactions, login pages, and any sensitive data transfer over the web.
Port 22 (SSH): Used for SSH (Secure Shell) protocol, which provides secure access to a remote computer over an encrypted connection. SSH is commonly used for remote administration, file transfer, and secure communication between computers.
Port 25 (SMTP): Used for SMTP (Simple Mail Transfer Protocol) traffic, which is the protocol used for sending email messages between servers. Port 25 is used by mail servers to send outgoing email messages to other mail servers.
Port 67 (DHCP): Port 67 is used by DHCP servers to receive DHCPDISCOVER and DHCPREQUEST messages from DHCP clients.
Port 68 (DHCP): Port 68 is used by DHCP clients to receive DHCPOFFER, DHCPACK, and DHCPNAK messages from DHCP servers.
Port 587 (SMTP Submission): Used for SMTP Submission, which is an alternative port for sending email messages from email clients (e.g., Outlook, Thunderbird) to mail servers. Port 587 is commonly used for sending email from email clients to mail servers with encryption and authentication.
Port 110 (POP3): Used for POP3 (Post Office Protocol version 3) traffic, which is a protocol used by email clients to retrieve email messages from a mail server. POP3 is used for downloading emails to the client's computer or device.
Port 143 (IMAP): Used for IMAP (Internet Message Access Protocol) traffic, which is another protocol used by email clients to retrieve email messages from a mail server. IMAP allows clients to manage emails on the server, sync folders, and access email from multiple devices while keeping messages on the server.
Port 3306 (MySQL): Used for MySQL database server traffic, which is a popular relational database management system. Port 3306 is used by MySQL clients to connect to the MySQL server and perform database operations.
These are just a few examples of common port numbers and their associated protocols. Different applications and services use specific port numbers for communication, and understanding these port numbers can help in network configuration and troubleshooting.
DNS(Domain Name System)记录是DNS服务器上存储的数据项,用于将域名解析为对应的IP地址或其他网络服务信息。常见的DNS记录类型包括:
这些DNS记录类型可以组合使用,以实现域名到IP地址的解析、邮件传递、服务发现等功能。通过管理DNS记录,可以控制域名的解析行为和网络服务的路由,保证网络通信的正常进行。
在浏览器中输入并按下“www.google.com”后,通常会经历以下步骤才能显示谷歌的网页:
整个过程包括了DNS解析、建立TCP连接、发送HTTP请求、服务器处理请求、接收和解析响应、页面渲染和显示页面等步骤,确保用户能够顺利访问和浏览网页内容。
游戏客户端实现用户身份验证或会话管理等功能通常涉及以下步骤和技术:
上述流程是一个简化的用户身份验证和会话管理的实现过程。实际应用中,还可能涉及到一些安全性和稳定性的考虑,比如使用HTTPS协议保证通信安全、使用加密算法保护用户密码和会话令牌、处理会话过期和异常情况等。
游戏客户端可能会使用Cookie来实现一些功能或记录一些信息,但与网站应用不同,游戏客户端通常不会使用Cookie来实现用户身份验证或会话管理等功能。下面是一些游戏客户端可能会使用的Cookie类型:
需要注意的是,游戏客户端通常不会使用Cookie来存储敏感信息,如用户密码等。对于敏感信息的处理,游戏客户端通常会使用更安全的方式,比如加密存储、安全传输等。
HTTP响应状态码是指在客户端发送请求后,服务器返回的表示请求处理结果的数字代码。状态码通常分为以下几个类别:
1xx:信息性状态码,表示请求已经接收并且服务器正在处理。 100:Continue(继续),表示客户端可以继续发送请求体。 101:Switching Protocols(切换协议),表示服务器已经理解客户端的请求,并将通过Upgrade消息头通知客户端切换协议。
2xx:成功状态码,表示服务器成功接收、理解并处理了客户端的请求。 200:OK,表示请求成功处理。 201:Created,表示请求已经成功并且服务器创建了新的资源。 204:No Content,表示服务器成功处理了请求,但没有返回任何内容。
3xx:重定向状态码,表示需要客户端采取进一步的操作来完成请求。 301:Moved Permanently,永久重定向。 302:Found,临时重定向。 304:Not Modified,客户端的缓存资源仍然有效。
4xx:客户端错误状态码,表示客户端发送的请求有误或无法完成。 400:Bad Request,客户端发送了一个错误的请求。 401:Unauthorized,请求未授权,需要进行身份验证。 403:Forbidden,服务器理解请求,但拒绝执行。 404:Not Found,请求的资源不存在。 5xx:服务器错误状态码,表示服务器在处理请求时发生了错误。
500:Internal Server Error,服务器遇到了一个未知的错误。 502:Bad Gateway,服务器作为网关或代理时从上游服务器收到了无效的响应。 503:Service Unavailable,服务器暂时无法处理请求,通常是由于过载或维护。
这些状态码在HTTP协议中有明确的规定,客户端和服务器可以根据不同的状态码进行相应的处理和反馈,以确保通信过程的正常进行和信息的正确传递。
TCP 三次握手(three-way handshake)对于建立可靠的网络连接至关重要。这个过程确保了通信双方的同步和可靠性,以下是其重要性:
总体来说,TCP 三次握手确保了通信的可靠性和顺序性,对于构建稳定的网络连接至关重要。
TCP 的四次握手(four-way handshake)是在连接关闭时的重要过程,它确保了连接的可靠关闭和资源释放。以下是四次握手的重要性:
综上所述,TCP 四次握手是确保连接可靠关闭和资源释放的重要步骤,对于网络通信的稳定性和效率至关重要。
HTTPS(Hypertext Transfer Protocol Secure)和 HTTP(Hypertext Transfer Protocol)是用于在网络上传输数据的两种协议,它们之间的主要区别包括以下几点:
综上所述,HTTPS相对于HTTP更安全、更可信,适合传输敏感数据和进行安全的网络通信。
TCP (Transmission Control Protocol) and HTTPS (Hypertext Transfer Protocol Secure) are different protocols used in computer networking, and they serve different purposes.
In summary, TCP is a lower-level protocol responsible for reliable data transmission, while HTTPS is a higher-level protocol that adds security features, including encryption, to the communication process between clients and servers, typically used in web browsing and secure online transactions.
多人网游游戏实现多人同步通常采用以下技术和策略:
综合利用这些技术和策略,多人网游可以实现较好的多人同步效果,保证玩家在游戏中获得良好的体验和互动性。
判断从服务器到客户端导致客户端接收不到更新的问题可以采取以下步骤:
通过以上方法结合调试和分析,可以逐步定位问题所在,找出导致客户端接收不到更新的具体原因,并进行相应的修复和优化。
反作弊软件是一种专门设计用于防止游戏作弊行为的软件。它们通常结合了多种技术和策略,旨在监控游戏进程、检测作弊程序,并采取相应的防御措施。下面是反作弊软件通常采取的一些技术和方法:
总的来说,反作弊软件通过监控、检测、识别和防御等多种技术手段,来防止游戏中的作弊行为,维护游戏的公平性和竞技性。这些技术通常需要不断更新和改进,以应对不断演变的作弊手段和挑战。
游戏3C是指游戏中的三个重要要素,即Character(角色)、Camera(摄像机)和Control(控制)。这些要素在游戏设计和开发中扮演着关键的角色,影响着玩家的游戏体验和游戏的可玩性。
游戏3C的设计需要综合考虑角色的特性、摄像机的视角和控制方式,以提供丰富、流畅、易于操作的游戏体验。良好的游戏3C设计可以增强游戏的沉浸感、可玩性和乐趣,是游戏开发中重要的方面之一。
对于设计一个范围性的攻击,可以使用设计模式中的命令模式(Command Pattern)来实现。命令模式可以将请求封装成一个对象,从而允许将请求的发送者和接收者解耦,同时支持对请求的参数化和队列化操作。
以下是使用命令模式设计范围性攻击的一种实现方式:
public interface Command {
void execute();
}
public class RangeAttackCommand implements Command {
private int damage;
private int range;
private List<Character> targets;
public RangeAttackCommand(int damage, int range, List<Character> targets) {
this.damage = damage;
this.range = range;
this.targets = targets;
}
@Override
public void execute() {
for (Character target : targets) {
// 对目标造成伤害
target.takeDamage(damage);
}
}
}
public class Player {
private Command rangeAttackCommand;
public void setRangeAttackCommand(Command command) {
this.rangeAttackCommand = command;
}
public void performRangeAttack() {
if (rangeAttackCommand != null) {
rangeAttackCommand.execute();
}
}
}
// 创建玩家对象和敌人列表
Player player = new Player();
List<Character> enemies = new ArrayList<>();
enemies.add(new Enemy());
enemies.add(new Enemy());
// 创建范围攻击命令并设置给玩家
Command rangeAttack = new RangeAttackCommand(50, 5, enemies);
player.setRangeAttackCommand(rangeAttack);
// 玩家发起范围攻击
player.performRangeAttack();
通过上述设计,使用命令模式可以有效地实现范围性攻击,将攻击请求和执行解耦,并支持灵活的参数化操作,提高了游戏系统的可扩展性和可维护性。
游戏变得卡顿可能有多种原因,以下从游戏引擎的角度进行分析可能的原因:
综上所述,游戏卡顿可能是由于性能瓶颈、内存管理问题、渲染优化不足、脚本执行效率低下、资源管理问题等多种因素导致的。需要通过性能分析工具和调试工具来定位具体的问题,并采取相应的优化措施来提升游戏的性能和流畅度。
在游戏引擎中判断手雷弹的攻击范围内是否包括敌人通常可以通过碰撞检测和区域检测来实现。以下是一些常见的方法:
这些方法可以结合使用,根据游戏的具体需求和场景来选择合适的检测方式。例如,在实时性要求高的游戏中,可以使用快速的碰撞检测方法;而在需要精确判断的情况下,可以使用射线检测或区域检测等方法。
ECS(Entity-Component-System)是一种游戏引擎常用的设计模式,它将游戏对象拆分成实体(Entity)、组件(Component)和系统(System),每个部分都有特定的责任和功能。以下是游戏引擎使用ECS设计的一些原因:
总的来说,游戏引擎使用ECS设计模式能够提高游戏的性能、灵活性和可维护性,适合于复杂的游戏项目开发和管理。
想象一下你正在开发一个城市建设类的游戏,其中有各种不同类型的建筑物,比如住宅区、商业区、工业区等。你可以使用ECS设计模式来管理这些建筑物。
实体(Entity): 在游戏中,每个建筑物可以作为一个实体。例如,一个住宅区实体代表一个住宅区建筑物。
组件(Component): 每种建筑物都有不同的属性和特征,这些可以表示为组件。比如,建筑物可以有“位置”组件表示其在游戏世界中的坐标位置,还可以有“生产力”组件表示其每天产生的资源数量。
系统(System): 系统负责管理组件和处理游戏逻辑。比如,你可以有一个“建筑物管理系统”,它负责管理所有建筑物的生命周期、资源产出、交互等。另外,你可以有一个“交互系统”,负责处理玩家与建筑物的交互,比如点击建筑物显示详细信息、升级建筑物等。
通过ECS设计模式,你可以轻松地添加新的建筑物类型或调整现有的建筑物属性,而不会影响其他部分的代码。比如,你可以添加一个新的“公园”建筑物类型,只需要创建对应的实体并添加相应的组件即可,而无需修改现有的系统代码。
这样的设计使得游戏开发更加灵活、可扩展,同时也提高了代码的可维护性和可读性,适用于需要管理大量复杂实体和交互的游戏项目。
手游通常不使用延迟渲染(Deferred Rendering)的主要原因是出于性能和资源管理的考虑。延迟渲染是一种高级的渲染技术,它能够处理大量的光照和材质细节,但在移动设备上实现延迟渲染可能存在以下挑战:
因此,为了在移动设备上获得更好的性能和用户体验,手游通常会选择更轻量级的渲染技术,如提前渲染(Forward Rendering)、简化的光照模型、减少渲染通道等,以确保游戏在移动设备上运行流畅且效果良好。
Rendering Techniques used in Genshin Impact For Console https://www.docswell.com/s/UnityJapan/KWRPQ5-210617-unity-dojo20211mihoyozhenzhongyi#p1
Instanced Rendering(实例化渲染)是一种用于优化渲染性能的技术,特别适用于需要大量重复对象的场景,比如在游戏中大量相同模型的渲染。
实例化渲染的优化性能主要体现在以下几个方面:
减少绘制调用: 实例化渲染通过将多个相同的对象合并为一个批次进行渲染,减少了绘制调用的次数。传统的渲染方式可能需要为每个对象进行单独的绘制调用,而实例化渲染可以将多个对象合并为一个绘制调用,减少了CPU到GPU之间的通信开销和调用次数。
减少顶点数据传输: 实例化渲染可以通过使用实例化数组来存储对象的位置、旋转、缩放等信息,而不是为每个对象单独传输顶点数据。这样可以减少GPU对于顶点数据的读取和传输开销,提高了渲染效率。
合并渲染状态: 实例化渲染可以将多个对象的渲染状态合并为一个批次进行渲染,如材质、纹理、光照等。这样可以减少渲染状态的切换和设置开销,提高了渲染效率。
利用硬件优化: 实例化渲染是现代GPU硬件支持的特性,可以充分利用硬件的并行处理能力。GPU可以同时处理多个实例化对象的渲染指令,提高了渲染效率和吞吐量。
总的来说,实例化渲染通过减少绘制调用、顶点数据传输、渲染状态切换等开销,充分利用GPU硬件的并行处理能力,从而优化了渲染性能,特别适用于大规模重复对象的渲染场景,如森林中的树木、城市中的建筑等。
前置++的操作顺序是先执行递增操作,然后再返回递增后的值。
class MyClass {
public:
MyClass& operator++() {
// 前置++操作,先递增值,再返回递增后的对象
++value;
return *this;
}
private:
int value;
};
MyClass obj;
++obj; // 使用前置++,递增obj的值
后置++的操作顺序是先返回当前值,然后再执行递增操作。
class MyClass {
public:
MyClass operator++(int) {
// 后置++操作,先返回当前对象的值,再递增值
MyClass temp = *this;
++value;
return temp;
}
private:
int value;
};
MyClass obj;
obj++; // 使用后置++,返回obj的值,然后递增obj的值
语法形式为const int* ptr
或int const* ptr
,表示ptr是一个指向常量int的指针,可以用来指向不同的int变量,但不能通过ptr修改指向的int变量的值。
const int* ptrToConst; // Pointer to a constant integer
int num = 10;
ptrToConst = # // Allowed: pointer points to the constant integer 'num'
*ptrToConst = 20; // Not allowed: trying to modify the constant integer
A constant pointer is declared using the const keyword after the asterisk (*) in the pointer declaration. It means that the pointer itself is constant, and once initialized to point to a memory location, it cannot be modified to point to another location.
int* const constPtr; // Constant pointer to an integer
int num1 = 10, num2 = 20;
constPtr = &num1; // Allowed: constant pointer initialized to point to 'num1'
constPtr = &num2; // Not allowed: cannot change the constant pointer to point to 'num2'
*constPtr = 30; // Allowed: modifying the value at the memory location pointed by constPtr
Const Member Functions and Const Objects: When a member function is declared as const, it indicates that the function does not modify the state of the object on which it is called. This is particularly useful when working with const objects, as it ensures that calling a const member function won't change the object's state.
Const-Correctness: Using const with member functions helps enforce const-correctness in your codebase. It makes the intent clear that certain functions are meant to be used with const objects and should not modify object state.
Accessing Data Members: Inside a const member function, you can access data members of the object but cannot modify them unless they are declared as mutable. This ensures that the object's state remains unchanged when calling const member functions.
class MyClass {
private:
int value;
public:
// Non-const member function
void setValue(int newValue) {
value = newValue;
}
// Const member function to get the value
int getValue() const {
return value;
}
};
int main() {
const MyClass obj; // Creating a const object
// Calling a const member function on a const object is allowed
int val = obj.getValue(); // This is fine, as getValue() is const
// obj.setValue(10); // Error: setValue() is not const and cannot be called on a const object
return 0;
}
Read-only Access Guarantee. Declaring a member function as const indicates that the function does not modify the object's state. It promises that the function will not change any non-static data members of the class or call any non-const member functions.
Const member functions can be called on const objects. This allows const objects to access member functions that do not modify the object's state.
class MyClass {
public:
int getValue() const {
// This function promises not to modify any data members
return value;
}
private:
int value;
};
const MyClass obj;
int val = obj.getValue(); // Allowed, because getValue() is declared const
Declaring member functions as const helps in detecting accidental modifications to const objects or const references, as the compiler will generate an error if a const member function attempts to modify the object.
class MyClass {
public:
void setValue(int newValue) const {
// Error: const member function cannot modify data members
value = newValue; // Compiler error
}
private:
int value;
};
In object-oriented programming with C++ and similar languages, virtual functions and virtual tables (vtables) play a crucial role in implementing polymorphism. Here's an explanation in English:
The memory layout of a subclass instance includes the following components:
In summary, virtual functions and vtables allow for runtime polymorphism by enabling dynamic dispatch of function calls based on the actual object type. The vptr in subclass instances points to the vtable, which contains function pointers for virtual functions, facilitating the correct execution of overridden functions in derived classes.
https://pabloariasal.github.io/2017/06/10/understanding-virtual-tables/
Note that vtables exist at the class level, meaning there exists a single vtable per class, and is shared by all instances.
when a call to a virtual function on an object is performed, the vpointer of the object is used to find the corresponding vtable of the class. Next, the function name is used as index to the vtable to find the correct (most specific) routine to be executed. Done!
#include <iostream>
class Base
{
public:
~Base()
{
std::cout << "Destroying base" << std::endl;
}
};
class Derived : public Base
{
public:
Derived(int number)
{
some_resource_ = new int(number);
}
~Derived()
{
std::cout << "Destroying derived" << std::endl;
delete some_resource_;
}
private:
int* some_resource_;
};
int main()
{
Base* p = new Derived(5);
delete p;
}
// result
// > Destroying base
Making Base’s destructor virtual will result in the expected behavior:
// > Destroying derived
// > Destroying base
In summary, the key differences in space distribution between std::vector and std::list are:
The choice between vector and list depends on the specific requirements of the application, such as the frequency of insertions, deletions, and element access operations.
When a std::vector in C++ needs to expand its capacity to accommodate more elements, it follows a process known as reallocation and growth strategy. Here's an explanation in English of how std::vector expands:
In summary, the space complexity of std::unordered_map is typically O(n) in the worst case, but it can be more efficient in practice due to its hash table implementation, which aims to distribute elements evenly across buckets to optimize memory usage and access times.
class A
{
public:
int &x;
};
class A {
public:
int& x = someInteger; // Initialized at the point of declaration
};
Leetcode: Longest connecting sets of words, last letter must be the same as the first letter of the other word.
https://www.geeksforgeeks.org/write-a-function-to-get-the-intersection-point-of-two-linked-lists/
[Common] Use hash map
or
Find the intersection point using the difference in node counts
#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Function to get the length of a linked list
int getLength(ListNode* head) {
int length = 0;
ListNode* current = head;
while (current) {
length++;
current = current->next;
}
return length;
}
// Function to advance a linked list pointer by a given number of steps
void advanceList(ListNode*& head, int steps) {
while (steps > 0 && head) {
head = head->next;
steps--;
}
}
// Function to check if two linked lists intersect
bool doLinkedListsIntersect(ListNode* headA, ListNode* headB) {
int lengthA = getLength(headA);
int lengthB = getLength(headB);
// Advance the longer list's pointer to make both lists equal in length
if (lengthA > lengthB) {
advanceList(headA, lengthA - lengthB);
} else if (lengthB > lengthA) {
advanceList(headB, lengthB - lengthA);
}
// Compare nodes in both lists for intersection
while (headA && headB) {
if (headA == headB) {
// Nodes match, intersection found
return true;
}
headA = headA->next;
headB = headB->next;
}
// No intersection found
return false;
}
int main() {
// Create linked list 1: 1 -> 2 -> 3 -> 4 -> 5
ListNode* list1 = new ListNode(1);
list1->next = new ListNode(2);
list1->next->next = new ListNode(3);
list1->next->next->next = new ListNode(4);
list1->next->next->next->next = new ListNode(5);
// Create linked list 2: 6 -> 7 -> 8
ListNode* list2 = new ListNode(6);
list2->next = new ListNode(7);
list2->next->next = new ListNode(8);
// Set intersection point: list1 intersects with list2 at node with value 4
list2->next->next->next = list1->next->next->next;
if (doLinkedListsIntersect(list1, list2)) {
std::cout << "Linked lists intersect.\n";
} else {
std::cout << "Linked lists do not intersect.\n";
}
return 0;
}
#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Function to check if a linked list has a cycle and find the entrance of the cycle
ListNode* detectCycle(ListNode* head) {
if (!head || !head->next) {
return nullptr; // No cycle if the list is empty or has only one node
}
ListNode* slow = head;
ListNode* fast = head;
bool hasCycle = false;
// Move slow pointer by one step and fast pointer by two steps until they meet or fast reaches the end
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
hasCycle = true; // Cycle detected
break;
}
}
// If there's no cycle, return nullptr
if (!hasCycle) {
return nullptr;
}
// Reset slow pointer to head and move both pointers by one step until they meet at the entrance of the cycle
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // Return the node where the cycle starts (entrance of the cycle)
}
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = head->next; // Create a cycle
ListNode* cycleEntrance = detectCycle(head);
if (cycleEntrance) {
std::cout << "Linked list has a cycle, entrance at value: " << cycleEntrance->val << std::endl;
} else {
std::cout << "Linked list does not have a cycle.\n";
}
return 0;
}
Underlying Data Structure:
Ordering:
Performance:
Usage Scenarios:
红黑树 (Red-Black Tree):
哈希表 (Hash Table, 哈希映射/哈希表):
https://youtu.be/qvZGUFHWChY?si=nD16HTRWNQBMyxs6
红黑树在插入一个新节点时,需要进行一系列的调整操作,以维护红黑树的性质。下面是红黑树插入操作的大致步骤和调整过程:
下面是红黑树插入操作的详细调整过程:
Color new node to black
Rotate in opposite direction
Rotate in opposite direction
Rotation is O(1) operations, because we are simply manipulating pointers.
调整过程会根据具体情况进行不同的操作,保证插入后的红黑树依然满足红黑树的五个性质:
(1) 每个节点是红色或黑色。 (2) 根 (root) 节 (leaf) 点是黑色。 (3) 每个叶子节点(NIL节点)都是黑色。 (4) 每个红色节点的两个子节点都是黑色(不能有两个相邻的红色节点)。 (5) 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点(黑色平衡性)。
这些调整操作保证了红黑树的平衡性和性质,使得红黑树在插入和删除操作后依然保持高效的查找性能。
当使用 std::vector 容器进行不断的 push_back 操作导致容器不断扩容,并且之后全部进行 pop_back 操作以清空容器时,容器的多余空间不会立即回收,而是由容器自行管理,可能会保留一部分多余空间以便之后的 push_back 操作不需要频繁的重新分配内存。这是为了提高性能,避免频繁的内存分配和释放所带来的开销。
具体来说,std::vector 会保留一部分预留空间(capacity),这个预留空间可以容纳额外的元素,以便之后的插入操作不需要重新分配内存。当容器的元素数量减少到一定程度时,并不会立即释放多余的空间,而是保留在容器内部,以备将来的插入操作使用。
如果需要手动释放容器的多余空间,可以使用 shrink_to_fit 方法。这个方法会要求容器将多余的预留空间释放掉,使得容器的大小与容器中元素的数量相匹配。但是需要注意的是,shrink_to_fit 并不是必然立即回收多余空间的操作,具体回收的效果取决于标准库的实现和具体情况。
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
// 不断进行 push_back 操作
for (int i = 0; i < 1000; ++i) {
vec.push_back(i);
}
std::cout << "Capacity after push_back: " << vec.capacity() << std::endl;
// 清空容器
vec.clear();
std::cout << "Capacity after clear: " << vec.capacity() << std::endl;
// 使用 shrink_to_fit 方法释放多余空间
vec.shrink_to_fit();
std::cout << "Capacity after shrink_to_fit: " << vec.capacity() << std::endl;
return 0;
}
在上面的示例中,vec.shrink_to_fit() 调用之后,容器会尝试释放多余的预留空间,使得容器的大小与元素数量相匹配。但是请注意,shrink_to_fit 并不保证一定会回收多余空间,具体效果取决于标准库的实现和内存管理策略。
Heap is sometimes called binary heap / nearly complete binary tree
Heap represented as an array, note that usually heap's root is placed at index 1
Max-Heapify, O(log n), height of the binary tree
i
is smaller than its left and right childbuild-max-heap, O(n)
Hash collision resolution is the process of handling situations where two or more keys hash to the same index in a hash table. This collision can occur due to the finite range of hash values compared to the potentially infinite set of keys. There are several techniques to resolve hash collisions:
Axis Aligned
#include <iostream>
struct Point {
int x;
int y;
};
struct Rectangle {
Point topLeft;
Point bottomRight;
};
bool doRectanglesOverlap(Rectangle rect1, Rectangle rect2) {
// If one rectangle is on the left side of the other
if (rect1.bottomRight.x < rect2.topLeft.x || rect2.bottomRight.x < rect1.topLeft.x)
return false;
// If one rectangle is above the other
if (rect1.bottomRight.y < rect2.topLeft.y || rect2.bottomRight.y < rect1.topLeft.y)
return false;
// Rectangles overlap
return true;
}
int main() {
Rectangle rect1 = {{1, 4}, {5, 1}};
Rectangle rect2 = {{3, 6}, {7, 2}};
if (doRectanglesOverlap(rect1, rect2)) {
std::cout << "Rectangles overlap.\n";
} else {
std::cout << "Rectangles do not overlap.\n";
}
return 0;
}
Non Axis Aligned
#include <iostream>
#include <algorithm>
struct Point {
int x;
int y;
};
struct Rectangle {
Point topLeft;
Point bottomRight;
};
bool doRectanglesOverlap(Rectangle rect1, Rectangle rect2) {
// Check if one rectangle is to the left of the other
if (rect1.bottomRight.x < rect2.topLeft.x || rect2.bottomRight.x < rect1.topLeft.x)
return false;
// Check if one rectangle is above the other
if (rect1.bottomRight.y < rect2.topLeft.y || rect2.bottomRight.y < rect1.topLeft.y)
return false;
// Check for overlap in x and y directions
// Project rectangles onto x-axis and check for overlap
bool xOverlap = (std::max(rect1.topLeft.x, rect2.topLeft.x) <= std::min(rect1.bottomRight.x, rect2.bottomRight.x));
// Project rectangles onto y-axis and check for overlap
bool yOverlap = (std::max(rect1.topLeft.y, rect2.topLeft.y) <= std::min(rect1.bottomRight.y, rect2.bottomRight.y));
// If both xOverlap and yOverlap are true, rectangles overlap
return xOverlap && yOverlap;
}
int main() {
Rectangle rect1 = {{1, 4}, {5, 1}};
Rectangle rect2 = {{3, 6}, {7, 2}};
if (doRectanglesOverlap(rect1, rect2)) {
std::cout << "Rectangles overlap.\n";
} else {
std::cout << "Rectangles do not overlap.\n";
}
return 0;
}
struct Node {
int key;
int val;
Node *next;
Node *prev;
Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr) {}
};
class LRUCache {
public:
int capacity;
unordered_map<int, Node*> dic;
Node *head = new Node(-1, -1);
Node *tail = new Node(-1, -1);
LRUCache(int capacity) {
this->capacity = capacity;
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (dic.find(key) == dic.end()) {
return -1;
}
Node *node = dic[key];
remove(node);
add(node);
return node->val;
}
void put(int key, int value) {
if (dic.find(key) != dic.end()) {
Node *oldNode = dic[key];
remove(oldNode);
}
Node *node = new Node(key, value);
dic[key] = node;
add(node);
if (dic.size() > capacity) {
Node *nodeToDelete = head->next;
remove(nodeToDelete);
dic.erase(nodeToDelete->key);
}
}
void add(Node *node) {
Node *previousEnd = tail->prev;
previousEnd->next = node;
node->prev = previousEnd;
node->next = tail;
tail->prev = node;
}
void remove(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
Round 2
Graphics:
C++:
Algo:
MiHoYo has developed several notable games, including:
These games showcase MiHoYo's range in genres, from action-packed adventures to puzzle-solving and romance simulations.
The development pipeline for games typically involves several stages, each with specific tasks and roles. Here's a general overview:
This issue comprises of some preparation contents made for interviews