购物网站的详细设计ui设计师是什么意思

当前位置： 首页 > news >正文

购物网站的详细设计,ui设计师是什么意思,常州微网站建设文档,中国电信网站备案 密码重置一、什么是链表 1、链表与顺序表对比 不同点LinkedListArrayList物理存储上不连续连续随机访问效率O(N)O(1#xff09;插入、删除效率O(1)O(N) 3、链表的分类 链表根据结构分类#xff0c;可分为单向/双向、无头结点/有头节点、非循环/循环链表#xff0c;这三组每组各取… 一、什么是链表 1、链表与顺序表对比 不同点LinkedListArrayList物理存储上不连续连续随机访问效率O(N)O(1插入、删除效率O(1)O(N) 3、链表的分类 链表根据结构分类可分为单向/双向、无头结点/有头节点、非循环/循环链表这三组每组各取一个就构成一种结构链表。其中单向、不带头、非循环链表是学习的重点双向、不带头、非循环链表在实际开发中常用。 以单向、不带头、非循环链表为例 双向、不带头、非循环链表 单向、带头、非循环链表好处在于不用特别处理头节点比如增删时 单向、不带头、循环链表 二、单向、不带头、非循环链表的实现 1、IList 接口 定义 IList 接口声明线性表需要实现的方法 package listinterface;public interface IList {//头插法void addFirst(int data);//尾插法void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void clear();void display(); }2、结点内部类 结点仅由链表内部使用且每个结点的产生不依赖于某个链表可定义为链表的私有静态内部类 public class MySingleList implements IList {// 结点内部类private static class Node {int data;Node next;public Node(int data) {this.data data;}}// 头结点private Node head;// 链表长度private int size;………… } 3、打印链表 Overridepublic void display() {Node cur head;while (cur ! null) {System.out.print(cur.data );cur cur.next;}System.out.println( size: size);} 4、清空链表、获取链表长度 Overridepublic int size() {return size;}Overridepublic void clear() {head null;size 0;} head 为空没有引用指向 node1自动回收 node1node1 回收没有引用指向 node2自动回收 node2……故 clear 只需 head 设为 null 即可。 5、头插法 Overridepublic void addFirst(int data) {Node newNode new Node(data);newNode.next head;head newNode; // if (head ! null) { // newNode.next head; // } // head newNode;size;} 6、尾插法 Overridepublic void addLast(int data) {Node newNode new Node(data);if (head null) {head newNode;size;return;}Node cur head;while (cur.next ! null) { // 找到尾节点cur cur.next;}cur.next newNode;size;} 7、任意位置插入 受查异常父类方法没抛出异常子类方法不能抛出异常父类抛出了子类不做要求。非受查异常不做要求。为了不改动 IList且让 addIndex 抛出异常以便在 main 处对异常做处理链表下标越界异常选择继承非受查异常 RuntimeExcption。 package myexception;public class ListIndexOutOfBoundsException extends RuntimeException {public ListIndexOutOfBoundsException(String message) {super(message);} } private void checkIndexOutOfBounds(int index) throws ListIndexOutOfBoundsException {if (index 0 || index size) {throw new ListIndexOutOfBoundsException(插入位置不合法。 Index: index , Size: size);}}private Node findIndex(int index) {Node cur head;int cnt 0;while (cnt ! index) {cur cur.next;cnt;}return cur;}Overridepublic void addIndex(int index, int data) throws ListIndexOutOfBoundsException {// 先检查索引是否越界checkIndexOutOfBounds(index);if (index 0) { // 在 0 处插入没有前驱节点addFirst(data);return;}if (index size) { // 在末尾插入addLast(data);return;}Node newNode new Node(data);// 找到插入位置前的节点Node pre findIndex(index - 1);// 插入新节点newNode.next pre.next;pre.next newNode;size;} 8、删除第一次出现关键字为key的节点 private Node findKey(int key) {Node cur head;while (cur.next ! null) {if (cur.next.data key) {return cur;}cur cur.next;}return null;}Overridepublic void remove(int key) {if (head null) { // 空链表return;}if (head.data key) { // 头节点就是要删除的节点head head.next;size–;return;}Node pre findKey(key);if (pre ! null) { // 找到了要删除的节点pre.next pre.next.next;size–;} else { // 要删除的节点不存在System.out.println(要删除的节点不存在。);}} 9、删除所有关键字为 key 的节点 Overridepublic void removeAllKey(int key) {if (head null) { // 空链表return;}Node pre head;Node cur head.next;while (cur ! null) {if(cur.data key) {pre.next cur.next;// cur cur.next;}else {pre cur;// cur cur.next;}cur cur.next;}if (head.data key) {head head.next;size–;}} 三、链表面试题练习 1、反转链表

1. 反转链表 - 力扣LeetCode 思路从头开始边遍历边反转最后尾结点为 head。 class Solution {public ListNode reverseList(ListNode head) {// 特殊处理 空链表、只有一个结点的链表if(head null || head.next null) { // 两者顺序不能反因为 null 没有nextreturn head;}ListNode cur head.next;// 头结点其 next 为 null head.next null;// 边反转边遍历直到反转完尾结点while(cur ! null) {ListNode curN cur.next; cur.next head;head cur;cur curN;}return head;} } 2、链表的中间结点
2. 链表的中间结点 - 力扣LeetCode 思路 1、计算链表长度的一半再走一半长。时间复杂度 O(N) O(N/2)。 2、设置 slow 和 fast 从 head 开始走slow 每次走 1 步fast 每次走 2 步。那么 fast 走完全程fast null 或者 fast.next null必是 slow 的两倍长度故 slow 就是中间节点的位置。时间复杂度 O(N/2) 更优。 class Solution {public ListNode middleNode(ListNode head) { // 根据题目链表非空// 从头节点开始ListNode slow head;ListNode fast head;// fast 走完整个链表while(fast ! null fast.next ! null) {// slow 每次走 1 步fast 每次走 2 步slow slow.next;fast fast.next.next;}// slow 就是中间结点return slow;} } 3、返回倒数第 k 个结点 面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode 思路slow 从 head 开始fast 比 slow 先多走 k-1 步然后 slow、fast 每次只走一步直到 fast 走到尾结点。 class Solution {public int kthToLast(ListNode head, int k) {// 根据题目k 保证有效因此不用判断 k0 和 k len 的情况ListNode slow head;ListNode fast head;// 当 fast 先走 k-1 步int cnt k-1;// k保证有效fast 不会走过头while(cnt ! 0) { fast fast.next;cnt–;}// 让 fast 走到尾结点slow 就是倒数第 k 个结点while(fast.next ! null) {slow slow.next;fast fast.next;}return slow.val;} } 4、合并两个有序列表
3. 合并两个有序链表 - 力扣LeetCode 思路分别同时遍历两个链表更小的插入新链表插入的链表插入后更新为 next直到 l1 或者 l2 遍历完了。没遍历完的那个链表把剩的接在新链表尾。为了不单独处理头指针新链表带头节点。 class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head new ListNode(); // 创建头节点ListNode cur head;ListNode cur1 list1;ListNode cur2 list2;// 其中一个遍历完就退出while(cur1 ! null cur2 ! null) {if(cur1.val cur2.val) {cur.next cur1;// cur cur.next;cur1 cur1.next;}else {cur.next cur2;// cur cur.next;cur2 cur2.next;}cur cur.next;}// 没遍历完的接在后面if(cur1 ! null) {cur.next cur1;}if(cur2 ! null) {cur.next cur2;}return head.next; // 不带头节点} } 5、链表分割 链表分割_牛客题霸_牛客网 思路先创建两个链表依次遍历原链表小于和大于等于 x 的分开尾插入两个链表再合并。 public class Partition {public ListNode partition(ListNode pHead, int x) {// 创建两个头节点ListNode head1 new ListNode(-1); ListNode head2 new ListNode(-1);// 遍历原链表每个结点与 x 比大小分类放在两个新链表中ListNode cur1 head1;ListNode cur2 head2; while(pHead ! null) {if(pHead.val x) {cur1.next pHead;cur1 cur1.next;}else {cur2.next pHead;cur2 cur2.next;}pHead pHead.next;}// 现在 cur1、cur2 分别指向两个链表的尾结点。cur1.next head2.next; // 链表1的尾接上链表2的头cur2.next null; // 链表2的尾接上 null// 如果最后链表1为空cur1就是head1没问题// 如果最后链表2为空cur2就是head2没问题return head1.next;} } 6、链表的回文结构 链表的回文结构_牛客题霸_牛客网 思路 1、求尾结点头、尾同时前进并比较到 head tail奇数长度 或者 head.next tail 偶数长度为止。tail 往前走行不通因为是单链表。 2、把原链表的后一半反转再将反转链表与原链表对比直到反转链表遍历完。时间复杂度O(N/2)O(N/2)O(N/2)O(N)。找到一半处、将一半反转、对比一半。 public class PalindromeList {private ListNode findHalf(ListNode head) {ListNode slow head;ListNode fast head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}return slow;}private ListNode reverse(ListNode head) {if(head null || head.next null) {return head;}ListNode cur head.next;head.next null;while(cur ! null) {ListNode curN cur.next;cur.next head;head cur;cur curN;}return head;}public boolean chkPalindrome(ListNode A) {// 找到中间结点ListNode halfNode findHalf(A);// 将后一半反转ListNode B reverse(halfNode);// 将后半段与前半段对比后半段遍历完退出while(B ! null) {if(A.val ! B.val) {return false;}A A.next;B B.next;}return true;} } 7、相交链表
4. 相交链表 - 力扣LeetCode 思路可能分叉的地方前边或后边。但是对于链表不可能后边分叉因为如果后边分叉了当你遍历一条单链时遍历到后边分叉的地方就不知道继续走哪条路了这样就不是单链表了。因此只有可能如上图的Y型或者在一条直线上。 如果同时各自出发每次走一步直到有一方到达尾结点那么短的链表总是先到达并且它们的最终距离是两链表的长度差。长度差来自分叉的部分而不是相交的部分。那么如果让长的先走长度差步再同时走它们碰面的地方将是相交处。 public class Solution {private int size(ListNode head) {ListNode cur head;int cnt 0;while(cur ! null) {cnt;cur cur.next;}return cnt;}public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 求两条链的长度int size1 size(headA);int size2 size(headB);// 让长的作为 headA求两链表长度差(正)int len size1 - size2;if(size1 size2) {len size2 - size1;ListNode tmp headA;headA headB;headB tmp;}// 让长的先走 len 步while(len ! 0) {headA headA.next;len–;}// 再同时走相等的地方就是相交结点while(headA ! headB) {headA headA.next;headB headB.next;}return headA;} } 8、环形链表
5. 环形链表 - 力扣LeetCode 思路慢指针和快指针同时走如果有环那么快、慢指针总会在环里相遇快指针多跑 k 圈然后追上慢指针如果没环快指针先走完全程结束。我们设慢指针每次走1步快指针每次走2步。 为什么快指针不能是 3、4、……、n 步如果是3步存在以下情况无论走多久都不会相遇 快指针如果走 4 步存在以下情况无论走多久都不会相遇 以此类推…… public class Solution {public boolean hasCycle(ListNode head) {// 设置快、慢指针ListNode slow head;ListNode fast head;// slow 每次走1步fast 每次走2步// 直到 fast null(偶数个) 或者 fast.next null(奇数个) 返回 flase// 或者 slow fast 返回 truewhile(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if(slow fast) {return true;}}return false;} } 9、环形链表Ⅱ
6. 环形链表 II - 力扣LeetCode 思路 若一指针 head1 从相遇点开始一指针 head2 从头指针开始同时走每次走一步。当 head1 走 X 步到达入口同时head2 从相遇点开始走了 (k-1) 圈回到相遇点再走 N 步到入口。即两指针相遇处就是入口结点。 public class Solution {private ListNode getMeetNode(ListNode head) {ListNode slow head;ListNode fast head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if(slow fast) {return slow;}}return null;}public ListNode detectCycle(ListNode head) {// 获得 slow 与 fast 的相遇结点ListNode meetNode getMeetNode(head);// 链表无环返回 nullif(meetNode null) {return null;}// 分别从头指针相遇结点开始走两指针相遇处就是入口while(head ! meetNode) {head head.next;meetNode meetNode.next;}return head;} } 四、双向、不带头、非循环链表的实现 1、Node 内部类和属性 public class MyLinkedList implements IList {private static class Node {int val;Node next; // 后继指针Node prev; // 前驱指针public Node(int val) {this.val val;}}private Node head; // 头指针private Node tail; // 尾指针private int size; // 链表大小………… } 2、清空链表 与单向不同直接 head null双向需要遍历结点并释放 node原因如下head 为空还有 node2 指向 node1所以手动置 node2 的 pre 为空node1释放还有 node3 指向 node2手动置 node3 的 pre 未空…… Overridepublic void clear() {Node cur head;while (cur! null) {Node curN cur.next;cur.prev null;cur.next null;cur curN;}head null;tail null;size 0;} 3、头插法 Overridepublic void addFirst(int data) {Node newNode new Node(data);if (head null) {head newNode;tail newNode;} else {newNode.next head;head.prev newNode;head newNode;}size;} 4、尾插法 Overridepublic void addLast(int data) {Node newNode new Node(data);if (head null) {head newNode;tail newNode;} else {tail.next newNode;newNode.prev tail;tail newNode;}size;} 5、任意位置插入 Overridepublic void addIndex(int index, int data) {// 先检查索引是否越界checkIndexOutOfBounds(index);if (index 0) { // 在 0 处插入没有前驱节点addFirst(data);return;}if (index size) { // 在末尾插入addLast(data);return;}Node newNode new Node(data);// 找到插入位置Node cur findIndex(index);// 插入新节点newNode.next cur;newNode.prev cur.prev;cur.prev.next newNode;cur.prev newNode;size;} 6、删除第一次出现的 key private Node findKey(int key) {Node cur head;while (cur ! null) {if (cur.val key) {return cur;}cur cur.next;}return null;}Overridepublic void remove(int key) {Node deleteNode findKey(key); // 找到待删除节点如果不存在返回 nullif (deleteNode null) { // 包含空链表的情况System.out.println(要删除的节点不存在。);return;}if (deleteNode head) { // 待删除节点是头节点包含了链表只有一个结点的情况head deleteNode.next;if (head null) { // 链表只有一个节点tail null;} else {head.prev null;}} else if (deleteNode tail) { // 待删除节点是尾节点tail deleteNode.prev;tail.next null;} else { // 待删除节点是中间节点deleteNode.prev.next deleteNode.next;deleteNode.next.prev deleteNode.prev;}size–;} 7、删除所有 key Overridepublic void removeAllKey(int key) {Node cur head;while (cur ! null) {if (cur.val key) {if (cur head) { // 待删除节点是头节点head cur.next;if (head null) { // 链表中只有一个节点tail null;}else {head.prev null;}} else if (cur tail) { // 待删除节点是尾节点tail cur.prev;tail.next null;} else { // 待删除节点是中间节点cur.prev.next cur.next;cur.next.prev cur.prev;}size–; // cur cur.next; // 跳过已删除节点继续遍历} /else {cur cur.next;}/cur cur.next;}} 五、LinkedList 的使用 集合类中LinkedList 的底层是双向链表。 1、常用方法的使用 2、迭代器 IteratorE 是集合类通用的迭代器线性表专用的迭代器 ListIteratorE 功能更强可以反向迭代