最小覆盖子串(哈希表、字符串)
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 **注意:**如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
示例 2:
输入:s = "a", t = "a"
输出:"a"
提示:
- 1 <= s.length, t.length <= 105
- s 和 t 由英文字母组成
**进阶:**你能设计一个在 o(n) 时间内解决此问题的算法吗? 以下程序实现了这一功能,请你填补空白处内容:
public class Min_Win_Sub {
public String minWindow(String s, String t) {
int[] ta = new int[128];
int[] sa = new int[128];
int min = Integer.MAX_VALUE;
String minwin = "";
for (int i = 0; i < t.length(); i++) {
ta[t.charAt(i)]++;
}
int count = 0;
int end = 0;
int start = 0;
while (end < s.length()) {
if (ta[s.charAt(end)] != 0) {
if (sa[s.charAt(end)] < ta[s.charAt(end)]) {
count++;
}
sa[s.charAt(end)]++;
}
if (count == t.length()) {
_________________;
if (end - start + 1 < min) {
minwin = s.substring(start, end + 1);
min = end - start + 1;
}
}
end++;
}
return minwin;
}
}
解答:
while (ta[s.charAt(start)] == 0 || sa[s.charAt(start)] > ta[s.charAt(start)]) {
if (sa[s.charAt(start)] > ta[s.charAt(start)]) {
sa[s.charAt(start)]--;
}
start++;
}
两数之和(数组、哈希表)
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]
提示:
- 2 <= nums.length <= 103
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
解答:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> cache = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int distance = target - nums[i];
if (cache.containsKey(distance)) {
return new int[] { cache.get(distance), i };
} else {
cache.put(nums[i], i);
}
}
return new int[] {};
}
}
二叉树的层序遍历 II(树、广度优先搜索)
给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层序遍历为: [ [15,7], [9,20], [3] ]
解答:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list1 = new ArrayList<>();
if (root == null)
return list1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> list2 = new ArrayList<>();
int count = queue.size();
for (int i = 0; i < count; i++) {
TreeNode node = queue.poll();
list2.add(node.val);
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
list1.add(0, list2);
}
return list1;
}
}
本文内容到此结束了, 如有收获欢迎点赞
标签:end,charAt,nums,int,start,二叉树,哈希,new,两数 From: https://blog.51cto.com/zhanjq/6167928