最长连续序列(并查集、数组)
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n)_ _的算法解决此问题。
示例 1： 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
解答：
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
复原 IP 地址(字符串、回溯)
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 **有效 IP 地址 **。你可以按任何顺序返回答案。 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
- 0 <= s.length <= 3000
- s 仅由数字组成
解答：
class Solution {
private List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if (s.length() < 4)
return res;
backtrack(s, 0, new StringBuilder(), 0);
return res;
}
private void backtrack(String s, int start, StringBuilder sb, int pointNumOfSb) {
if (pointNumOfSb > 4)
return;
if (start == s.length() && pointNumOfSb == 4) {
res.add(sb.toString().substring(1));
return;
}
for (int i = start; i < s.length() && i - start < 3; i++) {
String x = s.substring(start, i + 1);
if (x.charAt(0) == '0' && x.length() > 1)
return;
if (Integer.parseInt(x) <= 255) {
sb.append("." + x);
backtrack(s, i + 1, sb, pointNumOfSb + 1);
sb.delete(sb.lastIndexOf("."), sb.length());
}
}
}
}
删除链表的倒数第 N 个结点(链表、双指针)
给你一个链表，删除链表的倒数第 n_ _个结点，并且返回链表的头结点。 **进阶：**你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
解答：
public class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode v = new ListNode(0, head);
ListNode handle = v;
List<ListNode> index = new ArrayList<>();
while (v != null) {
index.add(v);
v = v.next;
}
int pre = index.size() - n - 1;
int next = index.size() - n + 1;
index.get(pre).next = next >= 0 && next < index.size() ? index.get(next) : null;
return handle.next;
}
}
本文内容到此结束了， 如有收获欢迎点赞
标签：ListNode,示例,int,IP,查集,next,链表,num From： https://blog.51cto.com/zhanjq/6167926