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。

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
这15个Vue指令，让你的项目开发爽到爆

这15个Vue指令，让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件，按住 Control 和回车键再显示它吗？小菜一碟： <template
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
使用SecondaryNameNode恢复NameNode的数据

使用SecondaryNameNode恢复NameNode的数据

1）需求： NameNode进程挂了并且存储的数据也丢失了，如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2）故障模拟 （1）kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 （2）删除NameNode存储的数据（/opt/module/hadoop-3.1.4/data/tmp/dfs/na
阅读更多...
Hadoop数据压缩使用介绍

Hadoop数据压缩使用介绍

一、压缩原则 （1）运算密集型的Job，少用压缩 （2）IO密集型的Job，多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1）为了支持多种压缩/解压缩算法，Hadoop引入了编码/解码器 2）要在Hadoop中启用压缩，可以配置如下参数
阅读更多...
Makefile简明使用教程

Makefile简明使用教程

文章目录 规则makefile文件的基本语法：加在命令前的特殊符号：.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具，常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2