主要记录一些简单的算法和数据结构的题目，一方面是自己在准备的积累一方面适合复习使用。代码不一定最优，但是思考过程基本会给。
第一周，算法给生活加点料。
1.在单链表中删除倒数第K个节点
要求：如果链表长度为N，时间复杂度为O(N)，额外空间为O(1)
想法：首先呢，单链表只能够从头开始遍历。现在要做呢就是如何在遍历了一次后能够准确找到倒数K节点的位置，例如我们可以计算到总体长度在用总体长度减去K的大小来判断。刚好就是总体长度减去K等于要删除的位置。那么就可以来实现代码了
public class Demo01 {
public class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node RemoveLastKNode(Node head, int lastK){
int Number = 0;
//首先判断是否为空且K值有效
if(head == null || lastK < 1){
return head;
}
Node cur = head;
while(cur != null){
cur = cur.next;
Number++;
}
//如果当前节点数与K相同那么就删除头结点
if(Number-lastK == 0){
head = head.next;
}
//如果当前节点数小于K数就返回
else if(Number-lastK < 0){
return head;
}
//如果当前节点数大于K就遍历删除第Number-lastK个节点
else{
cur = head;
for(int i =0; i < Number-lastK; i++){
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
}*2.反转单链表以及双链表 *
要求：如果链表长度为N，时间复杂度为O(N)，额外空间为O(1)
想法：首先想到的使如何交换A和B两个的值，方法就在此。我们呢每次遍历原先链表，然后把其next指针指向新的链表。如同a->b->c->d->null,首先拿出a，再拿出b，并且使得b的next指向a就有了b->a，一次类推就变成了反转链表。但是由于空间的限制，所以我们呢只能实现在当前链表的转移，也就是每次拿出下一个节点用其next指针只想头结点即可。
public class Demo02 {
public class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node reverseList(Node head){
Node pre = null;
Node cur = null;
while(head != null){
//当前节点指向head的next
cur = head.next;
//然后把下一个节点指向当前新链表
head.next = pre;
//pre继承当前链表
pre = head;
//转换后head变为最新的链表
head = cur;
}
return head;
}
}
实际上看就是pre一直在记录新生成的反转列表，cur一直在记录没有转换的列表至于双向链表原理一致
*3.反转部分单链表 *
给定两个整数from和to表示反转的开始位置和结束位置
要求：
- 如果链表长度为N，时间复杂度为O(N)，额外空间为O(1)
- 如果不满足1<= from<=to<=N，则不用调整
想法：首先就是要判断给定的要求。然后再是根据反转的位置专门实现两个位置间的反转操作。反转的操作上一题中给出。是否可以实现把范围内的数据摘取出来，然后单独反转再放回去呢。卧槽？？？忘记额外空间了。看来是不行 = = 那就原样子来吧
public class Demo03 {
public class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node reversePart(Node head,int from,int to){
//用于计算总长度
int len = 0;
Node cur = head;
//用于记录from的前一个节点，以至于后面好搭接
Node pre = null;
//同理记录to的后一个节点
Node pos = null;
while(cur != null){
len++;
//记录两个节点的位置
if(len == from-1)
pre = cur;
if(len == to+1)
pos = cur;
}
//判断第二个条件是否成立
if(from > to || from < 1 || to > len){
return head;
}
//截取反转位置
cur = pre == null ? head:pre.next;
//这一步开始就是上一题的模型
Node cur2 = cur.next;
cur.next = pos;
Node next = null;
while(cur2 != null){
next = cur2.next;
cur2.next = cur;
cur = cur2;
cur2 = next;
}
//拼接
if(pre != null){
pre.next = cur;
return head;
}
return cur;
}
}*4.两个单链表生成相加链表 *
假设每一个节点的值都在0-9之间，那么链表整体就可以代表一个整数，然后实现两个链表的相加。
要求：没啥要求，实现就好了。
想法：我们之前尝试了反转的效果，那么这一题也可也这样做，反转后就是从低位加起来，再一个进位器就够了。最后结果逆序输出就行。或者说呢尝试以下栈这个结构。后进后出嘛。
import java.util.Stack;
public class Demo04 {
public class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node addListNode(Node head1,Node head2){
//创建两个栈，用于操作两个线性表
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
//将他们分别放入栈中
while(head1 != null){
s1.push(head1.value);
head1 = head1.next;
}
while(head2 != null){
s1.push(head2.value);
head2 = head2.next;
}
//用于保存结果的栈
Stack<Integer> ans = new Stack<>();
//ac为进位器
int ac = 0;
int n1,n2,n = 0;
Node node = null;
Node pre = null;
while(!s1.isEmpty() || !s2.isEmpty()){
n1 = s1.isEmpty()? 0 : s1.pop();
n2 = s2.isEmpty()? 0 : s2.pop();
n = n1 + n2 + ac;
pre = node;
node = new Node(n % 10);
node.next = pre;
ac = n /10;
}
//最后判断以下ac是否还有数据
if(ac == 1){
pre = node;
node = new Node(1);
node.next = pre；
}
return node;
}
}*5.删除无序链表中重复出现的值 *
要求：
- 实现一个长度为N时间复杂度为O(N)的程序
- 实现一个空间复杂度为O(1)的程序
想法：时间复杂度为O(N)那么就要用到哈希算法，如果要空间复杂度呢，就是先排序喽，排序时间大致为O(N²)，空间为1.
import java.util.HashSet;
public class Demo05 {
public class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public void remove(Node head){
if(head == null){
return;
}
//创建hashSet
HashSet<Integer> set = new HashSet<>();
Node pre = head;
Node cur = head.next;
//首先加入第一个值，然后开始判断
set.add(head.value);
while(cur != null){
//如果set中有这个值
if(set.contains(cur.value)){
pre.next = cur.next;
}else{
//如果没有就从新加入这个新值
set.add(cur.value);
pre = cur;
}
cur = cur.next;
}
}
}
