/**
* 单向链表实现
*/
public class LinkedListForAlgorithm<E> {
private Node<E> first;
private Node<E> last;
private int size;
/**
* 一个私有的静态内部类作为链表的元素
* 这里由于后面的算法题中需要使用到这个
* 静态内部类，所以把其写成public的，并
* 把其成员变量也写成public的
* @author Peter
*/
public static class Node<E>{
public Node<E> next;
public E item;
public Node(){
}
public Node(E e){
this.item=e;
}
@Override
public String toString() {
if (item == null) {
return "null";
}
return item.toString();
}
}
public void add(E e){
Node<E> toAddNode=new Node<E>(e);
//如果第一个为null证明现在是在添加第一个元素
if(first==null && last==null){
//那么就将第一个元素设为这个添加的元素
first=toAddNode;
//将末尾元素设为这个添加的元素
last=toAddNode;
this.size++;
return;
}
//原有的last的下一个设置为本个
last.next=toAddNode;
//然后把现在的last设置为本个
last=toAddNode;
this.size++;
}
public boolean contains(E e) {
//从第一个开始往下一个一个找，所以慢
Node<E> current = first;
while (current != null) {
if (current.item.equals(e)) {
return true;
}
//没找到就往下继续找
current = current.next;
}
/*
* 如果都到最后一个元素了（末尾元素为null了）
* 还是没找到，那么就返回不包含。
*/
return false;
}
public E remove(){
if(this.first==null||this.size==0){
throw new RuntimeException("集合为空，不能在删除元素！");
}
Node<E> toRemoveNode=first;
first=toRemoveNode.next;
size--;
return toRemoveNode.item;
}
public boolean remove(E e) {
//第一个元素如果为null说明集合为空抛异常
if (this.first == null || this.size == 0) {
throw new RuntimeException("集合为空！");
}
Node<E> current = first;
while (current!=null) {
Node<E> toRemoveNode = current.next;
/*
* 要删除的元素为第一个元素
* 那么将第一个元素删除
*/
if(current.item.equals(e)){
remove();
return true;
}
/*
* 如果要删除的元素为null，
* 证明集合中不包含要删除的元素，
* 直接跳出循环返回false
*/
if(toRemoveNode==null){
break;
}
/*
* 找到要删除元素的上一个元素
* 要删除元素的上一个元素为：current
* 要删除元素为：current.next
*/
if (toRemoveNode.item.equals(e)) {
//执行删除操作
current.next = toRemoveNode.next;
toRemoveNode.next = null;
toRemoveNode.item = null;
toRemoveNode = null;
this.size--;
return true;
}
//没找到就往下继续找
current = current.next;
}
/*
* 如果都到最后一个元素了（末尾元素为null了）
* 还是没找到，那么就返回false，表示删除失败！。
*/
return false;
}
public Node<E> getFirst() {
return first;
}
public void setFirst(Node<E> first) {
this.first = first;
}
public Node<E> getLast() {
return last;
}
public void setLast(Node<E> last) {
this.last = last;
}
public int getSize() {
return size;
}
@Override
public String toString() {
if (this.first == null || this.size == 0) {
return "[]";
}
String toStr = "[";
Node<E> current = first;
while (current!= null) {
toStr = toStr+current.toString()+",";
current = current.next;
}
return toStr.substring(0,toStr.length()-1)+"]" ;
}
public static void main(String[] args) {
}
}
/**
* 力扣第206题：
* https://leetcode-cn.com/problems/reverse-linked-list/
* 在不使用其它数据结构的情况下
* 反转一个单向链表
*/
public class ReverseLinkedList {
public static void main(String[] args) {
//创建测试数据
LinkedListForAlgorithm<Integer> linkedList = new LinkedListForAlgorithm<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
linkedList.add(5);
System.out.println("反转前的数据为："+linkedList);
Node<Integer> first = linkedList.getFirst();
// reverse1(first);
reverse2(first);
/*
* 进行反转后因为链表内部的头指针和为指针还是原来的值
* 所以需要进行设置正确
*/
linkedList.setFirst(linkedList.getLast());
linkedList.setLast(linkedList.getFirst());
System.out.println("反转后的数据为："+linkedList);
}
/**
* 使用迭代的方式反转
* 时间复杂度是：O(n)
* 空间复杂度是：O(1)
* @param first 链表中的头元素
* @return 反转之后的头元素
*/
private static <E> Node<E> reverse2(Node<E> first) {
Node<E> newNode = null;
while (first != null) {
//先保存头节点的下一个，方便后续将头节点进行后移
Node<E> next = first.next;
//将头节点的下一个设置为新节点
first.next = newNode;
//修改新节点的指向老的节点
newNode = first;
//将头节点往后移
first = next;
}
//返回反转之后的头节点
return newNode;
}
/**
* 使用递归的方式反转
* 思路：假设除了头元素的后面所有元素都是已经反转好的，
* 那么现在只需要将头元素的下一个即（已经反转好的那一部分的尾部）
* 的下一个指向头元素后再将头元素的下一个指向null即可。
*
* 时间复杂度是：O(n)
* 空间复杂度因为使用了递归，而递归使用了隐式地栈，
* 所以就是O(n)
* @param first 链表中的头元素
* @return 反转之后的头元素
*/
private static <E> Node<E> reverse1(Node<E> first) {
//最外层的方法是处理的第1个元素
if(first == null || first.next == null){
return first;
}
//处理第2个元素以及其后的元素
Node<E> reversedNode = reverse1(first.next);
first.next.next = first;
first.next = null;
return reversedNode;
}
}
/**
* 力扣第141题：
* https://leetcode-cn.com/problems/linked-list-cycle/
*
* 判断一个链表中是否有环
*/
public class LeetCodeTest02 {
public static void main(String[] args) {
//准备数据
Node<Integer> first = new Node<>(3);
Node<Integer> node1 = new Node<>(2);
Node<Integer> node2 = new Node<>(0);
Node<Integer> node3 = new Node<>(-4);
first.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node1;
// node3.next = null;
System.out.println("是否有环？"+hasCycle1(first));
// System.out.println("是否有环？"+hasCycle2(first));
}
/**
* 使用暴力方式
* 时间复杂度为：O(n)
* 因为使用了额外的数组空间所以
* 空间复杂度为：O(n)
* @param first 链表中的头元素
* @return 是否有环
*/
public static <E> boolean hasCycle1(Node<E> first) {
//校验入参防止空指针
if(first == null || first.next == null){
return false;
}
//创建一个Set去存放已经遍历过的节点
Set<Node<E>> resultSet = new HashSet<>();
//遍历链表的每一个元素
while(first.next !=null){
//如果Set中不存在就将其添加进Set中后跳过本次循环
if(resultSet.contains(first)){
//如果Set中存在就直接返回true表示有环
return true;
}
resultSet.add(first);
//然后first的指针往后移
first = first.next;
}
//如果到了这里说明遍历完毕没有环就返回false
return false;
}
/**
* 使用快慢指针方式
* 原理：如果有环，那么快指针和慢指针都最终会进入
* 环中，那么总有一天快指针会套圈慢指针
* 时间复杂度为：O(n)
* 空间复杂度为：O(1)
* @param first 链表中的头元素
* @return 是否有环
*/
public static <E> boolean hasCycle2(Node<E> first) {
//校验入参防止空指针
if(first == null || first.next == null){
return false;
}
Node<E> slow = first;
Node<E> fast = first;
/*
* 开始遍历，快指针每次走两步，慢指针每次走一步
* 如果快指针不为null且快指针的下一个不为null
* 说明快指针还没有到达终点就继续循环
*/
while(fast != null && fast.next != null){
//慢指针走一步
slow = slow.next;
//快指针走两步
fast = fast.next.next;
//如果快指针和慢指针相等说明快指针已经套圈慢指针所以返回true
if(slow == fast){
return true;
}
}
//如果到了这里说明遍历完毕快指针已经到达终点所以没有环就返回false
return false;
}
}
/**
* 力扣第24题：
* https://leetcode-cn.com/problems/swap-nodes-in-pairs/
* 两两交换链表中的节点
*/
public class LeetCodeTest01 {
public static void main(String[] args) {
//创建测试数据
LinkedListForAlgorithm<Integer> linkedList = new LinkedListForAlgorithm<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
// linkedList.add(5);
System.out.println("处理前的数据为："+linkedList);
Node<Integer> first = linkedList.getFirst();
// Node<Integer> resultFirst = swapPairs1(first);
Node<Integer> resultFirst = swapPairs2(first);
/*
* 进行反转后因为链表内部的头指针和尾指针还是原来的值
* 所以需要进行设置正确，否则会导致toString方法混乱
*/
linkedList.setFirst(resultFirst);
System.out.println("处理后的数据为："+linkedList);
}
/**
* 递归的方式实现
*
* 时间复杂度为：O(n)
* 由于使用了递归存在隐式的栈空间，所以
* 空间复杂度为：O(n)
* @param first 链表中的头元素
* @return 处理之后的头节点
*/
private static <E> Node<E> swapPairs1(Node<E> first) {
/*
* 递归的终止条件：
* 如果链表长度为奇数则是first.next == null
* 例如：链表为：1-->2-->3，first = 1 时
* 如果链表长度为偶数则是first == null
* 例如：链表为：3-->4，first = 3 时
*/
if(first == null || first.next == null) {
return first;
}
/*
* 假设链表是 1->2->3->4
* 那么就先保存节点2
*/
Node<E> tmp = first.next;
/*
* 开始递归，处理节点3->4
* 当递归结束返回后，就变成了4->3
* 此时first的下一个就指向了4，变成1->4->3
*/
first.next = swapPairs1(tmp.next);
//再将2节点指向节点1即可
tmp.next = first;
return tmp;
}
/**
* 迭代的方式实现
*
* 时间复杂度为：O(n)
* 空间复杂度为：O(1)
* @param first 链表中的头元素
* @return 处理之后的头节点
*/
private static <E> Node<E> swapPairs2(Node<E> first) {
//创建一个空节点去指向原有链表的头节点
Node<E> firstPre = new Node<>();
firstPre.next = first;
//用一个变量去存需要替换的元素
Node<E> tmp = firstPre;
//开始循环去两两交换指针
while(tmp.next != null && tmp.next.next != null){
//pre指向要交换的两个节点的前者
Node<E> pre = tmp.next;
//next指向要交换的两个节点的后者
Node<E> next = tmp.next.next;
//进行两两交换指向
/*
* 将上一次循环保存的交换后的后者的下一个
* 指向其下一个的下一个，即：本次交换后的前者。
*/
tmp.next = next;
//将前者的下一个指向后者的下一个
pre.next = next.next;
//将后者的下一个指向前者
next.next = pre;
//再保存原始的前者
tmp = pre;
}
//返回空节点指向的节点即：新的头节点
return firstPre.next;
}
}
/**
* 力扣第20题：
* https://leetcode-cn.com/problems/valid-parentheses/
* 有效的括号
*/
public class LeeCodeTest01 {
public static void main(String[] args) {
//准备数据
// String str = "[](){}";
// String str = "[(]){}";
// String str = "[(){}]";
// String str = "()))";
String str = "()";
System.out.println(str+"是一个合法的字符串么？"+isValid1(str));
System.out.println(str+"是一个合法的字符串么？"+isValid2(str));
}
/**
* 暴力方式：
* 用其中合法的括号去每次替换成空字符串，最后的得到的结果
* 的长度如果为0，说明是合法的，否则不合法
*
* 因为每次replace方法参数为大于1的字符串那么就是一个O(n)的操作，
* 在加上外层的循环那么就是嵌套的一个循环的情况，所以
* 时间复杂度为：O(n^2)
* 空间复杂度为：O(1)
* @param str 带有括号的字符串
* @return 是否合法
*/
public static boolean isValid1(String str){
//校验入参
if(str == null || str.length() == 0){
return false;
}
//如果长度不为偶数那么也不可能是合法的
if((str.length() & 1) != 0){
return false;
}
//首先保存一下要处理的字符串
String tmp = str;
//对其进行循环处理
while(str.length() != 0){
//每次循环对每一种合法括号进行替换
str = str.replace("()", "");//(){[}]
str = str.replace("[]", "");
str = str.replace("{}", "");
//替换完后，判断如果和原有的字符串相同则说明不合法直接返回false
if(str.equals(tmp)){
return false;
}
//否则说明有可能合法将要处理的字符串重新赋值后继续下一次循环
tmp = str;
}
//如果循环结束那么就是处理后的字符串为空字符串，就说明其是合法的返回true
return true;
}
/*
* 声明一个装有所有合法括号的对应关系的Map
*/
private static final Map<Character, Character> BRACKETS_MAP = new HashMap<>();
static {
BRACKETS_MAP.put('(', ')');
BRACKETS_MAP.put('[', ']');
BRACKETS_MAP.put('{', '}');
}
/**
* 使用栈方式：
*
*
* 时间复杂度为：O(n)
* 空间复杂度为：O(n)
* @param str 带有括号的字符串
* @return 是否合法
*/
public static boolean isValid2(String str){
//校验入参
if(str == null || str.length() == 0){
return false;
}
//如果长度不为偶数那么也不可能是合法的
if((str.length() & 1) != 0){
return false;
}
//如果map中不包含第一个字符，说明没有括号存在，直接返回false
if(!BRACKETS_MAP.containsKey(str.charAt(0))){
return false;
}
//创建一个栈用于辅助寻找
Stack<Character> stack = new Stack<>();
//遍历字符串的字符数组 [(])
for (Character ch : str.toCharArray()) {
//如果为左括号，那么就执行入栈
if(BRACKETS_MAP.containsKey(ch)){
stack.push(ch);
continue;
}
//如果为右括号，且此时栈大小为0，说明也不满足直接返回false
if(stack.isEmpty()){
return false;
}
//如果为右括号，且此时栈大小不为0，那么就弹栈并比较如果不同直接返回false
if(ch != BRACKETS_MAP.get(stack.pop())){
return false;
}
//如果相同那么继续下一次循环
}
//如果最后栈大小依然为0，那么表示是合法的
return stack.size() == 0;
}
}