15道使用频率极高的基础算法题

2024-06-05 08:48
文章标签 算法 基础 使用 15 频率 极高

本文主要是介绍15道使用频率极高的基础算法题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;

合并排序一般的思路都是创建一个更大数组C，刚好容纳两个数组的元素，先是一个while循环比较，将其中一个数组A比较完成，将另一个数组B中所有的小于前一个数组A的数及A中所有的数按顺序存入C中，再将A中剩下的数存入C中，但这里是已经有一个数组能存下两个数组的全部元素，就不用在创建数组了，但只能从后往前面存，从前往后存，要移动元素很麻烦。

void MergeArray(int a[], int alen, int b[], int blen)
{int len = alen + blen - 1;alen--;blen--;while (alen >= 0 && blen >= 0){if (a[alen] >= b[blen]){a[len--] = a[alen--];}else{a[len--] = b[blen--];}}while (alen >= 0){a[len--] = a[alen--];}while (blen >= 0){a[len--] = b[blen--];}
}int main()
{int a[10] = {1,3,5,7,9};int b[5] = {1,4,6,8,10};MergeArray(a, 5, b, 5);for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){cout<<a[i]<<" ";}
}

2、合并两个单链表;

struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};ListNode* MergeList(ListNode *head1, ListNode *head2)
{if (head1 == NULL){return head2;}if (head2 == NULL){return head1;}ListNode *head; //新链表头结点if (head1->val <= head2->val){head = head1;head1 = head1->next;}else{head = head2;head2 = head2->next;}ListNode *pre = head;while (head1 != NULL && head2 != NULL){if (head1->val <= head2->val){pre->next = head1;head1 = head1->next;}else{pre->next = head2;head2 = head2->next;}pre = pre->next;}if (head1 != NULL){pre->next = head1;}if (head2 != NULL){pre->next = head2;}return head;
}int main()
{ListNode *head1 = new ListNode(0);ListNode *head2 = new ListNode(1);ListNode *cur1 = head1;ListNode *cur2 = head2;for (int i = 2; i < 10; i++){ListNode *newnode = new ListNode(i);if (i & 1){cur2->next = newnode;cur2 = newnode;}else{cur1->next = newnode;cur1 = newnode;}}ListNode *head = MergeList(head1, head2);ListNode *temp = head;while (temp != NULL){cout<<temp->val<<" ";temp = temp->next;}
}

3、倒序打印一个单链表;

①递归实现，先递归在打印就变成倒序打印了，如果先打印在调用自己就是顺序打印了。
②借助栈来实现。

struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};void reversePrintNode(ListNode *head)
{if (head != NULL){reversePrintNode(head->next);cout<<head->val<<" ";}
}void reversePrintNode2(ListNode *head)
{stack<ListNode*> nodes;while (head != NULL){nodes.push(head);head = head->next;}while (!nodes.empty()){cout<<nodes.top()->val<<" ";nodes.pop();}
}int main()
{ListNode *head = new ListNode(0);ListNode *cur = head;for (int i = 1; i < 10; i++){ListNode *newnode = new ListNode(i);cur->next = newnode;cur = cur->next;}reversePrintNode2(head);
}

4、给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;

#include <iostream>
using namespace std;struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};void printList(ListNode *head)
{while (head != NULL){cout<<head->val<<" ";head = head->next;}cout<<endl;
}void dropList(ListNode *head)
{if (head == NULL) return;ListNode *temp;while (head != NULL){temp = head->next;delete head;head = temp;}
}ListNode* deleteNode(ListNode *head, ListNode *del)
{if (head == NULL || del == NULL){return head;}if (head == del){ListNode *temp = head->next;delete head;head = temp;}else if (del->next != NULL){ListNode *next = del->next;del->val = next->val;del->next = next->next;delete next;}else{ListNode *cur = head;while (cur != NULL && cur->next != del){cur = cur->next;}if (cur != NULL){delete del;cur->next = NULL;}}return head;
}int main()
{for (int i = 0; i < 10; i++){ListNode **nodes = new ListNode*[10];nodes[0] = new ListNode(0);ListNode *cur = nodes[0];for (int j = 1; j < 10; j++){nodes[j] = new ListNode(j);nodes[j-1]->next = nodes[j];}ListNode *head = nodes[0];ListNode *newhead = deleteNode(head, nodes[i]);cout<<"删除节点"<<i<<"后的结果: ";printList(newhead);dropList(newhead);delete [] nodes;}
}

5、找到链表倒数第K个节点;

通过两个指针，两个指针都指向链表的开始，一个指针先向前走K个节点，然后再以前向前走，当先走的那个节点到达末尾时，另一个节点就刚好与末尾节点相差K个节点。

#include <iostream>
using namespace std;struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};void printList(ListNode *head)
{while (head != NULL){cout<<head->val<<" ";head = head->next;}cout<<endl;
}void dropList(ListNode *head)
{if (head == NULL) return;ListNode *temp;while (head != NULL){temp = head->next;delete head;head = temp;}
}ListNode* findKthToTail(ListNode *head, int k)
{if (head == NULL || k == 0){return NULL;}ListNode *temp = head;for (int i = 0; i < k; i++){if (temp != NULL){temp = temp->next;}else{return NULL;}}ListNode *kNode = head;while (temp != NULL){temp = temp->next;kNode = kNode->next;}return kNode;
}int main()
{ListNode *head = new ListNode(0);ListNode *cur = head;for (int i = 1; i < 10; i++){ListNode *newnode = new ListNode(i);cur->next = newnode;cur = newnode;}cout<<findKthToTail(head, 1)->val<<endl;dropList(head);
}

6、反转单链表;

见博文递归与非递归反转链表

7、通过两个栈实现一个队列;

#include <iostream>
#include <stack>
using namespace std;template<class T>
class CQueue
{
public:void push(T& t);void pop();T& top();int size();
private:stack<T> s1;stack<T> s2;void gather(stack<T>& s1, stack<T>& s2);
};template<class T> void CQueue<T>::push(T& t)
{gather(s1, s2);s1.push(t);
}template<class T> void CQueue<T>::pop()
{gather(s2, s1);s2.pop();
}template<class T> T& CQueue<T>::top()
{gather(s2, s1);T& t = s2.top();return t;
}template<class T> int CQueue<T>::size()
{return s1.size() + s2.size();
}template<class T> void CQueue<T>::gather(stack<T>& s1, stack<T>& s2)
{while(!s2.empty()){s1.push(s2.top());s2.pop();}
}int main()
{CQueue<int> q;for (int i = 0; i < 10; i++){q.push(i);}while (q.size() > 0){cout<<q.top()<<" ";q.pop();}
}

8、二分查找;

int binarySearch(int a[], int len, int val)
{int begin = 0;int end = len - 1;int mid = (begin + end) / 2;while (begin <= end){if (a[mid] > val){end = mid - 1;}else if(a[mid] < val){begin = mid + 1;}else{return mid;}mid = (begin + end) / 2;}return -1;
}int main()
{int a[] = {1,2,3,4,5,6,7,8,9};cout<<binarySearch(a, 9, 1);
}

9、快速排序
详细介绍见博文九大排序算法总结

void quickSort(int a[], int left, int right)
{if(left >= right){return;}int val = a[left];int begin = left;int end = right;while (begin < end){while(begin < end && a[end] >= val){end--;}a[begin++] = a[end];while(begin < end && a[begin] <= val){begin++;}a[end--] = a[begin];}a[begin] = val;quickSort(a, left, begin - 1);quickSort(a, end + 1, right);
}int main()
{int a[] = {2,3,8,9,6,4,5,7,1,0};int len = sizeof(a)/sizeof(a[0]);quickSort(a, 0, len - 1);for(int i = 0; i < len; i++){cout<<a[i]<<" ";}
}

10、获得一个int型的数中二进制中1的个数;

int find1count(int n)
{int count = 0;while (n){n &= (n - 1);count++;}return count;
}

11、输入一个数组，实现一个函数，让所有奇数都在偶数前面;

void RecordOddEven(int a[],int len)
{int i = 0;int j = len - 1;while (i < j){while (i < j && a[i] % 2 == 1){i++;}while (i < j && a[j] % 2 == 0){j--;}swap(a[i], a[j]);i++;j--;}
}

12、判断一个字符串是否是另一个字符串的子串;

KMP算法，详见博文KMP算法字符串匹配。

#include <iostream>
using namespace std;void prefixFun(char *pattern, int *prefun)
{int len = 0;while ('\0' != pattern[len]){len++;}int count = 0;prefun[1] = 0;for (int i = 2; i <= len; i++){while (count > 0 && pattern[count] != pattern[i - 1]){count = prefun[count];}if (pattern[count] == pattern[i - 1]){count++;}prefun[i] = count;}
}void KMPstrMatching(char *target, char *pattern)
{int tarLen = 0;while ('\0' != target[tarLen]){tarLen++;}int patLen = 0;while ('\0' != pattern[patLen]){patLen++;}int *prefun = new int[patLen + 1];prefixFun(pattern, prefun);int count = 0;for (int i = 0; i < tarLen; i++){while (count > 0 && pattern[count] != target[i]){count = prefun[count];}if (pattern[count] == target[i]){count++;}if (count == patLen){cout<<"Patterns matching at index: "<<i - patLen + 1<<endl;count = prefun[count];}}delete [] prefun;
}int main()
{KMPstrMatching("abcdabababcdabcdabcabcd", "abcd");
}

13、把一个int型数组中的数字拼成一个串，这个串代表的数字最小;

先将数字转换成字符串存在数组中，在通过qsort排序，在排序用到的比较函数中，将要比较的两个字符串进行组合，如要比较的两个字符串分别是A,B，那么组合成，A+B，和B+A，在比较A+B和B+A，返回strcmp(A+B, B+A)，经过qsort这么一排序,数组就变成从小到大的顺序了，组成的数自然是最小的。

//把一个int型数组中的数字拼成一个串，是这个串代表的数组最小
#define MaxLen 10 
int Compare(const void* str1,const void* str2)
{char cmp1[MaxLen*2+1];char cmp2[MaxLen*2+1];strcpy(cmp1,*(char**)str1);strcat(cmp1,*(char**)str2);strcpy(cmp2,*(char**)str2);strcat(cmp2,*(char**)str1);return strcmp(cmp1,cmp2);
}  
void GetLinkMin(int a[],int len)
{char** str=(char**)new int[len];for (int i=0;i<len;i++){str[i]=new char[MaxLen+1];sprintf(str[i],"%d",a[i]); }qsort(str,len,sizeof(char*),Compare);for (int i=0;i<len;i++){cout<<str[i]<<" ";delete[] str[i] ;}delete[] str;
} 
void GetLinkMinTest()
{int arr[]={123,132,213,231,321,312};GetLinkMin(arr,sizeof(arr)/sizeof(int));
}

14、输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）;

递归实现，只要某个节点的两个子节点都不为空，就左右交换，让左子树交换，让右子树交换。

struct NodeT
{int value;NodeT* left;NodeT* right;NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}
};//输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）
void TreeClass(NodeT* root)
{if( root==NULL || (root->left==NULL && root->right==NULL) ) return; NodeT* tmpNode=root->left;root->left=root->right;root->right=tmpNode;TreeClass(root->left);TreeClass(root->right); 
}void PrintTree(NodeT* root)
{if(root){cout<<root->value<<" ";PrintTree(root->left);PrintTree(root->right);} 
}void TreeClassTest()
{NodeT* root=new NodeT(8);NodeT* n1=new NodeT(6);NodeT* n2=new NodeT(10);NodeT* n3=new NodeT(5);NodeT* n4=new NodeT(7);NodeT* n5=new NodeT(9);NodeT* n6=new NodeT(11);root->left=n1;root->right=n2;n1->left=n3;n1->right=n4;n2->left=n5;n2->right=n6;PrintTree(root);cout<<endl;TreeClass( root );PrintTree(root);cout<<endl;
}

15、输入两个链表，找到它们第一个公共节点;

如果两个链表有公共的节点，那么第一个公共的节点及往后的节点都是公共的。从后往前数N个节点（N=短链表的长度节点个数）,长链表先往前走K个节点（K=长链表的节点个数-N），这时两个链表都距离末尾N个节点，现在可以一一比较了，最多比较N次，如果有两个节点相同就是第一个公共节点，否则就没有公共节点。

另一种思路是借助栈，详见博文Intersection of Two Linked List

//输入两个链表，找到它们第一个公共节点
int GetLinkLength(NodeL* head)
{ int count=0;while (head){head=head->next;count++;}return count;
}NodeL* FindFirstEqualNode(NodeL* head1,NodeL* head2)
{if (head1==NULL || head2==NULL)return NULL;int len1=GetLinkLength(head1);int len2=GetLinkLength(head2);NodeL* longNode;NodeL* shortNode;int leftNodeCount;if (len1>len2){longNode=head1;shortNode=head2;leftNodeCount=len1-len2;}else{longNode=head2;shortNode=head1;leftNodeCount=len2-len1;}for (int i=0;i<leftNodeCount;i++){longNode=longNode->next;}while (longNode && shortNode && longNode!=shortNode){longNode=longNode->next;shortNode=shortNode->next;}if (longNode)//如果有公共节点，必不为NULL{return longNode;}return NULL;  
}void FindFirstEqualNodeTest()
{NodeL* head1=new NodeL(0);NodeL* head2=new NodeL(0);NodeL* node1=new NodeL(1);NodeL* node2=new NodeL(2);NodeL* node3=new NodeL(3);NodeL* node4=new NodeL(4);NodeL* node5=new NodeL(5);NodeL* node6=new NodeL(6);NodeL* node7=new NodeL(7);head1->next=node1;node1->next=node2;node2->next=node3;node3->next=node6;//两个链表相交于节点node6head2->next=node4;node4->next=node5;node5->next=node6;//两个链表相交于节点node6node6->next=node7;NodeL* node= FindFirstEqualNode(head1,head2);if (node){cout<<node->value<<endl;}else{cout<<"没有共同节点"<<endl;}
}

这篇关于15道使用频率极高的基础算法题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1032616。

相关文章

python中的显式声明类型参数使用方式

python中的显式声明类型参数使用方式

《python中的显式声明类型参数使用方式》文章探讨了Python3.10+版本中类型注解的使用,指出FastAPI官方示例强调显式声明参数类型,通过|操作符替代Union/Optional,可提升代... 目录背景python函数显式声明的类型汇总基本类型集合类型Optional and Union(py
阅读更多...
Java使用正则提取字符串中的内容的详细步骤

Java使用正则提取字符串中的内容的详细步骤

《Java使用正则提取字符串中的内容的详细步骤》：本文主要介绍Java中使用正则表达式提取字符串内容的方法,通过Pattern和Matcher类实现,涵盖编译正则、查找匹配、分组捕获、数字与邮箱提... 目录1. 基础流程2. 关键方法说明3. 常见场景示例场景1：提取所有数字场景2：提取邮箱地址4. 高级
阅读更多...
使用SpringBoot+InfluxDB实现高效数据存储与查询

使用SpringBoot+InfluxDB实现高效数据存储与查询

《使用SpringBoot+InfluxDB实现高效数据存储与查询》InfluxDB是一个开源的时间序列数据库,特别适合处理带有时间戳的监控数据、指标数据等,下面详细介绍如何在SpringBoot项目... 目录1、项目介绍2、 InfluxDB 介绍3、Spring Boot 配置 InfluxDB4、I
阅读更多...
使用Java读取本地文件并转换为MultipartFile对象的方法

使用Java读取本地文件并转换为MultipartFile对象的方法

《使用Java读取本地文件并转换为MultipartFile对象的方法》在许多JavaWeb应用中,我们经常会遇到将本地文件上传至服务器或其他系统的需求,在这种场景下,MultipartFile对象非... 目录1. 基本需求2. 自定义 MultipartFile 类3. 实现代码4. 代码解析5. 自定
阅读更多...
使用Python实现无损放大图片功能

使用Python实现无损放大图片功能

《使用Python实现无损放大图片功能》本文介绍了如何使用Python的Pillow库进行无损图片放大,区分了JPEG和PNG格式在放大过程中的特点,并给出了示例代码,JPEG格式可能受压缩影响,需先... 目录一、什么是无损放大？二、实现方法步骤1：读取图片步骤2：无损放大图片步骤3：保存图片三、示php
阅读更多...
使用Python实现一个简易计算器的新手指南

使用Python实现一个简易计算器的新手指南

《使用Python实现一个简易计算器的新手指南》计算器是编程入门的经典项目,它涵盖了变量、输入输出、条件判断等核心编程概念,通过这个小项目,可以快速掌握Python的基础语法,并为后续更复杂的项目打下... 目录准备工作基础概念解析分步实现计算器第一步：获取用户输入第二步：实现基本运算第三步：显示计算结果进
阅读更多...
python之uv使用详解

python之uv使用详解

《python之uv使用详解》文章介绍uv在Ubuntu上用于Python项目管理,涵盖安装、初始化、依赖管理、运行调试及Docker应用,强调CI中使用--locked确保依赖一致性... 目录安装与更新standalonepip 安装创建php以及初始化项目依赖管理uv run直接在命令行运行pytho
阅读更多...
C#使用Spire.XLS快速生成多表格Excel文件

C#使用Spire.XLS快速生成多表格Excel文件

《C#使用Spire.XLS快速生成多表格Excel文件》在日常开发中,我们经常需要将业务数据导出为结构清晰的Excel文件,本文将手把手教你使用Spire.XLS这个强大的.NET组件,只需几行C#... 目录一、Spire.XLS核心优势清单1.1 性能碾压：从3秒到0.5秒的质变1.2 批量操作的优雅
阅读更多...
Kotlin 枚举类使用举例

Kotlin 枚举类使用举例

《Kotlin枚举类使用举例》枚举类（EnumClasses）是Kotlin中用于定义固定集合值的特殊类,它表示一组命名的常量,每个枚举常量都是该类的单例实例,接下来通过本文给大家介绍Kotl... 目录一、编程枚举类核心概念二、基础语法与特性1. 基本定义2. 带参数的枚举3. 实现接口4. 内置属性三、
阅读更多...
Java List 使用举例(从入门到精通)

Java List 使用举例(从入门到精通)

《JavaList使用举例(从入门到精通)》本文系统讲解JavaList,涵盖基础概念、核心特性、常用实现（如ArrayList、LinkedList）及性能对比,介绍创建、操作、遍历方法,结合实... 目录一、List 基础概念1.1 什么是 List？1.2 List 的核心特性1.3 List 家族成
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2