javaSE之数组
== 现在有一个单向链表，谈一谈，如何判断链表中是否出现了环==
单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。
// 链表的节点结构如下 typedef struct node { int data; struct node *next; } NODE;
最常用方法：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。
通过使用STL库中的map表进行映射。首先定义 map<NODE *, int> m; 将一个 NODE * 指针映射成数组的下标，并赋值为一个 int 类型的数值。然后从链表的头指针开始往后遍历，每次遇到一个指针p，就判断 m[p] 是否为0。如果为0，则将m[p]赋值为1，表示该节点第一次访问；而如果m[p]的值为1，则说明这个节点已经被访问过一次了，于是就形成了环。
<mark>谈一谈，bucket如果用链表存储，它的缺点是什么？</mark>
①查找速度慢，因为查找时，需要循环链表访问
②如果进行频繁插入和删除操作，会导致速度很慢。
== 有一个链表，奇数位升序偶数位降序，如何将链表变成升序==
public class OddIncreaseEvenDecrease {
/** * 按照奇偶位拆分成两个链表 */
public static Node[] getLists(Node head) {
Node head1=null;
Node head2=null;
Node cur1=null;
Node cur2=null;
int count=1;//用来计数
while (head!=null) {
if (count%2==1) {
if (cur1!=null) {
cur1.next=head;
cur1=cur1.next;
}else {
cur1=head;
head1=cur1;
}
}else {
if (cur2!=null) {
cur2.next=head;
cur2=cur2.next;
}else {
cur2=head;
head2=cur2;
}
}
head=head.next;
count++;
}
//跳出循环，记得最后两个末尾的下一个元素指向null
cur1.next=null;
cur2.next=null;
Node[] nodes=new Node[] {head1,head2};
return nodes;
}
/** * 反转链表 */
public static Node reverseList(Node head) {
Node pre=null;
Node next=null;
while (head!=null) {
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
/** * 合并两个有序链表 */
public static Node combineList(Node head1,Node head2) {
if (head1==null||head2==null) {
return head1!=null? head1:head2;
}
Node head=head1.val<head2.val? head1:head2;
Node cur1=head==head1? head1:head2;
Node cur2=head==head1? head2:head1;
Node pre=null;
Node next=null;
while (cur1!=null&&cur2!=null) {
//这里一定要有=，否则一旦cur1的value和cur2的value相等的话，
//下面的pre.next会出现空指针异常
if (cur1.val<=cur2.val) {
pre=cur1;
cur1=cur1.next;
}else {
next=cur2.next;
pre.next=cur2;
cur2.next=cur1;
pre=cur2;
cur2=next;
}
}
pre.next=cur1==null? cur2:cur1;
return head;
}
}
class Node{
Node next;
int val=0;
public Node(int val) {
this.val=val;
}
}
<mark>随机链表的复制</mark>
//随机链表的复制
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
RandomListNode p = head;
// copy every node and insert to list
while (p != null) {
RandomListNode copy = new RandomListNode(p.label);
copy.next = p.next;
p.next = copy;
p = copy.next;
}
// copy random pointer for each new node
p = head;
while (p != null) {
if (p.random != null)
p.next.random = p.random.next;
p = p.next.next;
}
// break list to two
p = head;
RandomListNode newHead = head.next;
while (p != null) {
RandomListNode temp = p.next;
p.next = temp.next;
if (temp.next != null)
temp.next = temp.next.next;
p = p.next;
}
return newHead;
}
<mark>一个数组，除一个元素外其它都是两两相等，求那个元素?</mark>
public static int find1From2(int[] a){
int len = a.length, res = 0;
for(int i = 0; i < len; i++){
res= res ^ a[i];
}
return res;
}
<mark>找出数组中和为S的一对组合，找出一组就行</mark>
//从数组中找出一对数和为S的一对数
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] a = new int[2];
map.put(nums[0], 0);
for (int i = 1; i < nums.length;i++) {
if (map.containsKey(target - nums[i])) {
a[0] = map.get(target -nums[i]);
a[1] = i;
return a;
} else {
map.put(nums[i], i);
}
}
return a;
}
<mark>求一个数组中连续子向量的最大和</mark>
//求一个数组中连续子向量的最大和
public class FindGreatestSumOfSubArray {
public int findGreatestSumOfSubArray(int[] array) {
int sum = array[0];
int max = array[0];
for(int i = 1;i < array.length;i ++) {
//前面sum大于0，认为是有贡献的，可以叠加在上面。否则认为没有贡献，另起炉灶
if(sum >= 0) {
sum = sum + array[i];
}
else {
sum = array[i];
}
if(sum > max) {
max = sum;
}
}
return max;
}
<mark>介绍一下，排序都有哪几种方法？请列举出来。</mark>
排序的方法有：插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），
归并排序，分配排序（箱排序、基数排序）
快速排序的伪代码。
/ /使用快速排序方法对a[ 0 :n- 1 ]排序
从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点
把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点
递归地使用快速排序方法对left 进行排序
递归地使用快速排序方法对right 进行排序
所得结果为l e f t + m i d d l e + r i g h t
查看30道真题和解析