[综合] 链表--双指针--求链表倒数第k个元素

求链表倒数第k个元素 思路：可以定义两个临时指针，一个快指针，一个慢指针，使快指针领先k步，然后慢指针再走，当快指针到末尾的时候，那么慢指针的位置就是倒数第k个指针了。 ListNode*findKthtoLast(ListNode*head,intk) {if(head==NULL||k<0...

[综合] 链表--交换链表相邻的两个元素

交换链表相邻的两个元素 题目：给定一个链表，交换每个相邻的元素，最后返回新的链表节点。 ListNode*swapNodes(ListNode*head) {if(head==NULL||head->next==NULL)returnhead;ListNode*dummyNode=newLis...

[综合] 链表--两个链表相加

两个链表相加 题目：给定两个链表，链表中的每一个元素是一个整数，写一个函数返回一个新的链表，新链表是给定两个链表的和。 例如：7->1->6+5->9->2返回2->1->9 ListNode*sum(ListNode*L1,ListNode*L2) {if(L1...

[综合] 链表--Merge Two? Sorted List

融合两个有序链表 题目：Mergetwosortedlinkedlistsandreturnitasanewlist. 本文介绍两种方法. 方法1：用递归 ListNode*mergeTwoLists(ListNode*L1,ListNode*L2){if(L1==NULL)returnL2;if(...

[综合] 链表--逆序遍历链表

逆序遍历链表 模式识别：如果对靠前节点的处理必须在靠后节点之后，即倒序访问问题，则用recursion(递归)，或者等效地，stack来解决。 例题：逆序遍历链表 voidtraverse(ListNode*head){if(head==NULL)return;traverse(head->n...

[综合] 链表--Reorder List

重排序一个链表 GivenasinglylinkedlistL:L0->L1->...->Ln-1->Ln reorderitto:L0->Ln->L1->Ln-1->L2->Ln-2->... Youmustdothisin-placew...

[综合] 十大简单排序：选择排序

选择排序 思想：遍历一次数组，选择一个最小值，然后放到第一个位置，第二次遍历数组，再找到一个最小值，放入第二个位置，继续遍历数组，直到尾部，就把数组排好了。 voidswap(intarr[],inti,intj) {inttmp=arr[i];arr[i]=arr[j];arr[j]=tmp; }...

[综合] 十大简单排序：冒泡排序

冒泡排序 思想：从第一个位置开始，依次比较大小，若前面的值大，则将前值与后值交换，经过一轮的比较后，最大值就排在了末尾。由此而来，比较N轮，N是数组元素个数，那么整个数组就有序了。 voidswap(intarr[],inti,intj) {inttmp=arr[i];arr[i]=arr[j];a...

[综合] 十大排序：插入排序

插入排序及希尔排序 插入排序的思想：插入排序的思想有点类似摸扑克牌，首先抽取第一张，当做已经排好序，然后第二张，插入到已经排好序的扑克牌中，依次类推，第三张...直到最后一张。 voidinsertSort(intarr[],intlen) {for(inti=1;i<len;i++){//类...

[综合] 十大简单排序：快速排序

快速排序（分治思想） 思想：选定一个元素做中轴，一般是数组最后一个元素，从两头遍历数组，左边比中轴大的元素和右边小于等于中轴的元素对换，当左游标大于等于右游标的时候，左游标处的值一定是大于中轴值的，将左游标处的值与末尾的中轴值交换，就完成了第一次的分割，接下来，对中轴两边的数组段再次进行上述相同的处...

[综合] 十大简单排序：归并排序

归并排序 思想：先把数组中的元素拆分成两部分，使这两部分都有序，然后再合并这两部分。其中拆分成的两部分，又可以继续拆分成两部分，如此递归下去，直到不能拆分。 voidmerge(intarr[],intleftptr,intrightptr,intrightBound) {intmid=rightp...

[综合] 十大简单排序：计数排序

计数排序 思想：用一个例子来说明计数排序的思想，对N个50-59之间的整数进行排序，N可能很大。虽然数据量很大，但是取值范围却很小，我们可以利用一个数组a[10]，a[0].....a[9]对应50....59，也就是说，数据减去50作为数组的下标，例如56，那么对应的下标就是56-50=6，那么a...

[综合] 十大简单排序：桶排序

桶排序 本次介绍的这个桶排序，用的比较少，下面分析其思想。 思想：遍历数组,找到数组中的最大值和最小值,计算差值,然后选择桶的个数，有了差值和桶个数,进而可以确定每个桶的取值范围，之后再次遍历数组,将元素放入桶中,对每个桶内的元素排序,最后依次输出桶内值，如果桶用数组表示,那么数组的大小必须是原数组...

[综合] 栈和队列：实现一个栈，O(1)时间复杂度获取栈内最大元素

实现一个栈，获取栈内最大元素 题目：实现一个栈，使栈的Push、PopTop和Max的时间复杂度为O(1)，Max()将返回栈内最大的元素。 思路：用两个栈，第一个是常规栈，第二个只存储到来的元素中比栈顶大的元素。 复杂度分析：时间复杂度符合题目要求O(1)。空间复杂度最坏情况附加的stack中需要...

[综合] 栈和队列：用栈实现一个队列

用栈实现一个队列 题目：用栈实现一个队列 classQueueWithStack{private:stack<int>input;stack<int>output;public:intdequeue();//出队列voidenqueue(int);//入队列 };voidQu...

[综合] 栈和队列:用队列实现一个栈

用队列实现一个栈 题目：用两个队列实现一个栈. 思路：保持一个队列为空,一个队列有数据,插入数据时向有数的队列插，弹出数据时,将有数队列的最后一个留下，其余的挪动到空队列。 classMyStack{private:queue<int>q1;queue<int>q2;publ...

[综合] 栈和队列:Validate Parenthesis

ValidateParenthesis 前言:有一类问题有这样的特性：当前节点的解决依赖后驱节点。 对于某个当前节点，如果不能获知后驱节点，就无法得到有意义的解。 这类问题可以通过stack（或等同于stack的若干个临时变量） 解决：先将当前节点入栈，然后看其后继节点的值，直到其依赖的所有 节点都...

[综合] 栈和队列：中序遍历一个二叉树

中序遍历一个二叉树 题目：两种方式遍历给定二叉树 方法一：递归 本方法代码很简单，可见算法的精髓就在于很巧妙的解决问题，并不需要很复杂的代码。 voidInOrder(TreeNode*root) {if(root==NULL)return;InOrder(root->left);visit(...

[综合] 栈和队列：计算表达式

计算表达式 题目：计算(4+5)*(7-2) 思路：本文只介绍简单处理后的表达式，来简单的阐明栈在计算表达式中的应用，例如上面的表达式，要用栈的话，需要对表达式做转换，转成45+72-*,然后利用栈做计算。 intexpress(stringinput) {stack<int>st;in...

[综合] 栈和队列：二叉树的前序遍历

二叉树的前序遍历 题目：用两种方式实现二叉树的前序遍历 方法1：递归 voidpreOrder(TreeNode*root) {if(root==NULL)return;visit(root);preOrder(root->left);preOrder(root->right); } 方...