開心學演算法的第四天
環形單鏈表
環形串列結構
構造環形串列
class singleLinked<E>{
//環形串列頭節點
private Node<E> head;
//環形串列元素個數
private int size;
class Node<E>{
private E val;
private Node<E> next;
public Node(E val){
this.val = val;
}
}
}
添加元素
//添加元素
public void add(E val){
//如果是空鏈表
if (head == null){
head = new Node<>(val);
head.next = head;
size++;
return;
}
//非空鏈表常規操作
Node newNode = new Node(val);
//快取頭節點
Node node = head;
//遍歷至尾結點出
while (node.next != head){
node = node.next;
}
//將節點加在尾部
node.next = newNode;
newNode.next = head;
size++;
}
洗掉元素
洗掉元素：分三種情況
1.洗掉頭節點
洗掉頭節點要找到鏈表的最后一個節點，然后head后移一個也就是
head = head.next，然后使最后一個節點的next指向head即可，
2.洗掉鏈表僅有的一個節點
這里需要用size進行判斷，我的size先進行了減減操作，所有條件是
size == 0就可以直接head= null洗掉成功直接回傳，
3.洗掉常規的節點
定義一個快指標node，慢指標low然后然后找到要洗掉的節點，使用
low = low.next就可以洗掉當前node節點，
//洗掉指定位置元素
public boolean remove(E val){
//判斷鏈表為空
if (head == null){
System.out.println("鏈表為空洗掉失敗");
return false;
}
size--;
//洗掉頭節點
if (head.val == val && size != 0){
//找到尾結點
Node tail = head;
while (tail.next != head){
tail = tail.next;
}
head = head.next;
tail.next = head;
return true;
}else if (size == 0){
//表示的是洗掉最后一個節點
head = null;
return true;
} else{
//洗掉平常節點
Node node = head;
Node low = head;
while(node.val != val){
low = node;
node = node.next;
}
low.next = low.next.next;
return true;
}
}
列印當前鏈表
//列印鏈表
public void showLinked(){
if (head == null){
System.out.println("鏈表為空");
return;
}
Node node = head;
int index = 0;
while(index++ < size){
System.out.print(node.val+" ");
node = node.next;
}
}
獲取節點個數
//獲取鏈表有效個數
public int getSize(){
return this.size;
}
所有代碼
class singleLinked<E>{
private Node<E> head;
private int size;
class Node<E>{
private E val;
private Node<E> next;
public Node(E val){
this.val = val;
}
}
//添加元素
public void add(E val){
//如果是空鏈表
if (head == null){
head = new Node<>(val);
head.next = head;
size++;
return;
}
//非空鏈表常規操作
Node newNode = new Node(val);
//快取頭節點
Node node = head;
//遍歷至尾結點出
while (node.next != head){
node = node.next;
}
//將節點加在尾部
node.next = newNode;
newNode.next = head;
size++;
}
//洗掉指定位置元素
public boolean remove(E val){
//判斷鏈表為空
if (head == null){
System.out.println("鏈表為空洗掉失敗");
return false;
}
size--;
//洗掉頭節點
if (head.val == val && size != 0){
//找到尾結點
Node tail = head;
while (tail.next != head){
tail = tail.next;
}
head = head.next;
tail.next = head;
return true;
}else if (size == 0){
//表示的是洗掉最后一個節點
head = null;
return true;
} else{
//洗掉平常節點
Node node = head;
Node low = head;
while(node.val != val){
low = node;
node = node.next;
}
low.next = low.next.next;
return true;
}
}
//列印鏈表
public void showLinked(){
if (head == null){
System.out.println("鏈表為空");
return;
}
Node node = head;
int index = 0;
while(index++ < size){
System.out.print(node.val+" ");
node = node.next;
}
}
//獲取鏈表有效個數
public int getSize(){
return this.size;
}
}
約瑟夫環問題
問題描述：
num個人圍成一圈對其進行編號從第一個人開始報數，每當到第count個時當前這個人出局，然后下一個人從1開始繼續依次類推到最后剩余的那個人，列印出剩余那個人的編號，
陣列解法
/**
* 問題描述：
* num個人圍成一圈從第一個人開始報數，每當到第count個時當前這個人出局
* 然后下一個人從1開始繼續依次類推到最后剩余的那個人，列印出剩余那個人的編號
* @param num 表示一個幾個人
* @param count 報的數字
*/
public static void joseph(int num,int count){
//初始化arr陣列
int[] arr = new int[num];
for (int i = 0; i < arr.length; i++) {
arr[i] = i+1;
}
//創建相同長度的boolean陣列標記是否已經出局
boolean[] flag = new boolean[arr.length];
//查看陣列中剩余的元素
int residue = arr.length;
//用來計數
int number = 1;
while(residue != 1){
for (int i = 0;i < arr.length;i++){
if (number % count == 0 && !flag[i]){
flag[i] = true;
residue--;
number++;
}
if (flag[i]){
continue;
}
number++;
}
}
//列印最后一個元素
for (int i = 0; i < arr.length; i++) {
if (!flag[i]){
System.out.println("最后一個元素"+arr[i]);
}
}
}
鏈表解法
使用上面的環形鏈表即可求解，
回圈的條件直接是getsize == 1就可以判斷當前只剩一個人，每次移除掉指定節點即可，這種做法相對于陣列的解法簡單且清晰，
//約瑟夫環問題
public void joseph(int num,int count){
//構建鏈表
Node node = head;
int i = 1;
while (getSize() != 1){
if (i%count==0) {
remove((E) node.val);
}
i++;
node = node.next;
}
System.out.println(head.val);
}
點個贊唄~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/252671.html
標籤：java
上一篇：一個小案例精通lamda運算式