1. 移除链表元素
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。
示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
示例 2:
输入:head = [], val = 1
输出:[]
示例 3:
输入:head = [7,7,7,7], val = 7
输出:[]
提示:
列表中的节点数目在范围 [0, 10^4] 内
1 <= Node.val <= 50
0 <= val <= 50
出处:
https://edu.csdn.net/practice/28091689
代码:
import java.util.*; class Solution { public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public static ListNode removeElements(ListNode head, int val) { ListNode top = new ListNode(0); top.next = head; ListNode pre = top; ListNode temp = head; while (temp != null) { if (temp.val == val) pre.next = temp.next; else pre = temp; temp = temp.next; } return top.next; } public static ListNode createLinkedList(int[] nums) { if (nums == null || nums.length == 0) { return null; } ListNode head = new ListNode(nums[0]); ListNode cur = head; for (int i = 1; i < nums.length; i++) { cur.next = new ListNode(nums[i]); cur = cur.next; } return head; } public static void printLinkedList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.val + "->"); cur = cur.next; } System.out.println("null"); } public static void main(String[] args) { int[] nums = {1,2,6,3,4,5,6}; ListNode head = createLinkedList(nums); printLinkedList(head); head = removeElements(head, 6); printLinkedList(head); int[] nums2 = {}; head = createLinkedList(nums2); printLinkedList(head); head = removeElements(head, 1); printLinkedList(head); int[] nums3 = {7,7,7,7}; head = createLinkedList(nums3); printLinkedList(head); head = removeElements(head, 7); printLinkedList(head); } }
输出:
1->2->6->3->4->5->6->null
1->2->3->4->5->null
null
null
7->7->7->7->null
null
2. 跳跃游戏 II
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
出处:
https://edu.csdn.net/practice/28091690
代码:
import java.util.*; class jump { public static int jump(int[] nums) { int end = 0; int steps = 0; int maxPosition = 0; for (int i = 0; i < nums.length - 1; i++) { maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) { end = maxPosition; steps++; } } return steps; } public static void main(String[] args) { int[] nums = {2,3,1,1,4}; System.out.println(jump(nums)); } }
输出:
2
3. 复原 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" 和 "192.168@1.1" 是 无效 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 仅由数字组成
出处:
https://edu.csdn.net/practice/28091691
代码:
import java.util.*; class restoreIpAddresses { private static List<String> res = new ArrayList<>(); public static List<String> restoreIpAddresses(String s) { if (s.length() < 4) return res; backtrack(s, 0, new StringBuilder(), 0); return res; } private static 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()); } } } public static void main(String[] args) { String s = "25525511135"; System.out.println(restoreIpAddresses(s)); s = "0000"; res.clear(); System.out.println(restoreIpAddresses(s)); s = "1111"; res.clear(); System.out.println(restoreIpAddresses(s)); s = "010010"; res.clear(); System.out.println(restoreIpAddresses(s)); s = "101023"; res.clear(); System.out.println(restoreIpAddresses(s)); } }
输出:
[255.255.11.135, 255.255.111.35]
[0.0.0.0]
[1.1.1.1]
[0.10.0.10, 0.100.1.0]
[1.0.10.23, 1.0.102.3, 10.1.0.23, 10.10.2.3, 101.0.2.3]