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