种一棵树最好的时间是十年前，或者现在
2023.3.14
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
1 2 3 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
思路1:通过双循环暴力计算两个数的和； class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
思路二：使用哈希表建立索引
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int [] twoSum(int [] nums, int target) { Map<Integer,Integer> map = new HashMap <>(); for (int i=0 ;i<nums.length;i++) { map(数组值，脚标); if (map.get(target - nums[i]) != null ) { return new int []{map.get(target-nums[i]),i}; } map.put(nums[i],i); } return new int []{0 ,0 }; } }
两个相同字符之间的最长子字符串
给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ， 计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。
子字符串 是字符串中的一个连续字符序列。
示例 1：
1 2 3 输入：s = "aa" 输出：0 解释：最优的子字符串是两个 'a' 之间的空子字符串。
思路：通过哈希表记录最开始出现的位置，然后比较后面的出现时距离
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int maxLengthBetweenEqualCharacters (String s) { HashMap<Character, Integer> map = new HashMap <>(s.length() >> 1 ); int max=-1 ; for (int i=0 ;i<s.length();i++) { char c = s.charAt(i); if (map.get(c)==null ) { map.put(c,i); continue ; } max = Math.max(max,i-map.get(c)-1 ); } return max; } }
2023.3.20
合并两个有序链表:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
1 2 输入：l1 = [1 ,2 ,4 ], l2 = [1 ,3 ,4 ] 输出：[1 ,1 ,2 ,3 ,4 ,4 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public ListNode mergeTwoLists (ListNode l1, ListNode l2) { if (l1==null ) return l2; else if (l2 == null ) return l1; if (l1.val<l2.val) { l1.next = mergeTwoLists(l1.next,l2); return l1; } else { l2.next = mergeTwoLists(l2.next,l1); return l2; } } }
删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表
1 2 输入：head = [1,1,2,3,3] 输出：[1,2,3]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public ListNode deleteDuplicates (ListNode head) { ListNode cur = head; while (cur != null && cur.next != null ) { if (cur.val == cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; } }
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
1 2 3 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public class Solution { public boolean hasCycle (ListNode head) { if ( head == null ||head.next == null ) { return false ; } ListNode fast = head.next; ListNode slow = head; while (fast!=slow) { if (fast==null || fast.next==null ) { return false ; } fast = fast.next.next; slow = slow.next; } return true ; } }
只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
1 2 3 4 5 6 7 8 9 10 11 class Solution { public int singleNumber (int [] nums) { Set<Integer> Net = new HashSet <>(); for (int num : nums) { if (!Net.add(num)) Net.remove(num); } return Net.isEmpty()?-1 :Net.iterator().next(); } }
1 2 3 4 5 6 7 8 9 10 class Solution { public int singleNumber (int [] nums) { int reduce = 0 ; for (int num : nums) { reduce = reduce ^ num; } return reduce; } }
2023.3.25
无重复字符的最长子串
定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
1 2 3 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int lengthOfLongestSubstring (String s) { int n = s.length(), ans = 0 ; Map<Character, Integer> map = new HashMap <>(); for (int end = 0 , start = 0 ; end < n; end++) { char alpha = s.charAt(end); if (map.containsKey(alpha)) { start = Math.max(map.get(alpha), start); } ans = Math.max(ans, end - start + 1 ); map.put(alpha, end + 1 ); } return ans; } }