单链表逆置
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)的算法
。。。