java中printarray和selectsort方法-ag凯发k8国际
目录
1 左神部分集锦
2 leetcode前150题
3 牛客网剑指offer
4 javag
5 题目中的细节处理
1 左神部分集锦
1.1 code01_findnumber_b_in_a
在有序数组a中,找到b中(不)存在的数。public class code01_findnumber_b_in_a {
// 生成随机数组
public static int[] generaterandomarray(int maxsize, int maxvalue) {
int[] arr = new int[(int) ((maxsize 1) * math.random())];
for (int i = 0; i < arr.length; i ) {
arr[i] = (int) ((maxvalue 1) * math.random()) - (int) (maxvalue * math.random());
}
return arr;
}
// 二分法
public static int[] binary(int[] a, int[] b) {
if (a == null || b == null) {
return null;
}
int[] help = new int[b.length];
for (int i = 0; i < b.length; i ) {
int l = 0;
int r = a.length - 1;
while (l <= r) {
int mid = l (r - l) / 2;
if (b[i] < a[mid]) {
r = mid - 1;
} else if (b[i] > a[mid]) {
l = mid 1;
} else {
break;
}
}
if (l > r) {
help[i] = b[i];// 不在a中数
}
}
return help;
}
// 类似外排的方法
public static list waipai(int[] a, int[] b) {
arrays.sort(b);
list help = new arraylist<>();
int p1 = 0;
int p2 = 0;
while (p1 < a.length && p2 < b.length) {
if (a[p1] < b[p2]) {
p1 ;
} else if (a[p1] > b[p2]) {
p2 ;
} else {
help.add(b[p2]); //在a中的数
p1 ;
p2 ;
}
}
return help;
}
public static void main(string[] args) {
int amaxsize = 10;
int bmaxsize = 10;
int maxvalue = 100;
int[] a = generaterandomarray(amaxsize, maxvalue);
int[] b = generaterandomarray(bmaxsize, maxvalue);
//int[] a = { 1, 2, 3, 4, 5 };
//int[] b = { 1, 6, 3 ,5};
int[] res = binary(a, b);
//list list = waipai(a, b);
system.out.println(arrays.tostring(a));
system.out.println(arrays.tostring(b));
system.out.println(arrays.tostring(res));
//for (integer integer : list) {
//system.out.print(integer " ");
//}
}
}
1.2 code02_bubblesortpublic class code02_bubblesort {
public static void bubblesort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j ) {
if (arr[j] > arr[j 1]) {
swap(arr, j, j 1);
}
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static int[] generaterandomarray(int maxsize, int maxvalue) {
int[] arr = new int[(int)((maxsize 1) * math.random())];
for(int i =0; i < arr.length; i ) {
arr[i] = (int)((maxvalue 1)*math.random()) - (int)(maxvalue * math.random());
}
return arr;
}
public static void main(string[] args) {
int maxsize = 20;
int maxvalue = 100;
int[] arr = generaterandomarray(maxsize, maxvalue);
system.out.println(arrays.tostring(arr));
bubblesort(arr);
system.out.println(arrays.tostring(arr));
}
}
1.3 code03_insertsortpublic class code03_insertsort {
public static void insertsort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i ) {
for (int j = i - 1; j > -1; j--) {
if (arr[j] > arr[j 1]) {
swap(arr, j, j 1);
}
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(string[] args) {
int[] a = {4,1,2,7,40,35,51};
system.out.println(arrays.tostring(a));
insertsort(a);
system.out.println(arrays.tostring(a));
}
}
1.4 code04_selectsortpublic class code04_selectsort {
public static void selectsort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i ) {
int minindex = i;
for (int j = i 1; j < arr.length; j ) {
if (arr[j] < arr[minindex]) {
minindex = j;
}
}
swap(arr, i, minindex);
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static int[] generaterandomarray(int maxsize, int maxvalue) {
int[] arr = new int[(int)((maxsize 1)*math.random())];
for(int i=0;i
arr[i] = (int)((maxvalue 1)*math.random())-(int)(maxvalue * math.random());
}
return arr;
}
public static void main(string[] args) {
int[] arr = generaterandomarray(10, 50);
system.out.println(arrays.tostring(arr));
selectsort(arr);
system.out.println(arrays.tostring(arr));
}
}
1.5 code05_mergesortpublic class code05_mergesort {
public static void mergesort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergesort(arr, 0, arr.length - 1);
}
private static void mergesort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l (r - l) / 2;
mergesort(arr, l, mid);
mergesort(arr, mid 1, r);
merge(arr, l, mid, r);
}
private static void merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l 1];
int index = 0;
int p1 = l;
int p2 = mid 1;
while (p1 <= mid && p2 <= r) {
help[index ] = arr[p1] < arr[p2] ? arr[p1 ] : arr[p2 ];
}
while (p1 <= mid) {
help[index ] = arr[p1 ];
}
while (p2 <= r) {
help[index ] = arr[p2 ];
}
for (int i = 0; i < help.length; i ) {
arr[l i] = help[i];
}
}
public static void main(string[] args) {
// todo auto-generated method stub
int[] arr = new int[] { 2, 5, 1, 3, 6, 2, 1 };
mergesort(arr);
system.out.println(arrays.tostring(arr));
}
}
1.6 code06_smallnumbersum
小和问题:在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。public class code06_smallnumbersum {
public static int getsum(int[] arr) {
if(arr==null || arr.length < 2) {
return 0;
}
return mergesort(arr, 0, arr.length - 1);
}
private static int mergesort(int[] arr, int l, int r) {
if(l == r) {
return 0;
}
int mid = l (r - l) / 2;
return mergesort(arr, l, mid) mergesort(arr, mid 1, r) merge(arr, l, mid, r);
}
private static int merge(int[] arr, int l, int mid, int r) {
int sum = 0;
int[] help = new int[r - l 1];
int index = 0;
int p1 = l;
int p2 = mid 1;
while(p1 <= mid && p2 <= r) {
sum = arr[p1] < arr[p2] ? (r - p2 1) * arr[p1] : 0;
help[index ] = arr[p1] < arr[p2] ? arr[p1 ] : arr[p2 ];
}
while(p1 <= mid) {
help[index ] = arr[p1];
}
while(p2 <= r) {
help[index ] = arr[p2 ];
}
for(int i =0 ; i < help.length; i ) {
arr[l i] = help[i];
}
return sum;
}
public static void main(string[] args) {
// todo auto-generated method stub
int[] arr = new int[]{1,3,4,2,5};
system.out.print(getsum(arr));
}
}
// output:16
1.7 code07_quicksort
随机快排public class code07_quicksort {
public static void quicksort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quicksort(arr, 0, arr.length - 1);
}
private static void quicksort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l (int) (math.random() * (r - l 1)), r);
int[] p = partition(arr, l, r);
quicksort(arr, l, p[0] - 1);
quicksort(arr, p[1] 1, r);
}
}
private static int[] partition(int[] arr, int l, int r) {
int less = l-1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, l , less);
} else if (arr[l] > arr[r]) {
swap(arr, l, --more);
} else {
l ;
}
}
swap(arr, more, r);
return new int[] { less 1, more };
}
public static int[] generaterandomarray(int maxsize, int maxvalue) {
int[] arr = new int[(int) ((maxsize 1) * math.random())];
for (int i = 0; i < arr.length; i ) {
arr[i] = (int) ((maxvalue 1) * math.random()) - (int) (maxvalue * math.random());
}
return arr;
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* @param args
*/
public static void main(string[] args) {
// todo auto-generated method stub
int[] arr = generaterandomarray(20, 20);
system.out.println(arrays.tostring(arr));
quicksort(arr);
system.out.println(arrays.tostring(arr));
}
}
1.8 code08_heapsortpublic class code08_heapsort {
public static void heapsort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//���������
for (int i = 0; i < arr.length; i ) {
heapinsert(arr, i);
}
int size = arr.length - 1;
swap(arr, size, 0);
while(size > 0) {
heapify(arr, 0, size);
swap(arr, --size, 0);
}
}
// ��������β�������ϱƚ�
private static void heapinsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// �ѷ�Ԫ�ظı䣬���±ƚ�
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 1;
while(left < size) {
int largest = left 1 < size && arr[left] < arr[left 1] ? left 1: left;
largest = arr[largest] > arr[index]? largest: index;
if(largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 1;
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* @param args
*/
public static void main(string[] args) {
// todo auto-generated method stub
int[] arr = new int[]{3, 6, 3, 2, 9, 0};
system.out.println(arrays.tostring(arr));
heapsort(arr);
system.out.println(arrays.tostring(arr));
}
}
1.9 code09_mediumnumber
在一段数据流中,找到中位数public class code09_mediumnumber {
private int cnt = 0;
private priorityqueue low = new priorityqueue();
private priorityqueue high = new priorityqueue(new comparator() {
public int compare(integer o1, integer o2) {
return o2.compareto(o1);
}
});
public void insert(integer num) {
cnt ;
if((cnt & 1) == 1) {
if(!low.isempty() && num > low.peek()) {
low.offer(num);
num = low.poll();
}
high.offer(num);
}else {
if(!high.isempty() && num < high.peek()) {
high.offer(num);
num = high.poll();
}
low.offer(num);
}
}
public double germidian() {
double res = 0;
if((cnt & 1) == 1) {
res = high.peek();
}else {
res = (high.peek() low.peek()) / 2.0;
}
return res;
}
}
1.10 code10_maxgap
给定一个数组,求如果排序之后,相邻两个数的最大差值,时间复杂度o(n),不能基于比较的排序。public class code10_maxgap {
public static int maxgap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = integer.max_value;
int max = integer.min_value;
for (int i = 0; i < len; i ) {
min = math.min(min, nums[i]);
max = math.max(max, nums[i]);
}
if (min == max) {
return 0;
}
boolean[] hasnum = new boolean[len 1];
int[] maxs = new int[len 1];
int[] mins = new int[len 1];
int bid;
for (int i = 0; i < len; i ) {
bid = bucket(nums[i], len, min, max);
mins[bid] = hasnum[bid] ? math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasnum[bid] ? math.max(maxs[bid], nums[i]) : nums[i];
hasnum[bid] = true;
}
int res = 0;
int lastmax = maxs[0];
for (int i = 1; i <= len; i ) {
if (hasnum[i]) {
res = math.max(res, mins[i] - lastmax);
lastmax = maxs[i];
}
}
return res;
}
private static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
/**
* @param args
*/
public static void main(string[] args) {
// todo auto-generated method stub
int[] arr = new int[]{1,5,2,1,5,2,7,6,9,2};
//arrays.sort(arr);
system.out.println(arrays.tostring(arr));
system.out.print(maxgap(arr));
}
}
1.11 code11_array_stack_queue
用数组结构实现大小固定的队列和栈。
注意队列和栈需要的类属性和指针的变化。public class code11_array_stack_queue {
public static class arraystack {
private integer[] arr;
private integer size;// ջ��ָ��
public arraystack(int initsize) {
if (initsize < 0) {
throw new illegalargumentexception("size is less than 0");
}
arr = new integer[initsize];
size = 0;
}
public integer peek() {
if (size == 0) {
return null;
}
return arr[size - 1];
}
public void push(int obj) {
if (size == arr.length) {
throw new arrayindexoutofboundsexception("the stack is full");
}
arr[size ] = obj;
}
public integer pop() {
if (size == 0) {
throw new arrayindexoutofboundsexception("the stack is empty");
}
return arr[--size];
}
}
public static class arrayqueue {
private integer[] arr;
private integer size;
private integer first;
private integer last;
public arrayqueue(int initsize) {
if (initsize < 0) {
throw new illegalargumentexception("size is less than 0");
}
arr = new integer[initsize];
size = 0;
first = 0;
last = 0;
}
public integer peek() {
if (size == 0) {
return null;
}
return arr[first];
}
public void push(int obj) {
if (size == arr.length) {
throw new arrayindexoutofboundsexception("the queue is full");
}
size ;
arr[last] = obj;
last = last == arr.length - 1 ? 0 : last 1;
}
public integer poll() {
if (size == 0) {
throw new arrayindexoutofboundsexception("the queue is empty");
}
size--;
int temp = arr[first];
first = first == arr.length - 1 ? 0 : first 1;
return temp;
}
}
}
1.12 code12_getminstack
实现一个特殊的栈,在栈的基础上增加返回最小元素的操作。
· 思路:准备两个栈,data栈正常压栈,min栈需要比较当前数和栈顶数的大小。public class code12_getminstack {
private stack stackdata;
private stack stackmin;
public code12_getminstack() {
this.stackdata = new stack();
this.stackmin = new stack();
}
public void push(int newnum) {
if (this.stackmin.isempty()) {
this.stackmin.push(newnum);
} else if (newnum < this.getmin()) {
this.stackmin.push(newnum);
} else {
int newmin = this.stackmin.peek();
this.stackmin.push(newmin);
}
this.stackdata.push(newnum);
}
public integer getmin() {
if (this.stackmin.isempty()) {
throw new runtimeexception("your stack is empty");
}
return this.stackmin.peek();
}
}
1.13 code13_stack_convert_queuepublic class code13_stack_convert_queue {
public static class stacktoqueue{
private stack stackpush;
private stack stackpop;
public stacktoqueue() {
this.stackpush = new stack();
this.stackpop = new stack();
}
public void push(int pushint) {
stackpush.push(pushint);
}
public int poll() {
//empty()��isempty������ͬ��
if(stackpop.isempty() && stackpush.isempty()) {
throw new runtimeexception("queue is empty");
}else if(stackpop.isempty()) {
while(!stackpush.isempty()) {
stackpop.push(stackpush.pop());
}
}
return stackpop.pop();
}
public int peek() {
if(stackpop.isempty() && stackpush.isempty()) {
throw new runtimeexception("queue is empty");
}else if(stackpop.isempty()) {
while(!stackpush.isempty()) {
stackpop.push(stackpush.pop());
}
}
return stackpop.peek();
}
}
public static class queuetostack{
private queue queue;
private queue help;
public queuetostack() {
this.queue = new linkedlist();
this.help = new linkedlist();
}
public void push(int pushint) {
queue.offer(pushint);
}
public int peek() {
if(queue.isempty()) {
throw new runtimeexception("stack is empty");
}
while(queue.size() != 1) {
help.offer(queue.poll());
}
int res = queue.poll();
queue temp = help;
help = queue;
queue = temp;
return res;
}
}
}
1.14 code14_printmatrixspiralorderpublic class code14_printmatrixspiralorder {
public static void printmatrix(int[][] matrix) {
int tr = 0;
int tc = 0;
int dr = matrix.length - 1;// ����
int dc = matrix[0].length - 1;// ����
while (tr <= dr && tc <= dc) {
printedge(matrix, tr , tc , dr--, dc--);
}
}
public static void printedge(int[][] m, int tr, int tc, int dr, int dc) {
if (tr == dr) {
for (int i = tc; i <= dc; i ) {
system.out.print(m[tr][i] " ");
}
} else if (tc == dc) {
for (int i = tr; i <= dr; i ) {
system.out.print(m[i][tc] " ");
}
} else {
int curc = tc;
int curr = tr;
while (curc != dc) {
system.out.print(m[tr][curc] " ");
curc ;
}
while (curr != dr) {
system.out.print(m[curr][dc] " ");
curr ;
}
while (curc != tc) {
system.out.print(m[dr][curc] " ");
curc--;
}
while (curr != tr) {
system.out.print(m[curr][tc] " ");
curr--;
}
}
}
public static void main(string[] args) {
// todo auto-generated method stub
int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
printmatrix(matrix);
}
}
1.15 code15_rotatematrixpublic class code15_rotatematrix {
public static void rotate(int[][] matrix) {
int ax = 0;
int ay = 0;
int bx = matrix.length - 1;
int by = matrix[0].length - 1;
while(ax < bx) {
rotateedge(matrix, ax , ay , bx--, by--);
}
}
public static void rotateedge(int[][] m, int ax, int ay, int bx, int by) {
int times = by - ay;
int tmp = 0;
for(int i = 0; i != times; i ) {
tmp = m[ax][ay i];
m[ax][ay i] = m[bx - i][ay];
m[bx - i][ay] = m[bx][by - i];
m[bx][by - i] = m[ax i][by];
m[ax i][by] = tmp;
}
}
public static void printmatrix(int[][] matrix) {
for(int i = 0; i < matrix.length; i ) {
for(int j = 0; j < matrix[0].length; j ) {
system.out.print(matrix[i][j] " ");
}
system.out.println();
}
}
public static void main(string[] args) {
// todo auto-generated method stub
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
printmatrix(matrix);
rotate(matrix);
system.out.println("==============");
printmatrix(matrix);
}
}
1.16 code16_zigzagprintmatrixpublic class code16_zigzagprintmatrix {
public static void printmatrixzigzag(int[][] matrix) {
int tr = 0;
int tc = 0;
int dr = 0;
int dc = 0;
int endr = matrix.length - 1;
int endc = matrix[0].length - 1;
boolean fromup = false;
while (tr != endr 1) {
printlevel(matrix, tr, tc, dr, dc, fromup);
tr = tc == endc ? tr 1 : tr;
tc = tc == endc ? tc : tc 1;
dc = dr == endr ? dc 1 : dc;
dr = dr == endr ? dr : dr 1;
fromup = !fromup;
}
system.out.println();
}
public static void printlevel(int[][] m, int tr, int tc, int dr, int dc,
boolean f) {
if (f) {
while (tr != dr 1) {
system.out.print(m[tr ][tc--] " ");
}
} else {
while (dr != tr - 1) {
system.out.print(m[dr--][dc ] " ");
}
}
}
public static void main(string[] args) {
// todo auto-generated method stub
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
printmatrixzigzag(matrix);
}
}
1.17 code17_findnuminsortedmatrixpublic class code17_findnuminsortedmatrix {
public static boolean iscontains(int[][] matrix, int k) {
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == k) {
return true;
} else if (matrix[row][col] < k) {
row ;
} else {
col--;
}
}
return false;
}
public static void main(string[] args) {
// todo auto-generated method stub
int[][] matrix = new int[][] { { 0, 1, 2, 3, 4, 5, 6 }, // 0
{ 10, 12, 13, 15, 16, 17, 18 }, // 1
{ 23, 24, 25, 26, 27, 28, 29 }, // 2
{ 44, 45, 46, 47, 48, 49, 50 }, // 3
{ 65, 66, 67, 68, 69, 70, 71 }, // 4
{ 96, 97, 98, 99, 100, 111, 122 }, // 5
{ 166, 176, 186, 187, 190, 195, 200 }, // 6
{ 233, 243, 321, 341, 356, 370, 380 } // 7
};
int k = 233;
system.out.println(iscontains(matrix, k));
}
}
1.18 code18_ispalindromelistpublic class code18_ispalindromelist {
public static class node{
public int value;
public node next;
public node(int data) {
this.value = data;
}
}
//�۵�����
public static boolean ispalindrome(node head) {
if( head == null || head.next == null) {
return true;
}
node n1 = head;
node n2 = head;
while(n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
//n1ϊ�е�
n2 = n1.next;
n1.next = null;
node n3 = null;
while(n2 != null) {
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
n3 = n1;
n2 = head;
boolean res = true;
while(n1 != null && n2 != null) {
if(n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next;
n2 = n2.next;
}
//��ԭ����
n1 = n3.next;
n3.next = null;
while(n1 != null) {
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
}
1.19 code19_smallerequalbiggerpublic class code19_smallerequalbigger {
public static class node{
public int value;
public node next;
public node (int data) {
this.value = data;
}
}
public static node listpartition(node head, int pivot) {
if(head == null) {
return head;
}
node cur = head;
int i = 0;
while(cur != null) {
i ;
cur = cur.next;
}
node[] nodearr = new node[i];
i = 0;
cur = head;
//������ת�ɽڵ�����
for(; i != nodearr.length; i ) {
nodearr[i] = cur;
cur = cur.next;
}
arrpartition(nodearr, pivot);
for(i = 1; i < nodearr.length; i ) {
nodearr[i - 1].next = nodearr[i];
}
nodearr[i - 1].next = null;
return nodearr[0];
}
public static void arrpartition (node[] nodearr, int pivot) {
int less = -1;
int more = nodearr.length;
int index = 0;
while(less < more) {
if(nodearr[index].value < pivot) {
swap(nodearr, index , less);
}else if(nodearr[index].value > pivot) {
swap(nodearr, index, --more);
}else {
index ;
}
}
}
public static void swap(node[] arr, int a, int b) {
node temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
1.20 code20_copylistwithrandompublic class code20_copylistwithrandom {
public static class node{
public int value;
public node next;
public node rand;
public node(int data) {
this.value = data;
}
}
//���븴�ƽڵ�
public static node copylistwithrand(node head) {
if(head == null) {
return null;
}
node cur = head;
node next = null;
while(cur != null) {
next = cur.next;
cur.next = new node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
node curcopy = null;
while(cur != null) {
next = cur.next.next;
curcopy = cur.next;
curcopy.rand = cur.rand == null ? null : cur.rand.next;
cur = next;
}
node res = head.next;
cur = head;
while(cur != null) {
next = cur.next.next;
curcopy = cur.next;
cur.next = next;
curcopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
}
1.21 code21_findfirstintersectnodepublic class code21_findfirstintersectnode {
public static class node{
public int value;
public node next;
public node(int data) {
this.value = data;
}
}
public static node getintersectnode(node head1, node head2) {
if(head1 == null || head2 == null) {
return null;
}
node loop1 = getloopnode(head1);
node loop2 = getloopnode(head2);
if(loop1 == null && loop2 == null) {
return noloop(head1, head2);
}
if(loop1 != null && loop2 != null) {
return bothloop(head1, loop1, head2, loop2);
}
return null;
}
private static node bothloop(node head1, node loop1, node head2, node loop2) {
// todo �զ����ɵķ������
node cur1 = null;
node cur2 = null;
if(loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while(cur1 != loop1) {
n ;
cur1 = cur1.next;
}
while(cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = math.abs(n);
while(n != 0) {
n--;
cur1 = cur1.next;
}
while(cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}else {
cur1 = loop1.next;
while(cur1 != loop1) {
if(cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}
private static node noloop(node head1, node head2) {
// todo �զ����ɵķ������
node cur1 = head1;
node cur2 = head2;
int n = 0;
while(cur1.next != null) {
n ;
cur1 = cur1.next;
}
while(cur2.next != null) {
n--;
cur2 = cur2.next;
}
if(cur1 != cur2) {
return null;
}
cur1 = n > 0 ? head1: head2;
cur2 = cur1 == head1 ? head2 : head1;
n = math.abs(n);
while(n != 0) {
n--;
cur1 = cur1.next;
}
while(cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
public static node getloopnode(node head) {
// todo �զ����ɵķ������
if(head == null || head.next == null || head.next.next == null) {
return null;
}
node n1 = head.next;
node n2 = head.next.next;
while(n1 != n2) {
if(n2.next == null || n2.next.next == null) {
return null;
}
n1 = n1.next;
n2 = n2.next.next;
}
n2 = head;
while(n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
}
总结
以上是ag凯发k8国际为你收集整理的java中printarray和selectsort方法_算法题(一)的全部内容,希望文章能够帮你解决所遇到的问题。
- 上一篇:
- 下一篇: 1803无法升级到2004_微软向win