算法

单链表逆置

    public void reverseNodeList() {
        //创建单链表9,8,7...0
        Node curr=null;//初始化尾节点为空
        for(int i=0;i<10;i++){
            Node tmp=new Node(curr,i);
            curr=tmp;
        }
        //逆转
        Node prev=null;//前一个节点默认为空
        while (curr!=null){
            if(curr==null||curr.next==null) {
                curr.next=prev;//如果当前节点或他的下一个节点为空,就使他指向前一个节点
                break;//结束,否则极易造成死循环
            }

            Node tmp=curr.next;//保存当前节点的下一个节点,作为下次循环的curr
            curr.next=prev;//当前节点指向前一个节点
            prev=curr;//当前节点变下一次循环的前一个节点
            curr=tmp;
        }
    }

判断单链表相交

问题a:两链表都是没环的

问题a:
1.因为都是单链表,所以在相交之后,相交点之后都是一样的节点,最后一个节点也一定是一样的(类推)
2.将A的尾节点指向b的头结点,B循环到尾节点,如果是b的头结点,也是证明最后一个节点是一样的

问题b:两链表环的情况不知道

先用追逐法判断单链表是否有环

判断有环的就是p0和p1都指向头结点,然后每次1走一步,b走两步,看走到的点是不是相同
(可以这么去理解,有n个站台,a每次走一个站台,b每次走两个,如果这是个线性的那么b永远在a前面,如果有环,就是b得往回走,那么a,肯定是会相遇的,会有可能不相遇吗?如果b不是走两步的话,是有可能的,b的步伐太大,正好跳过了相遇点,但是每次走两步,假设跳过去相遇点,那么就应该是相遇点的前一个节点,那么相遇点实际上就有两个方向了,这就与单链表相矛盾了)

3种情形,都没环就是问题a,1个有环1个无环不可能相交,两个都有环还相交,环一定是共有的,即a环的相遇点在b的环上(记住吧)

找出第一个相交点

  • 如果都没环(相交类比成一个Y字型),同样A的尾节点指向b的头结点,转换成用追逐法求环的那个偶遇点问题

  • 剩下两个都有环的情况,
    计算出两链表的长度lA、lB,(环的长度和环到入口点长度之和就是链表长度)
    如果lA>lB,则链表A指针先走lA-lB,然后链表B指针开始走,两者相遇的点就是相交点
    如果lB>lA,则链表B指针先走lB-lA,然后链表A指针开始走,两者相遇的点就是相交点

一、排序

排序分内部排序和外部排序(需不需要访问外存)
排序算法的稳定是值排序后 2 个相等键值的顺序和排序之前它们的顺序相同

1.冒泡排序(n^2,最好n,最差n^2,内部稳定)

        boolean noSwarp=true;
        int[] b={8,5,5,7,8};
        for(int i=0;i<b.length-1;i++){
            noSwarp=true;
            for(int j=b.length-1;j>i;j--){
                if (b[j]<b[j-1]) {
                    int tmp=b[j];
                    b[j]=b[j-1];
                    b[j-1]=tmp;
                    noSwarp=false;
                }
            }
            if(noSwarp){
                break;
            }
        }
public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}

2.选择排序(n^2,,内部不稳定)

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

3.插入排序(n^2,最好n,最差n^2,内部稳定)

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较,找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数,插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

4.希尔排序(以插入排序为基础)

public class ShellSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int gap = 1;
        //选择合适的步长
        while (gap < arr.length) {
            gap = gap * 3 + 1;
        }

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {//从第一组的第二个数开始
                int tmp = arr[i];//保存当前要插入的值
                int j = i - gap;//循环调整有序组内元素位置
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }

        return arr;
    }
}

5.快速排序(分治的思想)

public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }
	//分区算法!
    private int partition(int[] arr, int left, int right) {
        // 设定基准值(pivot)为最左边的数字
        int pivot = left;
        int index = pivot + 1;//index表示小于基准值的右边界索引+1,初始化为   left+1
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {//大于基准值时直接过,不过index不再累加,等找到下一个小于基准值的,再交换
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);//最后将基准值和小于基准值的右边界元素交换
        return index - 1;
    }
}

6.堆排序

Math.floor(n/2)的位置开始,不断调整堆,调整堆的操作是个递归的操作(例如建造大顶堆设置索引largest=i,将其和子节点三者最大值和i的值进行对调,largest指向原最大值的位置,如果i=largest,则递归结束了(因为堆的下面是有序的了),否则继续递归该节点)

7.归并排序

不断将原序列切分成两个子序列,调用

二、最长子序列和

内容节选自 http://www.cnblogs.com/conw/p/5896155.html

1.O(N^3)的算法

i从1到n,j从i到n,k从i到j算出以i,j为首尾的子序列的和,最大值即为所求。

2.O(N^2)的算法

sum[i]表示从1到i的和,求出sum,从第i个数到第j个数的和即sum[j]-sum[i-1]。

#include <stdio.h>
//N是数组长度,num是待计算的数组,sum是数组前缀和,放在全局区是因为可以开很大的数组
int N, num[16384], sum[16384];
int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);
    //计算数组前缀和
    sum[0] = 0;
    for(int i = 1; i <= N; i++) {
        sum[i] = num[i] + sum[i - 1];
    }
    int ans = num[1]; //ans保存最大子序列和,初始化为num[1]能保证最终结果正确
    //i和j分别是枚举的子序列的起点和终点
    for(int i = 1; i <= N; i++) {
        for(int j = i; j <= N; j++) {
            int s = sum[j] - sum[i - 1];
            if(s > ans) ans = s;
        }
    }
    printf("%d\n", ans);
    return 0;
}

3.分治O(N*logN)

#include <stdio.h>
//N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组
int N, num[16777216];
int solve(int left, int right)
{
    //序列长度为1时
    if(left == right)
        return num[left];
    //划分为两个规模更小的问题
    int mid = left + right >> 1;
    int lans = solve(left, mid);
    int rans = solve(mid + 1, right);
 
    //横跨分割点的情况
    int sum = 0, lmax = num[mid], rmax = num[mid + 1];
    for(int i = mid; i >= left; i--) {
        sum += num[i];
        if(sum > lmax) lmax = sum;
    }
    sum = 0;
    for(int i = mid + 1; i <= right; i++) {
        sum += num[i];
        if(sum > rmax) rmax = sum;
    }

    //答案是三种情况的最大值
    int ans = lmax + rmax;
    if(lans > ans) ans = lans;
    if(rans > ans) ans = rans;

    return ans;
}
int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);
    printf("%d\n", solve(1, N));
    return 0;
}

4.动态规划O(N)

我们用dp[n]表示以第n个数结尾的最大连续子序列的和,于是存在以下递推公式:dp[n] = max(0, dp[n-1]) + num[n]
仔细思考后不难发现这个递推公式是正确的,则整个问题的答案是max(dp[m]) | m∈[1, N]。

#include <stdio.h>

//N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组
int N, num[134217728];

int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);
    
    num[0] = 0;
    int ans = num[1];
    for(int i = 1; i <= N; i++) {
        if(num[i - 1] > 0) num[i] += num[i - 1];
        else num[i] += 0;
        if(num[i] > ans) ans = num[i];
    }

    printf("%d\n", ans);

    return 0;
}

没有创建另外的数组我感觉有点混乱...

5.又一个O(N)的算法

。。。

comments powered by Disqus