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。

相关文章

使用Java解析JSON数据并提取特定字段的实现步骤(以提取mailNo为例)

使用Java解析JSON数据并提取特定字段的实现步骤(以提取mailNo为例)

《使用Java解析JSON数据并提取特定字段的实现步骤(以提取mailNo为例)》在现代软件开发中,处理JSON数据是一项非常常见的任务,无论是从API接口获取数据,还是将数据存储为JSON格式,解析... 目录1. 背景介绍1.1 jsON简介1.2 实际案例2. 准备工作2.1 环境搭建2.1.1 添加
阅读更多...
如何使用celery进行异步处理和定时任务(django)

如何使用celery进行异步处理和定时任务(django)

《如何使用celery进行异步处理和定时任务(django)》文章介绍了Celery的基本概念、安装方法、如何使用Celery进行异步任务处理以及如何设置定时任务,通过Celery,可以在Web应用中... 目录一、celery的作用二、安装celery三、使用celery 异步执行任务四、使用celery
阅读更多...
使用Python绘制蛇年春节祝福艺术图

使用Python绘制蛇年春节祝福艺术图

《使用Python绘制蛇年春节祝福艺术图》：本文主要介绍如何使用Python的Matplotlib库绘制一幅富有创意的“蛇年有福”艺术图,这幅图结合了数字,蛇形,花朵等装饰,需要的可以参考下... 目录1. 绘图的基本概念2. 准备工作3. 实现代码解析3.1 设置绘图画布3.2 绘制数字“2025”3.3
阅读更多...
Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单

Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单

《Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单》：本文主要介绍Springboot的ThreadPoolTaskScheduler线... 目录ThreadPoolTaskScheduler线程池实现15分钟不操作自动取消订单概要1，创建订单后
阅读更多...
Jsoncpp的安装与使用方式

Jsoncpp的安装与使用方式

《Jsoncpp的安装与使用方式》JsonCpp是一个用于解析和生成JSON数据的C++库,它支持解析JSON文件或字符串到C++对象,以及将C++对象序列化回JSON格式,安装JsonCpp可以通过... 目录安装jsoncppJsoncpp的使用Value类构造函数检测保存的数据类型提取数据对json数
阅读更多...
python使用watchdog实现文件资源监控

python使用watchdog实现文件资源监控

《python使用watchdog实现文件资源监控》watchdog支持跨平台文件资源监控,可以检测指定文件夹下文件及文件夹变动,下面我们来看看Python如何使用watchdog实现文件资源监控吧... python文件监控库watchdogs简介随着Python在各种应用领域中的广泛使用，其生态环境也
阅读更多...
Python中构建终端应用界面利器Blessed模块的使用

Python中构建终端应用界面利器Blessed模块的使用

《Python中构建终端应用界面利器Blessed模块的使用》Blessed库作为一个轻量级且功能强大的解决方案,开始在开发者中赢得口碑,今天,我们就一起来探索一下它是如何让终端UI开发变得轻松而高... 目录一、安装与配置：简单、快速、无障碍二、基本功能：从彩色文本到动态交互1. 显示基本内容2. 创建链
阅读更多...
springboot整合 xxl-job及使用步骤

springboot整合 xxl-job及使用步骤

《springboot整合xxl-job及使用步骤》XXL-JOB是一个分布式任务调度平台,用于解决分布式系统中的任务调度和管理问题,文章详细介绍了XXL-JOB的架构,包括调度中心、执行器和Web... 目录一、xxl-job是什么二、使用步骤1. 下载并运行管理端代码2. 访问管理页面，确认是否启动成功
阅读更多...
使用Nginx来共享文件的详细教程

使用Nginx来共享文件的详细教程

《使用Nginx来共享文件的详细教程》有时我们想共享电脑上的某些文件,一个比较方便的做法是,开一个HTTP服务,指向文件所在的目录,这次我们用nginx来实现这个需求,本文将通过代码示例一步步教你使用... 在本教程中，我们将向您展示如何使用开源 Web 服务器 Nginx 设置文件共享服务器步骤 0 —
阅读更多...
Java中switch-case结构的使用方法举例详解

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》：本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2