版权声明：本文为博主原创文章，未经博主允许不得转载；如需转载，请保持原文链接。
毕业之后很少用算法，感觉思维都有点僵化了，一道很简单的算法题也要想半天，好歹自己也是在ACM队混过的，怎么能这么菜呢，觉得还是要捡起算法，这里记录我的复习过程，慢慢积累；
2017-7-3 leetcode题
Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @return a ListNode
def addTwoNumbers(self, l1, l2):
head = ListNode(0)
l = head
carry = 0
while l1 or l2 or carry:
sum, carry = carry, 0
if l1:
sum += l1.val
l1 = l1.next
if l2:
sum += l2.val
l2 = l2.next
if sum > 9:
carry = 1
sum -= 10
l.next = ListNode(sum)
l = l.next
return head.next
2017-7-2 排序算法
冒泡排序
冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。 (C实现)
void testsort (int *a,int len)
{
for (int i=0;i<len-1;i++){
for (int j=0; j<len-i-1; j++) {
if (a[j]<a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
选择排序
先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
void select_sort(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
int index = i;
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[index])
index = j;
}
if (index != i)
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
插入排序
将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2)
void insert_sort(int arr[], int len)
{
for (int i = 1; i < len; i ++)
{
int j = i - 1;
int k = arr[i];
while (j > -1 && k < arr[j] )
{
arr[j + 1] = arr[j];
j --;
}
arr[j + 1] = k;
}
}
快速排序
快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
void quick_sort(int *a,int left,int right)
{
if (left<right) {
int i=left,j=right,target = a[i];
while (i<j) {
for (; i<j; j--) {
if (a[j]<target) {
a[i++] = a[j];
break;
}
}
for (; i<j; i++) {
if (a[i]>target) {
a[j--] = a[i];
break;
}
}
}
a[i] = target;
quick_sort(a, left, i-1);
quick_sort(a, i+1, right);
}
}
希尔排序 ShellSort
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
void ShellSort(int *arr, int N)
{
int i, j, increment;
int tmp;
for (increment = N / 2; increment > 0; increment /= 2)
{
for (i = increment; i < N; i++)
{
tmp = arr[i];
for (j = i; j >= increment; j -= increment)
{
if (arr[j - increment] > tmp)
arr[j] = arr[j - increment];
else
break;
}
arr[j] = tmp;
}
}
}
归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
void merge(int *a,int left,int mid,int right)
{
int i, k;
int tmp[right];
//申请空间，使其大小为两个
int left_low = left;
int left_high = mid;
int right_low = mid + 1;
int right_high = right;
for(k=0; left_low<=left_high && right_low<=right_high; k++){
// 比较两个指针所指向的元素
if(a[left_low]<=a[right_low]){
tmp[k] = a[left_low++];
}else{
tmp[k] = a[right_low++];
}
}
if(left_low <= left_high){
//若第一个序列有剩余，直接复制出来粘到合并序列尾
for(i=left_low;i<=left_high;i++)
tmp[k++] = a[i];
}
if(right_low <= right_high){
//若第二个序列有剩余，直接复制出来粘到合并序列尾
for(i=right_low; i<=right_high; i++)
tmp[k++] = a[i];
}
for(i=0; i<right-left+1; i++)
a[left+i] = tmp[i];
return;
}
void mergeFunc(int *a,int left,int right)
{
if (left<right) {
int mid = (left+right)/2;
mergeFunc(a, left, mid);
mergeFunc(a, mid+1, right);
merge(a,left,mid,right);
}
}
void mergeSort(int *a,int len)
{
mergeFunc(a,0,len-1);
}
2017-7-1 翻转二叉树
翻转二叉树，C语言实现
void invertTree (node *root)
{
if (root==NULL) {
return;
}
if (root->left) {
invertTree(root->left);
}
if (root->right) {
invertTree(root->right);
}
node *tree = root->left;
root->left = root->right;
root->right = tree;
}
Python实现
def invertTree(root):
if root is None:
return None
if root.left:
invertTree(root.left)
if root.right:
invertTree(root.right)
root.left, root.right = root.right, root.left
return root
2017-6-20 字符串替换空格
题：实现一个函数，把字符串中的空格替换成%20，例如：输入”We are happy.”，替换为”We%20are%20happy.”
解法一
一、最差的解法
从头到尾扫描字符串，每一次碰到字符串的时候做替换，由于是把1个字符串替换成3个字符串，所以必须把空格后面的所有的字符往后移动两个字节；
代码略；
时间复杂度为O（N2）。
解法二
二、空间换时间
新建一个数组，从头到尾扫描字符串，把其填入新的数组中，碰到空格时替换为%20；
代码略；
时间复杂度为O（N），到时牺牲了空间
解法三
三、最优解
- 先遍历一次统计出空格总数，然后计算出替换后需要的字符串总长度，例子中的字符串为14，替换后是18；
- 接下来我们从字符串的后面开始复制和替换，先准备两个指针，P1和P2。P1指向原始字符串的末尾，P2指向替换后的字符串末尾；
- 向前移动P1，逐个把字符复制到P2的位置，当P1碰到空格，P2做处理替换
代码略；
以上是所有的字符都只移动一次，时间复杂度为O（N）
2017-6-1 矩阵算法
在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字6，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。
[image]
本Young问题解法有二（如查找数字6）：
1、分治法，分为四个矩形，配以二分查找，如果要找的数是6介于对角线上相邻的两个数4、10，可以排除掉左上和右下的两个矩形，而递归在左下和右上的两个矩形继续找，如下图所示：
[image]
2、定位法，时间复杂度O（m+n）。首先直接定位到最右上角的元素，再配以二分查找，比要找的数（6）大就往左走，比要找数（6）的小就往下走，直到找到要找的数字（6）为止，如下图所示：
[image]
代码忽略；
2017-5-22 牛顿迭代算法
题：不用库函数，编写一个函数，求整数N的开方
#define ABS(VAL) ((VAL>0)?(VAL):(-VAL))
double sqrt(float x)
{
double g0,g1;
g0=x/2;
g1=(g0+x/g0)/2;
while(ABS(g0-g1)>0.001)
{
go=g1;
g1=(g0+x/g0)/2;
}
return g1;
}
这题算是网上的标准解法了，拿来练下手；
