重庆微信网站开发公司,天津品牌网站建设公司哪家好,网站开发流程人物,金蝶在线登录入口题1 链表的中间结点
描述 给定一个带有头结点 head 的非空单链表#xff0c;返回链表的中间结点。 如果有两个中间结点#xff0c;则返回第二个中间结点。 示例 1#xff1a; 输入#xff1a;[1,2,3,4,5] 输出#xff1a;此列表中的结点 3 (序列化形式#xff1a;[3,4,5…题1 链表的中间结点
描述 给定一个带有头结点 head 的非空单链表返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 示例 1 输入[1,2,3,4,5] 输出此列表中的结点 3 (序列化形式[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意我们返回了一个 ListNode 类型的对象 ans这样 ans.val 3, ans.next.val 4, ans.next.next.val 5, 以及 ans.next.next.next NULL. 示例 2 输入[1,2,3,4,5,6] 输出此列表中的结点 4 (序列化形式[4,5,6]) 由于该列表有两个中间结点值分别为 3 和 4我们返回第二个结点。 提示 给定链表的结点数介于 1 和 100 之间。 题解1 双指针法
思路用两个指针p是慢指针q是快指针移动速度是p的两倍当q到达末尾的时候p指针正好指在链表中间。
class Solution {public ListNode middleNode(ListNode head) {ListNode q head;ListNode p head;while(q ! null q.next ! null){q q.next.next;p p.next;}return ;}
}题解2 单指针法
思路首先遍历链表得到链表长度然后遍历至链表长度二分之一处
class Solution {public ListNode middleNode(ListNode head) {int n 0;ListNode cur head;while (cur ! null) {n;cur cur.next;}int k 0;cur head;while (k n / 2) {k;cur cur.next;}return cur;}
}题解3 数组法
思路链表的缺点在于不能通过下标访问对应的元素。因此我们可以考虑对链表进行遍历同时将遍历到的元素依次放入数组 A 中。如果我们遍历到了 N 个元素那么链表以及数组的长度也为 N对应的中间节点即为 A[N/2]。
class Solution {public ListNode middleNode(ListNode head) {ListNode[] A new ListNode[100];int t 0;while (head ! null) {A[t] head;head head.next;}return A[t / 2];}
}题2 环形链表
描述 给定一个链表判断链表中是否有环。 为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。 示例 1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。 示例 2 输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。 示例 3 输入head [1], pos -1 输出false 解释链表中没有环。 题解1 快慢指针法
思路如果存在环快慢指针总会相遇。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode i head;ListNode j head;while(i ! null i.next ! null){i i.next.next;j j.next;if(i j){return true;}}return false;}
}题解2 哈希表法
思路通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。我们遍历所有结点并在哈希表中存储每个结点的引用或内存地址。如果当前结点为空结点 null即已检测到链表尾部的下一个结点那么我们已经遍历完整个链表并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中那么返回 true即该链表为环形链表。
public boolean hasCycle(ListNode head) {SetListNode nodesSeen new HashSet();while (head ! null) {if (nodesSeen.contains(head)) {return true;} else {nodesSeen.add(head);}head head.next;}return false;
}题3 实现strStr()
描述
题解1
思路如果子串为空返回0。如果子串长于原字符串剩余字符串则找不到返回-1。如果原字符串当前位置和子串首字母匹配则对照字符串依次匹配字符如果子串全匹配返回i否则退出子串的循环原字符串当前位置向后移动。
class Solution {public int strStr(String haystack, String needle) {if(needle.length() 0){return 0;}for(int i 0; i haystack.length(); i){if ((haystack.length() - i) needle.length()) {return -1;}if(haystack.charAt(i) needle.charAt(0)){boolean flag true;for(int j 0; j needle.length(); j){if(haystack.charAt(ij) ! needle.charAt(j)){flag false;}}if(flag){return i;}}}return -1;}
}题解2 滑动窗口subString
class Solution {public int strStr(String haystack, String needle) {int L needle.length(), n haystack.length();for (int start 0; start n - L 1; start) {if (haystack.substring(start, start L).equals(needle)) {return start;}}return -1;}
}题解3 双指针法
思路pn指向原字符串pL指向子串当在原字符串中找到匹配子串第一个字母时比较两字符串记录相同的字符数遇到不同的字符即退出比较循环如果相同字符数等于子串字符数返回pn减去子串长度原串和子串在一起移动。如果相同字符数不等于子串字符数说明匹配失败原字符串要回溯到比较循环之前的位置即pn-子串长度1位置。
class Solution {public int strStr(String haystack, String needle) {int L needle.length(), n haystack.length();if (L 0) return 0;int pn 0;while (pn n - L 1) {// find the position of the first needle character// in the haystack stringwhile (pn n - L 1 haystack.charAt(pn) ! needle.charAt(0)) pn;// compute the max match stringint currLen 0, pL 0;while (pL L pn n haystack.charAt(pn) needle.charAt(pL)) {pn;pL;currLen;}// if the whole needle string is found,// return its start positionif (currLen L) return pn - L;// otherwise, backtrackpn pn - currLen 1;}return -1;}
}
