手撕算法
[TOC]
数据结构
排序
快速排序
#include <stdio.h>
int Partition(int a[],int low,int high){
int key = a[low];
while(low < high){
while(low < high && a[high] >= key)
high--;
if(low < high)
a[low++] = a[high];
while(low < high && a[low] <= key)
low++;
if(low < high)
a[high--] = a[low];
}
a[low] = key;
return low;
}
void quickSort(int *a,int start,int end){
int flag ;
if(a == NULL || start < 0 || end <= 0)
return ;
if(start < end){
flag = Partition(a,start,end);
quickSort(a,start,flag-1);
quickSort(a,flag+1,end);
}
}
int main(int argc, char *argv[])
{
int num,a[100],l=0;
int i;
for(i=0;;i++){
scanf("%d",&a[i]);
l++;
if(getchar()=='\n')
break;
}
quickSort(a,0,l-1);
for(i=0;i<l;i++){
printf("%d ",a[i]);
}
return 0;
}
//快排的优化，其实就是对基准数进行选择，最好情况是选出的数恰好能把序列分成两个等长的子序列。
//1.随机选取基准：但是对重复数组没有很大帮助
//2.三数取中：但是对重复数组没有很大帮助
//3.当待排序序列的长度分割到一定大小后，使用插入排序
//4.在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
//最坏情况O(n^2)
//1.基准是最大或最小 2.顺序是反序排列的
//非递归写法
void quickSort(int *a,int left,int right){
if(a==NULL||left<0||right<=0||left>right){
return;
}
stack<int> temp;
int i,j;
//注意保存顺序，先将初始状态的左右指针压栈
temp.push(right);//先存右指针
temp.push(left);//再存左指针
while(!temp.empty()){
i=temp.top();//先弹出左指针
temp.pop();
j=temp.top();//再弹出右指针
temp.pop();
if(i<j){
int k=Parition(a,i,j);
if(k>i){
temp.push(k-1);//保存中间变量
temp.push(i);//保存中间变量
}
if(j>k){
temp.push(j);
temp.push(k+1);
}
}
}
}
冒泡排序
//一般实现 O(n^2)
void maopaoSort(int *a,int n){
if(a == NULL||n <= 0)
return ;
for(int i = 0;i < n-1;i++){
for(int j = 0;j < n-1-i;j++){
if(a[j] > a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
//优化实现
void maopao1(int arr[], int n) {
int i = 0;
int j = 0;
int tmp = 0;
int flag ;
for (i = 0; i < n; ++i) {
flag = 1;
for (j = 0; j < n - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
flag = 0;
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if (flag) {
break;
}
}
}
选择排序
//O（n^2）
void chooseSort(int *a,int n){
if(a == NULL ||n <= 0)
return ;
for(int i = 0;i < n-1;i++){
int index = i;
//一轮中选出最小的一个，记录角标index
for(int j = i+1;j < n;j++){
if(a[j] < a[index]){
index = j;
}
}
//将第i小的数，放在第i个位置；如果刚好，就不用交换
if(i != index){
int tmp = a[i];
a[i] = a[index];
a[index] = tmp;
}
}
}
插入排序
//直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
//设数组为a[0…n-1]。
//1.初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
//2.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
//3.i++并重复第二步直到i==n-1。排序完成。
//下面给出严格按照定义书写的代码（由小到大排序）：
void Insertsort1(int a[], int n)
{
int i, j, k;
for (i = 1; i < n; i++)
{
//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
for (j = i - 1; j >= 0; j--)
if (a[j] < a[i])
break;
//如找到了一个合适的位置
if (j != i - 1)
{
//将比a[i]大的数据向后移
int temp = a[i];
for (k = i - 1; k > j; k--)
a[k + 1] = a[k];
//将a[i]放到正确位置上
a[k + 1] = temp;
}
}
}
//这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i] > a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处。
void Insertsort2(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
if (a[i] < a[i - 1])
{
int temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
a[j + 1] = a[j];
a[j + 1] = temp;
}
}
//再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。如果a[j]前一个数据a[j-1] > a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1] <= a[j]。这样也可以实现将一个新数据新并入到有序区间。
void Insertsort3(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
Swap(a[j], a[j + 1]);
}
堆排序
//堆排序的思想：通过建立一个大根堆或小根堆，根作为最值输出，然后n-1个数再进行堆调整和输出的过程。
//建堆过程是：将无序数组排列成一个完全二叉树的堆，从最后一个非叶子节点开始调整使得该节点是和两个叶子节点中最大（小）的。直到根节点，随后可以输出根节点。
//堆调整过程：将根结点输出后，将最后一个叶子结点与根节点交换，此时堆被打乱，开始从根节点向下层开始堆调整，保证堆顶为最值，然后继续输出和调整。
void heapAdjust(int *a,int i,int n){
int child,tmp;
for( ;2*i+1 < n;i = child){
//子节点的位置 = 父节点的位置 * 2 + 1
child = 2*i+1;
//得到子节点中较大的节点
if(child < n-1 && a[child+1] > a[child])
++child;
//如果较大的子节点大于父节点，那么把较大的子节点 往上移动，替换它的父节点
if(a[i] < a[child]){
tmp = a[i];
a[i] = a[child];
a[child] = tmp;
}
else
break;
}
}
void heapSort(int *a,int n){
if(a == NULL||n <= 0)
return ;
int i;
//调整序列的前半部分元素，之后第一个元素为序列最大的元素，n/2-1是最后一个非叶子结点
for(i = n/2-1;i >= 0;i--)
heapAdjust(a,i,n);
for(i = n-1;i > 0;i--){
//把第一个元素和当前的最后一个元素交换,保证当前最后一个位置的元素都是在现在这个序列之中最大的
a[i] = a[0] ^ a[i];
a[0] = a[0] ^ a[i];
a[i] = a[0] ^ a[i];
heapAdjust(a,0,i);
}
}
//时间复杂度：建堆过程O（n）、调整堆过程O（n*logn），所以最终是O（n*logn）
//空间复杂度：就地排序O（1）
应用
大数相乘
#include <stdio.h>
#include <string.h>
#define MAXSIZE 200
void bigNumberMulti(char a[],char b[]){
int l1 = (int)strlen(a), l2 = (int)strlen(b);
long num1[MAXSIZE],num2[MAXSIZE];
long result[MAXSIZE] = {0};
int i,j;
int tmp = 0, count = 0;
int len = l1+l2;
//字符串转整数并反转
for(i = l1-1; i >= 0; i--){
num1[i] = a[l1-i-1] - '0';
}
for(i = l2-1; i >= 0; i--){
num2[i] = b[l2-i-1] - '0';
}
//相乘
for (i = 0; i < l1; i++){
for(j = 0; j< l2; j++){
result[i+j] = result[i+j] + num1[i] * num2[j];
}
}
//进位
for(i = 0; i < len; i++){
tmp = result[i] + count;
result[i] = tmp % 10;
count = tmp / 10;
}
for(i = len; i >= 0; i--){
if (result[i] != 0){
break;
}
}
for(; i >= 0; i--){
printf("%d",result[i]);
}
}
int main(int argc, char const *argv[]){
char a[MAXSIZE];
char b[MAXSIZE];
scanf("%s", a);
scanf("%s", b);
bigNumberMulti(a,b);
return 0;
}
大数相加
//大数相加
#include <stdio.h>
#include <string.h>
#define MAXSIZE 200
int flag = 0;
//字符串逆置
void reverse(char str[]){
int length = (int)strlen(str);
char temp;
int i = 0 ,j;
while(i < length-i-1){
for (j = 0; j<length-1; j++) {
if (str[j]>'9'||str[j]<'0') {
printf("error");
flag = 1;
break;
}
}
temp = str[i];
str[i] = str[length-i-1];
str[length-i-1] = temp;
i++;
}
}
void bigNumAdd(char *a,char *b,char *result){
int i,acc = 0,temp;
int l1 = (int)strlen(a),l2 = (int)strlen(b);
if (a == NULL){
result = b;
}else if (b == NULL){
result = a;
}
reverse(a);
reverse(b);
if (flag) {
return;
}
for(i = 0;i < l1 && i < l2;i++){
temp = a[i]-'0'+b[i]-'0'+acc;
result[i] = temp%10+'0';
acc = temp/10;
}
if (i < l1){
for(;i < l1;i++){
temp = a[i] - '0' + acc;
result[i] = temp%10 +'0';
acc = temp/10;
}
}
if (i < l2){
for(;i < l2;i++){
temp = b[i] - '0' + acc;
result[i] = temp%10 + '0';
acc = temp/10;
}
}
if (acc == 1){
result[i++] = '1';
}
result[++i] = '\0';
reverse(result);
printf("%s", result);
}
int main(int argc, char const *argv[])
{
char a[MAXSIZE];
char b[MAXSIZE];
char result[MAXSIZE];
scanf("%s",a);
scanf("%s",b);
bigNumAdd(a,b,result);
return 0;
}
斐波那契(递归实现)
int func(int n){
if(n <= 1)
return n;
else
return func(n-1) + func(n-2);
}
斐波那契(非递归实现)
int func(int n){
if(n <= 1)
return n;
int f1 = 1,f2 = 0,num = 0;
for(int i = 2;i <= n;i++){
num = f1 + f2;
f2 = f1;
f1 = num;
}
return num;
}
青蛙跳台阶
//一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
//分析：首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。
//现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。
//我们把上面的分析用一个公式总结如下：
/ 1 n=1
f(n)= - 2 n=2
\ f(n-1)+(f-2) n>2
//分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。
//代码见上文Fibonacci序列算法。
变态青蛙跳台阶
//一个台阶总共有n级，如果一次可以跳1级，也可以跳2级......它也可以跳上n级。此时该青蛙跳上一个n级的台阶总共有多少种跳法？
//分析：用Fib(n)表示青蛙跳上n阶台阶的跳法数，青蛙一次性跳上n阶台阶的跳法数1(n阶跳)，设定Fib(0) = 1；
// 当n = 1 时， 只有一种跳法，即1阶跳：Fib(1) = 1;
// 当n = 2 时， 有两种跳的方式，一阶跳和二阶跳：Fib(2) = Fib(1) + Fib(0) = 2;
// 当n = 3 时，有三种跳的方式，第一次跳出一阶后，后面还有Fib(3-1)中跳法； 第一次跳出二阶后，后面还有Fib(3-2)中跳法；第一次跳出三阶后，后面还有Fib(3-3)中跳法
// Fib(3) = Fib(2) + Fib(1) + Fib(0) = 4;
// 当n = n时，共有n种跳的方式，第一次跳出一阶后，后面还有Fib(n-1)中跳法； 第一次跳出二阶后，后面还有Fib(n-2)中跳法......第一次跳出n阶后，后面还有 Fib(n-n)中跳法
// Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)
// 又因为Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)
// 两式相减得：Fib(n)-Fib(n-1)=Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 2
// 递归等式如下：
/ 1 n=0
f(n)= - 1 n=1
\ 2*f(n-1) n>2
二进制数中1的个数
//解法一：向右移动二进制数，和1相与，但会造成死循环，二进制最后变成0xFFFFFFFF.
while(n){
if(n & 1)
count++;
n>>1;
}
//解法二：向左移动1，相与
while(flag){
if(n & flag)
count++;
flag = flag << 1;
}
//解法三：该数减1和该数相与，执行次数就是个数
int numberOf1(int n) {
int count=0;
while(n){
count++;
n=(n-1)&n;
}
return count;
}
不用加减乘除做加法运算
//首先看十进制是如何做的： 5+7=12，三步走
//第一步：相加各位的值，不算进位，得到2。
//第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
//第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。
//同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111
//第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，即101^111。
//第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，即(101&111)<<1。
//第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
//继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
int func(int num1,int num2){
int temp;
while(num2!=0){
temp = num1^num2;
num2 = (num1&num2)<<1;
num1 = temp;
}
return num1;
}
最大公约数
2.1 递归实现
int gcd(int a, int b){
if(!b)
return a;
else
return gcd(b, a%b);
}
2.2 迭代实现
int gcd(int a, int b){
int c = a % b;
while(c){
a = b;
b = c;
c = a % b;
}
return b;
}
链表
单链表相邻奇偶交换
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int Value;
struct Node* pNext;
}Node;
Node *creatLink(Node *head) {
Node *pre = NULL;
head = (Node *)malloc(sizeof(Node));
pre = head;
int a[10] = {1,2,3,4,5,6};
for (int i = 0; i < 6; i++) {
Node *temp = (Node *)malloc(sizeof(Node));
temp->Value = a[i];
pre->pNext = temp;
pre = temp;
}
return head;
}
void swap(Node *head) {
Node *first, *second, *third;
first = head;
second = head->pNext;
while (second) {
third = second->pNext;
if (third == NULL) {
break;
}
first->pNext = third;
second->pNext = third->pNext;
third->pNext = second;
first = third->pNext;
second = third->pNext->pNext;
}
}
int main() {
Node *head = NULL, *pre;
head = creatLink(head);
pre = head->pNext;
while (pre) {
printf("%d ", pre->Value);
pre = pre->pNext;
}
printf("\n");
swap(head);
pre = head->pNext;
while (pre) {
printf("%d ", pre->Value);
pre = pre->pNext;
}
printf("\n");
}
在O(1)时间删除链表节点
//用下一个节点数据覆盖要删除的节点，然后删除下一个节点
//O(1)时间删除链表节点，从无头单链表中删除节点
void deleteRandomNode(Node *cur)
{
assert(cur != NULL);
assert(cur->next != NULL); //不能是尾节点
Node* pNext = cur->next;
cur->data = pNext->data;
cur->next = pNext->next;
delete pNext;
}
单链表的转置
//非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的
//单链表的转置,循环方法
Node* reverseByLoop(Node *head)
{
if(head == NULL || head->next == NULL)
return head;
Node *pre = NULL;
Node *next = NULL;
while(head != NULL)
{
next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
//单链表的转置,递归方法
Node* reverseByRecursion(Node *head)
{
//第一个条件是判断异常，第二个条件是结束判断
if(head == NULL || head->next == NULL)
return head;
Node *newHead = reverseByRecursion(head->next);
head->next->next = head;
head->next = NULL;
return newHead; //返回新链表的头指针
}
链表倒数第k个节点
//设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。
//倒数第k个节点
Node* theKthNode(Node *head,int k)
{
if(k < 0) return NULL; //异常判断
Node *slow,*fast;
slow = fast = head;
int i = k;
for(;i>0 && fast!=NULL;i--)
{
fast = fast->next;
}
if(i > 0) return NULL; //考虑k大于链表长度的case
while(fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
求链表的中间节点
//可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。
//求链表的中间节点
Node* theMiddleNode(Node *head)
{
if(head == NULL)
return NULL;
Node *slow,*fast;
slow = fast = head;
//如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件
//while(fast && fast->next != NULL && fast->next->next != NULL)
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
判断单链表是否存在环，环的入口
//通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。
//判断单链表是否存在环,参数circleNode是环内节点，后面的题目会用到
bool hasCircle(Node *head,Node *&circleNode)
{
Node *slow,*fast;
slow = fast = head;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
circleNode = fast;
return true;
}
}
return false;
}
//输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？
//思路：按照上面的思路，假设两个指针在（图Z点）相遇，此时slow指针走过的路径是a+b，而fast指针走过的路径是a+b+c+b。由于fast的步长是slow的两倍，因此可以得到：2（a+b）=a+b+c+b，解得a=c。由上图可以看出从X点到Y点的距离与从Z点到Y点的距离相等，即让slow指针与fast指针相遇后，我们让slow指针再指向头结点（X点），此时fast指针位置不变，再让slow和fast指针同时后移，当两个指针相遇时，slow和fast指向的是恰好是环形链表的起始节点（Y点）。
//代码如下：
//找到环的入口点
Node* findLoopPort(Node *head)
{
//如果head为空，或者为单结点，则不存在环
if(head == NULL || head->next == NULL) return NULL;
Node *slow,*fast;
slow = fast = head;
//先判断是否存在环
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
break;
}
if(fast != slow) return NULL; //不存在环
fast = head; //快指针从头开始走，步长变为1
while(fast != slow) //两者相遇即为入口点
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
判断两个链表是否相交
//思路一：直接判断第一个链表的每个节点是否在第二个链表中，但时间复杂度是O(n*m)
//思路二：针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的节点是否在hahs表里出现过，如果第二个链表的节点能在hash表中找到，则说明第二个链表与第一个链表有相同的节点。时间复杂度为线性的O（length1+length2）,空间复杂度为O（length1）
//思路三：转化为环的问题。把第二个链表接在第一个链表后面，如果有环则相交。判断有环参考上一个算法。其实，如果有环，则第二个链表的表头一定在环上，即第二个链表会构成一个循环链表，只需要遍历第二个链表，看是否会回到起始点就可以判断。这个方法时间复杂度是线性的。
//思路四：只需要判断尾指针是否相同，相同则相交。
//判断两个链表是否相交
bool isIntersect(Node *h1,Node *h2)
{
if(h1 == NULL || h2 == NULL) return false; //异常判断
while(h1->next != NULL)
{
h1 = h1->next;
}
while(h2->next != NULL)
{
h2 = h2->next;
}
if(h1 == h2) return true; //尾节点是否相同
else return false;
}
两链表相交的第一个公共节点
//较长链表先走L2-L1步，然后同时移动，相遇时的点就是相交的第一个节点
//求两链表相交的第一个公共节点
Node* findIntersectNode(Node *h1,Node *h2)
{
int len1 = listLength(h1); //求链表长度
int len2 = listLength(h2);
//对齐两个链表
if(len1 > len2)
{
for(int i=0;i<len1-len2;i++)
h1=h1->next;
}
else
{
for(int i=0;i<len2-len1;i++)
h2=h2->next;
}
while(h1 != NULL)
{
if(h1 == h2)
return h1;
h1 = h1->next;
h2 = h2->next;
}
return NULL;
}
反转链表
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL)
return nullptr;
ListNode *prenode=NULL;
ListNode *node=pHead;
ListNode *newhead;
while(node){
ListNode *nextnode=node->next;
if(nextnode==NULL)
newhead=node;
node->next=prenode;
prenode=node;
node=nextnode;
}
return newhead;
}
};
合并两个递增链表
ListNode *Merge(ListNode *h1,ListNode *h2){
if(h1 == NULL)
return h2;
else if(h2 == NULL)
return h1;
ListNode *newhead = NULL;
if(h1->value < h2->value){
newhead = h1;
newhead->next = Merge(h1->next,h2);
}
else{
newhead = h2;
newhead->next = Merge(h1,h2->next);
}
return newhead;
}
数组
最小的k个数
//利用快排，可以先将数组进行排序，然后直接按顺序取k个数即可，时间复杂度为O（n）
void GetNumbers(int *a,int n,int k){
if(a == NULL||n <= 0||k <= 0)
return ;
int start = 0,end = n - 1;
int flag = Partition(a,start,end);
while(flag != k-1){
if(flag > k-1){
end = flag - 1;
flag = Partition(a,start,end);
}else{
start = flag + 1;
flag = Partition(a,start,end);
}
}
for(int i = 0;i < k;i++){
printf("%d ",a[i]);
}
}
//如果要求不能调整数组元素，那么可以使用堆。用k个数建立最大堆，然后取其他数，与堆顶的数进行比较，比堆顶小则交换，否则取下一个数进行比较。这种做法适合海量数据，复杂度为O（n*logk）。或者使用红黑树，使得查找、删除和插入操作时间复杂度都为O（logk）。
数组奇偶交换，保证顺序
class Solution {
public:
void reOrderArray(vector<int> &array) {
if(array.size()==0)
return;
int l = array.size();
int newarray[l];
int newcount=0,oldcount=0;
for(int i =0;i<l;i++){
if(array[i]%2!=0){
newcount++;
}
}
for(int i =0;i<l;i++){
if(array[i]%2==0){
newarray[newcount++]=array[i];
}else{
newarray[oldcount++]=array[i];
}
}
for(int i =0;i<l;i++){
array[i]=newarray[i];
}
}
};
旋转数组中最小的数
class Solution {
public:
int minNumberInRotateArray(vector<int> a) {
int len = a.size();
if(len<=0)
return 0;
int l1=0,l2=len-1;
int flag =l1;
while(a[l1]>=a[l2]){
if(l2-l1==1){
flag=l2;
break;
}
flag = (l1+l2)/2;
if(a[l1]==a[l2]&&a[l1]==a[flag]){
int result = a[l1];
for(int i = l1+1;i<=l2;i++){
if(result>a[i])
result = a[i];
}
return result;
}
if(a[flag]>=a[l1])
l1=flag;
else if(a[flag]<=a[l2])
l2=flag;
}
return a[flag];
}
};
字符串
字符串转整数
//不调用库函数用C语言实现atoi函数的功能：
#include <stdio.h>
#include <stdlib.h>
int my_atoi(const char *str);
int main(int argc, char *argv[])
{
char *ptr = " 1234 3455";
int n;
n = my_atoi(ptr);
printf("myAtoi:%d/n", n);
n = atoi(ptr);
printf("atoi:%d/n", n);
return 0;
}
int my_atoi(const char *str)
{
int value = 0;
int flag = 1; //判断符号
while (*str == ' ') //跳过字符串前面的空格
{
str++;
}
if (*str == '-') //第一个字符若是‘-’，说明可能是负数
{
flag = 0;
str++;
}
else if (*str == '+') //第一个字符若是‘+’，说明可能是正数
{
flag = 1;
str++;
}//第一个字符若不是‘+’‘-’也不是数字字符，直接返回0
else if (*str >= '9' || *str <= '0')
{
return 0;
}
//当遇到非数字字符或遇到‘/0’时，结束转化
while (*str != '/0' && *str <= '9' && *str >= '0')
{
value = value * 10 + *str - '0'; //将数字字符转为对应的整形数
str++;
}
if (flag == 0) //负数的情况
{
value = -value;
}
return value;
}
KMP算法（字符串匹配）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void compute_prefix(const char *pattern,int next[]){
int i,j = -1;
const int m = strlen(pattern);
next[0] = j;
for(i = 1;i < m;i++){
while(j > -1 && pattern[j+1] != pattern[i]){
j = next[j];
}
if(pattern[i] == pattern[j+1])
j++;
next[i] = j;
}
}
int kmp(const char*text,const char *pattern){
int i,j = -1;
const int n = strlen(text);
const int m = strlen(pattern);
if(n == 0 && m == 0)
return 0;
if(m == 0)
return 0;
int *next =(int*)malloc(sizeof(int)*m);
compute_prefix(pattern,next);
for(i = 0;i < n;i++){
while(j > -1 && pattern[j+1]!=text[i])
j = next[j];
if(text[i] == pattern[j+1])
j++;
if(j == m-1){
free(next);
return i-j;
}
}
free(next);
return -1;
}
int main(){
char text[] = "abcabcabcd";
char pattern[] = "abcd";
char *ch = text;
int i = kmp(text,pattern);
if(i>=0)
printf("matched at %d:%s\n",i,ch+i);
return 0;
}
括号匹配
include <iostream>
#include <stack>
using namespace std;
// 判断字符是不是左括号类型
bool isLeft(char c)
{
return (c == '(' || c == '[' || c == '{');
}
// 判断右括号与左括号是否匹配
bool isMatch(char right, char left)
{
if (right == ')')
{
return (left == '(');
}
if (right == ']')
{
return (left == '[');
}
if (right == '}')
{
return (left == '{');
}
}
// 判断字符串是否匹配
bool matching(char* s)
{
stack<char> cs;
char c;
while (*s)
{
c = *s;
if (isLeft(c))
{
cs.push(c);
}
else
{
if (cs.empty() || !isMatch(c, cs.top()))
{
return false;
}
cs.pop();
}
++s;
}
if (!cs.empty())
{
return false;
}
return true;
}
字符串转数字
面试官至少会期待应聘都能够在不需要提示的情况下，考虑到输入的字符串中有非数字字符和正负号，要考虑到最大的正整数和最小的负整数以及溢出。同时面试试还期待应聘者能够考虑到当输入的字符串不能转换成整数时，应该如何做错误处理。
1、检查字符串是否为空
2、对非法输入，返回0，并设置全局变量
3、溢出
4、空字符串""
5、输入字符串只有"+"或"-"号
typedef enum {VALID, INVALID} ResType; //返回的结果类型
ResType g_rtRes = VALID;
bool isdigit(char ch)
{
return '0'<=ch && ch<='9';
}
int StrToInt(const char *str)
{
unsigned int iCur, iMax;
int sign;
const char *p;
//判断参数是否合法
if(!str || strlen(str)<=0){
g_rtRes = INVALID;
return 0;
}
//去掉前面空格
for(p=str; ' '==*p; p++);
//判断正负号
sign = 1;
iMax = ~(1<<8*sizeof(int)-1); //最大正整数
if('+'==*p){
p++;
}else if('-' == *p){
p++;
sign = -1;
iMax = ~iMax; // sign*iMax 就是最小负正数
}
//首位不是数字，输入非法
if(!isdigit(*p)){
g_rtRes = INVALID;
return 0;
}
//首位是0，特殊处理
if('0'==*p){
if(isdigit(*(p+1))){
g_rtRes = INVALID;
}
return 0;
}
//累和
for(iCur=0; isdigit(*p) && iCur<=iMax; p++){
iCur = iCur*10 + (*p - '0');
}
//返回结果
if(iCur <= iMax){
return (int)(sign*iCur);
}else{
g_rtRes = INVALID;
return 0;
}
}// StrToInt
树
二叉树前中后序递归
//前中后递归就是把1的位置换到2、3
void pre_traverse(BTree pTree){
if(pTree){
printf("%c ",pTree->data); //1
if(pTree->pLchild) //2
pre_traverse(pTree->pLchild);
if(pTree->pRchild) //3
pre_traverse(pTree->pRchild);
}
}
前序非递归
void PreOrderTraverse(BiTree T){ //非递归先序遍历
stack<BiTree> Stack;
if(!T){
printf("空树！\n");
return;
}
while(T || !Stack.empty()){
while(T){
Stack.push(T);
printf("%c",T->data);
T=T->lchild;
}
T=Stack.top();
Stack.pop();
T=T->rchild;
}
}
中序非递归
void InOrderTraverse(BiTree T){ //非递归中序遍历
stack<BiTree> Stack;
if(!T){
printf("空树！\n");
return;
}
while(T || !Stack.empty()){
while(T){
Stack.push(T);
T=T->lchild;
}
T=Stack.top();
Stack.pop();
printf("%c",T->data);
T=T->rchild;
}
}
后序非递归
//二叉树的后序遍历顺序为，root->left, root->right, root，因此需要保存根节点的状态。显然使用栈来模拟递归的过程，但是难点是怎么从root->right转换到root。
//对于节点p可以分情况讨论：
//1. p如果是叶子节点，直接输出
//2. p如果有孩子，且孩子没有被访问过，则按照右孩子，左孩子的顺序依次入栈
//3. p如果有孩子，而且孩子都已经访问过，则访问p节点
//如何来表示出p的孩是否都已经访问过了呢？
//最暴力的方法就是对每个节点的状态进行保存，这么做显然是可以的，但是空间复杂度太大了。
//我们可以保存最后一个访问的节点last，如果满足 (p->right==NULL && last ==p->left) || last=p->right，那么显然p的孩子都访问过了，接下来可以访问p
vector<int> postOrder(TreeNode *root) {
vector<int> res;
if(root == NULL)
return res;
TreeNode *p = root;
stack<TreeNode *> sta;
TreeNode *last = root;
sta.push(p);
while (!sta.empty()){
p = sta.top();
if( (p->left == NULL && p->right == NULL) || (p->right == NULL && last == p->left) || (last == p->right) ){
res.push_back(p->val);
last = p;
sta.pop();
}
else{
if(p->right)
sta.push(p->right);
if(p->left)
sta.push(p->left);
}
}
return res;
}
前中序推后序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/** 已知先序和中序，将后序求出来并存入数组s中 */
void print(int n,char * s1,char * s2,char * s){
if(n<=0)
return ;
/*
功能：查找字符s2中首次出现s1[0]的位置
说明：返回首次出现s1[0]的位置的指针，
如果s2中不存在c则返回NULL
*/
int p = strchr(s2,s1[0])-s2;
//这个是采用递归得到左子树
print(p,s1+1,s2,s);
//这个是采用递归得到右子树
print(n-1-p,s1+p+1,s2+p+1,s+p);
//要得到后序遍历,所以整个的最后一个是根
s[n-1] = s1[0];
}
int main() {
/*
定义s1用来存放前序，s2用来存放中序
ans用来存放后序
*/
char s1[30],s2[30],ans[30];
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
//EOF表示无更多的资料可读，是循环终止的条件
while(scanf("%s %s",s1,s2)!=EOF)
{
//获取数组s1的长度
int n=strlen(s1);
print(n,s1,s2,ans);
ans[n]='\0';
printf("%s\n",ans);
}
return 0;
}
动态规划
最大连续子序列之和
//状态转移方程： sum[i]=max(sum[i-1]+a[i],a[i])
#include <stdio.h>
main(){
int i,sum=0,max=0x80000000;
int data[]={1,-2,3,-1,7};
for(i=0;i<sizeof(data)/sizeof(data[0]);i++){
sum+=data[i];
if(sum>max)
max=sum;
if(sum<0)
sum=0;
}
printf("%d",max);
}
树塔问题
//数塔问题 ：要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？、
//转移方程：sum[i] = max(a[左孩子] , a[右孩子]) + a[i]
#include <stdio.h>
#define N 5
main(){
int i,j;
int data[N][N]={
{9,0,0,0,0},
{12,15,0,0,0},
{10,6,8,0,0},
{2,18,9,5,0},
{19,7,10,4,16}
};
for(i=N-1;i>0;i--){
for(j=0;j<i;j++){
data[i-1][j]+=data[i][j]>data[i][j+1]?data[i][j]:data[i][j+1];
}
}
printf("%d",data[0][0]);
}
01背包问题
//背包问题：有m件物品和一个承重为t的背包。第i件物品的重量是w[i]，价值是v[i]。
//求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。
//转移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]
#include <stdio.h>
#include <conio.h>
#include <string.h>
int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值
int max(int x,int y){//返回x,y的最大值
if(x>y) return x;
return y;
}
int main(){
int t,m,i,j;
memset(f,0,sizeof(f)); //总价值初始化为0
scanf("%d %d",&t,&m); //输入背包承重量t、物品的数目m
for(i=1;i<=m;i++)
scanf("%d %d",&w[i],&v[i]); //输入m组物品的重量w[i]和价值v[i]
for(i=1;i<=m;i++){ //尝试放置每一个物品
for(j=t;j>=w[i];j--){
f[j]=max(f[j-w[i]]+v[i],f[j]);
//在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
}
}
printf("%d",f[t]); //输出承重量为t的背包的总价值
printf("\n");
getch();
return 0;
}
最长递增子序列
//转移方程：b[k]=max(max(b[j]|a[j]<a[k],j<k)+1,1)
#include "stdio.h"
main(){
int i,j,length,max=0;
int a[] = {
1,-1,2,-3,4,-5,6,-7
};
int *b;
b = (int *)malloc(sizeof(a));
length = sizeof(a)/sizeof(a[0]);
for(i = 0; i < length; i++){
b[i] = 1;
for(j = 0; j < i; j++){
if(a[i] > a[j] && b[i] <= b[j]){
b[i] = b[j] + 1;
}
}
}
for(i = 0; i < length; i++)
if(b[i] > max)
max = b[i];
printf("%d",max);
}
最长公共子序列(LCS)
//一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
//转移方程：
//dp[i,j] = 0 i=0 || j=0
//dp[i,j] = dp[i-1][j-1]+1 i>0,j>0, a[i] = b[j]
//dp[i,j] = max(dp[i-1][j],dp[i][j-1]) i>0,j>0, a[i] != b[j]
#include "stdio.h"
#define M 8
#define N 6
void printLSC(int i, int j,char *a, int status[][N]){
if(i == 0 || j== 0)
return;
if(status[i][j] == 0){
printLSC(i-1,j-1,a,status);
printf("%c",a[i]);
}else{
if(status[i][j] == 1)
printLSC(i-1,j,a,status);
else
printLSC(i,j-1,a,status);
}
}
main(){
int i,j;
char a[] = {' ','A','B','C','B','D','A','B'};
char b[] = {' ','B','D','C','B','A'};
int status[M][N]; //保存状态
int dp[M][N];
for(i = 0; i < M; i++)
for(j = 0; j < N; j++){
dp[i][j] = 0;
status[i][j] = 0;
}
for(i = 1; i < M; i++)
for(j = 1; j < N; j++){
if(a[i] == b[j]){
dp[i][j] = dp[i-1][j-1] + 1;
status[i][j] = 0;
}
else if(dp[i][j-1] >= dp[i-1][j]){
dp[i][j] = dp[i][j-1];
status[i][j] = 2;
}
else{
dp[i][j] = dp[i-1][j];
status[i][j] = 1;
}
}
printf("最大长度：%d",dp[M-1][N-1]);
printf("\n");
printLSC(M-1,N-1,a,status);
printf("\n");
}
操作系统
生产者消费者
semaphore mutex = 1 ; //临界区互斥信号量
semaphore empty = n ; //空闲缓冲区
semaphore full = 0 ; //缓冲区初始化为空
producer() {
while(1){
produce an item in nextp; //生产数据
P(empty); //获取空缓冲区单元
P(mutex); //进入临界区
add nextp to buffer; //把数据放入缓冲区
V(mutex); //离开临界区，释放互斥信号量
V(full); //满缓冲区数+1
}
}
consumer() {
while(1){
P(full); //获取满缓冲区单元
P(mutex); //进入临界区
remove an item from buffer; //从缓冲区中取出数据
V(mutex); //离开临界区，释放互斥信号量
V(empty); //空缓冲区数+1
consume the item； //消费数据
}
}
读写问题
int count = 0; //用于记录当前的读者数量
semaphore mutex = 1; //用于保护更新count变量时的互斥
semaphore rw=1; //用于保证读者和写者互斥地访问文件
semaphore w=1; //用于实现“写优先”
writer(){
while(1){
P(w); //在无写进程请求时进入
P(rw); //互斥访问共享文件
writing; //写入
V(rw); // 释放共享文件
V(w) ; //恢复对共享支件的访问
}
}
reader () { //读者进程
while (1){
P (w) ; // 在无写进程请求时进入
P (mutex); // 互斥访问count变量
if (count==0) //当第一个读进程读共享文件时
P(rw); //阻止写进程写
count++; //读者计数器加1
V (mutex) ; //释放互斥变量count
V(w); //恢复对共享文件的访问
reading; //读取
P (mutex) ; //互斥访问count变量
count--; //读者计数器减1
if (count==0) //当最后一个读进程读完共享文件
V(rw); //允许写进程写
V (mutex); //释放互斥变量count
}
}
哲学家进餐
semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=l; //设置取筷子的信号量
Pi(){ //i号哲学家的进程
do{
P (mutex) ; //在取筷子前获得互斥量
P (chopstick [i]) ; //取左边筷子
P (chopstick[ (i+1) %5]) ; //取右边筷子
V (mutex) ; //释放取筷子的信号量
eat; //进餐
V(chopstick[i] ) ; //放回左边筷子
V(chopstick[ (i+l)%5]) ; //放回右边筷子
think; // 思考
}while(1);
}
OC
单例
#import "Session.h"
@implementation Session
static Session *session ;
//当我们调用shareInstance方法时获取到的对象是相同的，但是当我们通过alloc和init以及copy来构造对象的时候，依然会创建新的实例。要确保对象的唯一性，所以我们就需要封锁用户通过alloc和init以及copy来构造对象这条道路。
//我们知道，创建对象的步骤分为申请内存(alloc)、初始化(init)这两个步骤，我们要确保对象的唯一性，因此在第一步这个阶段我们就要拦截它。当我们调用alloc方法时，oc内部会调用allocWithZone这个方法来申请内存，我们覆写这个方法，然后在这个方法中调用shareInstance方法返回单例对象，这样就可以达到我们的目的。拷贝对象也是同样的原理，覆写copyWithZone方法，然后在这个方法中调用shareInstance方法返回单例对象。
+ (instancetype)shareInstance{
//GCD
static dispatch_once_t onceToken;
dispatch_once(&onceToken,^{
_session = [[super allocWithZone:NULL]init];
//不是使用alloc方法，而是调用[[super allocWithZone:NULL] init]
//已经重载allocWithZone基本的对象分配方法，所以要借用父类（NSObject）的功能来帮助出处理底层内存分配的杂物
});
//互斥锁
/*@syschronized(self){
if(_session == nil){
_session = [super allocWithZone:zone];
}
}*/
return session;
}
+ (instancetype)allocWithZone:(struct _NSZone *)zone{
return [Session shareInstance];
}
- (id)copyWithZone:(struct _NSZone *)zone{
return _session;
}
- (id)mutableCopyWithZone:(struct _NSZone *)zone{
return _session;
}
--------------------------------------------------------------------------
//大多数单例的使用场景都是到最后一直存活着，这样会带来内存的浪费
//weak的作用可以用一句话来说明：在不增加对象的引用计数的同时，又使得指针的访问是安全的
//如果在单例上用上weak？
//在所有使用单例的对象都释放后，单例对象本身也会自己释放。这样怎么样？
+ (id)shareInstance{
static __weak Session *weakSession;
Session *strongSession = weakSession;
@syschronized(self){
if(strongSession == nil){
strongSession = [[self alloc]init];
weakSession = strongSession;
}
}
return strongSession;
}
NSTimer循环引用
//方法一
typedef int(^MyBlock)(NSString *str);
@property(nontomic,strong) NSTimer *timer;
@property(nontomic,copy) MyBlock myblock;
- (instancetype)initWithBlock:(MyBlock)block{
self = [super init];
if(self){
if (block)
{
myblock = block;
}
if (!_timer)
{
__weak typeof(self) weakSelf = self;
_timer = [NSTimer scheduledTimerWithTimeInterval:1 target:weakSelf selector:@selector(start) userInfo:nil repeats:YES];
}
}
return self;
}
- (void)start{
NSLog("123");
}
- (void)dealloc{
[_timer invalidate];
_timer = nil;
}
//这样做还是会产生保留环，因为VC没有释放，timer对weakSelf这个变量是强引用。
//timer->weakSelf->VC->timer,三者之间形成了循环引用。
//--------------------------------------------------------------------------------------------------------
//方法二：为NSTimer增加一个分类，采用block块
#import <Foundation/Foundation.h>
@interface NSTimer (RCUncircle)
+ (NSTimer *)rcc_scheduledTimerWithTimeInterval:(NSTimeInterval)interval repeats:(BOOL)repeats block:(void(^)(NSTimer *timer))block;
@end
#import "NSTimer+RCUncircle"
@implementation NSTimer (RCUncircle)
+ (NSTimer *)rcc_scheduledTimerWithTimeInterval:(NSTimeInterval)interval repeats:(BOOL)repeats block:(void(^)(NSTimer *timer))block{
return [NSTimer scheduledTimerWithTimeInterval:interval target:self selector:@selector(rcc_blockInvoke:) userInfo:[block copy] repeats:repeats];
}
+ (void)rcc_blockInvoke:(NSTimer *)timer{
void (^block)(NSTimer *timer) = timer.userInfo;
if (block){
block(timer);
}
}
@end
#import "ViewController.h"
#import "NSTimer+RCUncircle"
@interface ViewController ()
@property (nontomic,strong) NSTimer *timer;
@end
@implementation ViewController
//定时器现在的target是NSTimer类对象，这是个单例，此处依然有循环引用，然后类对象无需回收，所以不用担心。
- (void)viewDidLoad{
[super viewDidLoad];
__weak typeof(self)weakSelf = self;
self.timer = [NSTimer rcc_scheduledTimerWithTimeInterval:1 repeats:YES block:^(NSTimer *timer){
__strong typeof(self) strongSelf = weakSelf;
[strongSelf start];
}];
}
- (void)start{
NSLog(@"123");
}
- (voi)dealloc{
[_timer invalidate];
}
