package org.yousharp.pointatoffer.linkedlist;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.yousharp.common.ListNode;
import java.util.LinkedList;
/**
* there are N numbers in a circle, delete the Mth number every time
* from the circle and begin at the 0th number, the next begin number is the one
* that after the deleted number. What is the last number remained in the circle?
* User: Daniel
* Date: 14-1-17
* Time: 下午8:42
*/
public class LastNumberInCircle {
private static Logger logger = LoggerFactory.getLogger(LastNumberInCircle.class);
/**
* we construct a linked list, and delete the Mth element from the circle each time,
* remember to move the start node forward after each delete operation.
* @param head the head node of the link list
* @param m delete the Mth number from the list
* @return the last remaining number of the list
*/
public ListNode linkListSolution(ListNode head, int m) {
if (null == head) {
return null;
}
// link the last node to head to form a loop link list
ListNode loopNode = head;
while (null != loopNode.next) {
loopNode = loopNode.next;
}
loopNode.next = head;
// loop until there is only one node in the list
while (head.next != head) {
// first step: we need to find the node before the Mth node
ListNode preNode = head;
for (int i = 0; i < m - 2; i++) {
preNode = preNode.next;
}
// the node to delete (the Mth node)
ListNode delNode = preNode.next;
// delete the Mth node
preNode.next = delNode.next;
// the next start node
head = preNode.next;
}
return head;
}
/**
* we do not construct linked list, we use the standard library LinkedList;
* the key point is to get the next start number.
* @param numberList the LinkedList containing all te numbers
* @param m delete the Mth number from the list
* @param n the number of numbers in the list
* @return the last remaining number
*/
public int arrayListSolution(LinkedList<Integer> numberList, int m, int n) {
if (null == numberList || 0 == numberList.size()) {
return -1;
}
// start from 0
int start = 0;
while (n > 1) {
// get the index of the number to be deleted
int delIndex = (start + m - 1) % n;
numberList.remove(delIndex);
n = numberList.size();
// get the index of the next start number
start = delIndex;
if (start >= n) {
start = 0;
}
}
return numberList.getLast();
}
/**
* using the math recursive and implementing by loop:
* f(n,m) = f'(n-1,m) = (f(n-1,m)+m) % n;
* @param numberList the LinkedList containing all te numbers
* @param m delete the Mth number from the list
* @param n the number of numbers in the list
* @return the last remaining number in the list
*/
public int mathSolutionByLoop(LinkedList<Integer> numberList, int m, int n) {
if (null == numberList || 0 == numberList.size()) {
return -1;
}
// f(1,m) = 0;
int last = 0;
// f(n,m) = (f(n-1,m) + m) % n;
for (int i = 2; i <= n; i++) {
last = (last + m) % i;
}
return numberList.get(last);
}
/**
* using the math recursive method, and implementing by recursion:
* f(n,m) = (f(n-1,m) + m) % n
* @param m the Mth element to delete in each recursion
* @param n the number of numbers in the list
* @return the index of the last number in the list
*/
public int mathSolutionByRecursive(int m, int n) {
if (1 == n) {
return 0;
}
return (mathSolutionByRecursive(m, n - 1) + m) % n;
}
/**
* just for testing
* @param args
*/
public static void main(String[] args) {
LastNumberInCircle lastInstance = new LastNumberInCircle();
ListNode head = new ListNode(4);
ListNode node1 = head.next = new ListNode(7);
ListNode node2 = node1.next = new ListNode(9);
ListNode node3 = node2.next = new ListNode(2);
ListNode node4 = node3.next = new ListNode(13);
ListNode node5 = node4.next = new ListNode(98);
// ListNode node6 = node5.next = new ListNode(6);
logger.info("1. last value is: {}", lastInstance.linkListSolution(head, 4).value);
LinkedList<Integer> numberList = new LinkedList<Integer>();
numberList.add(4);
numberList.add(7);
numberList.add(9);
numberList.add(2);
numberList.add(13);
numberList.add(98);
// numberList.add(6);
LinkedList<Integer> numberList2 = new LinkedList<Integer>();
numberList2.addAll(numberList);
logger.info("2. last value is: {}", lastInstance.arrayListSolution(numberList, 4, 6));
logger.info("3. last value is: {}", lastInstance.mathSolutionByLoop(numberList2, 4, 6));
int index = lastInstance.mathSolutionByRecursive(4, 6);
logger.info("4. last value is: {}", numberList2.get(index));
}
}
/**
* 问题描述:给定数字序列,长度为n,如0, 1, 2, ... , n-1构成一个圆圈,从第一个数字开始,
* 每次从序列中删除第m个元素,删除一个元素后,从删除元素的下一个元素继续,问序列中最后剩下的元素。
* 思路:
* 1. 构造一个链表,每次从链表中删除第m个元素,直到链表总只剩最后一个元素。
* 复杂度:O(n^2);
* 2. 从数学的角度寻找规律:
* f(n,m): 表示从n个元素的序列删除m个元素后最后剩下的元素;
* 删除第m个元素后,序列变成了:0, 1, 2, ... , m-2, m, m+1, ..., n-1,即:
* m, m+1, ..., n-1, 0, 1, 2, ..., m-2
* 将该序列使用f'(n-1,m)表示,显然有f(n,m) = f'(n-1,m),因为最后剩下的数字时相同的。
* 原序列为的f(n-1,m)为:
* 0, 1, 2, ..., n-2
* 可见从f(n-1,m)-->f'(n-1, m)的映射关系为:(f(n-1,m)+m)%n,综合:f(n,m) = f'(n-1,m),得到:
* f(n,m) = f'(n-1,m) = (f(n-1),m) + m) % n;
* 所以只要得到f(n-1,m)即可得到f(n,m),而f(1,m) = 0;所以有:
* f(n,m) = f'(n-1,m) = (f(n-1),m) + m) % n; (n > 1)
* 然后递归或循环都可以实现。
* 复杂度:O(n)
* */
没有合适的资源?快使用搜索试试~ 我知道了~
数据结构、算法及常见面试题:java实现.zip
共43个文件
java:39个
xml:1个
gitignore:1个
需积分: 2 0 下载量 69 浏览量
2024-01-14
12:42:54
上传
评论
收藏 49KB ZIP 举报
温馨提示
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何具体存储。例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,使得计算机可以执行以求解问题。 算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生唯一的确定输出。 算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界法等。 算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
资源推荐
资源详情
资源评论
收起资源包目录
数据结构、算法及常见面试题:java实现.zip (43个子文件)
open_suanfayushujujiegouxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxcxvcvcv
README 209B
pom.xml 1KB
src
main
resources
log4j.properties 622B
java
org
yousharp
designpattern
singleton
PerfectSingleton.java 1KB
DoubleCheckSingleton.java 866B
LazySingleton.java 753B
EagerSingleton.java 697B
InnerClassSingleton.java 625B
StaticBlockSingleton.java 672B
pointatoffer
tree
RebuiltBinaryTree.java 3KB
TraverseBinaryTreeByTier.java 910B
CheckSubBinaryTree.java 3KB
FirstCommonParent.java 5KB
MirrorOfBinaryTree.java 2KB
linkedlist
DeleteOneNode.java 2KB
StraightPoker.java 3KB
FindKthNode.java 1KB
ReverseLinkList.java 1KB
LastNumberInCircle.java 6KB
PrintLinkedListReversely.java 2KB
MergeTwoSortedList.java 2KB
array
SearchInTwoDimensionArray.java 2KB
NumberOfOneBit.java 1KB
printOneToMaxNum.java 3KB
FindMinimumInRotatedArray.java 2KB
MakeOddBeforeEven.java 2KB
AdditionWithoutOperator.java 2KB
PrintMatrixClockWise.java 2KB
FindNumbersWithSum.java 1KB
Fibonacci.java 3KB
CalculatePow.java 2KB
searchsort
FindSmallestElement.java 3KB
stackqueue
StackByQueues.java 2KB
QueueByStacks.java 2KB
StackWithMinMethod.java 3KB
string
StringReplace.java 2KB
StringPermutation.java 2KB
StringToInt.java 2KB
common
Queue.java 1KB
Stack.java 895B
ListNode.java 337B
TreeNode.java 389B
.gitignore 32B
共 43 条
- 1
资源评论
极致人生-010
- 粉丝: 2930
- 资源: 2826
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功