1、简介 我相信对于一个数组使用快排是十分简单的，如果对一个无序的单链表排序，是否也能够使用快排呢？ 我们先来回顾一下对无序数组的快排：先把数组中的一个元素设置为哨兵（一般是数组的第一个元素），然后利用两个指针指向数组的头和尾。分别移动这两个指针和哨兵进行比较，一趟下来可以把无序数组分为两部分，一部分比哨兵值小，一部分比哨兵值大。哨兵就到了属于它的位置。每一趟快速排序都能确定一个元素的位置。  比如 5 3 1 2 4 6 8 一趟快排下来后就变成了 4 3 1 2 5 6 8。这样5这个位置就固定了。接下来只要对 4 3 1 2 和 6 8 进行快速排序就可以。  2、链表的快排 对于一个单...

111

思路 用快慢指针的方式，每次让快指针走两步，慢指针走一步。如果快慢指针能相遇则说明链表有环。（因为快慢指针之间的相对距离一直在减小，如果有环快指针早晚可以追上慢指针） 代码实现 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { if(!head) retu...

1、入门小谈 假如让你求3的6次方后三位，这个程序毫无疑问是非常简单的： //求幂运算 long long test(int base,long long po) { int result = 1; for(int i=0;i<po;++i) result*=base; return result%1000; } int main() { int r = test(3,6); cout<<r<<endl; return 0; }  但是假如让你求3的100次方的后三位呢？ 如果我们还使用上面的程序的话，结果会是0。原因就在于3的100次方是个很大的数，大到long...

思路 这道题和剪绳子题是一模一样的，区别只在于该题数据范围很大。如果使用和剪绳子一样的做法，那么运行会超时。 剪绳子代码 class Solution { public: int cutRope(int number) { if(number==2||number==3) return number-1; int res = 1; while(number>4) { number-=3; res*=3; } return number*res; } };  如果这道题仍然用这种解法，程序必定会运行超时。其实这道题答案就是求3的高次幂。而求一个数的高次幂，我们可以使用快速幂算法来帮助我们优...

链表反转0.0

1、简介 我们写一个测试程序，来测试下我们的电脑一秒钟可以打印出多少数字。思路很简单，我们只需要利用alarm函数定时1s。然后在while(1)中不断打印变量值就好。 2、代码实现 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/types.h> #include <unistd.h> #include <signal.h> int main() { alarm(1); //定时1s int i = 0; while(1) ...

快速幂的运算

实现思路 利用一个unordered_map来存储链表中每个结点值出现的次数。然后遍历一遍链表。遇见结点值超过两次的直接跳过即可。 使用一个指针指向没有重复链表的结尾，然后用另一个指针去寻找值没有重复的那个结点，然后拼接在没有重复链表的结尾即可。 代码实现 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) {...

111

easy&medium