数据结构与算法

发表于 | 更新于: | 分类于 | | 阅读数

单链表逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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：两链表都是没环的

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

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

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

1
2
判断有环的就是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,内部稳定）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//我自己的，理解更合自己的胃口
   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;
       }
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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,,内部不稳定）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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,内部稳定）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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.希尔排序（以插入排序为基础）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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.快速排序（分治的思想）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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)的算法

。。。

坚持原创技术分享，您的支持将鼓励我继续创作！