1.[Minimum Window Substring]https://leetcode.com/problems/minimum-window-substring/description/
solution:同样是利用HashMap来存Dict，key保存word，value保存word出现的次数(要查找的串)。然后来遍历整个母串。因为这里是要求最短的包含子串的字符串，所以中间是可以允许有非子串字符的，当遇见非子串字符而count又没到子串长度时，可以继续走。当count达到子串长度，说明之前遍历的这些有符合条件的串，用一个pre指针帮忙找，pre指针帮忙找第一个在HashMap中存过的，并且找到后给计数加1后的总计数是大于0的，判断是否为全局最小长度，如果是，更新返回字符串res，更新最小长度，如果不是，继续找。
class Solution {
public String minWindow(String S, String T) {
if(S == null || S.length() == 0)
return "";
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0; i<T.length();i++)
{
if(map.containsKey(T.charAt(i)))
{
map.put(T.charAt(i),map.get(T.charAt(i))+1);
}
else
{
map.put(T.charAt(i),1);
}
}
int left = 0;
int count = 0;
int minLen = S.length()+1;
int minStart = 0;
for(int right=0; right<S.length();right++)
{
if(map.containsKey(S.charAt(right)))
{
map.put(S.charAt(right),map.get(S.charAt(right))-1);
if(map.get(S.charAt(right))>=0)
{
count++;
}
while(count == T.length())
{
if(right-left+1<minLen)
{
minLen = right-left+1;
minStart = left;
}
if(map.containsKey(S.charAt(left)))
{
map.put(S.charAt(left), map.get(S.charAt(left))+1);
if(map.get(S.charAt(left))>0)
{
count--;
}
}
left++;
}
}
}
if(minLen>S.length())
{
return "";
}
return S.substring(minStart,minStart+minLen);
}
}
solution 2:双指针
2.第一个只出现一次的字符
solution：需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把每一个字符映射成一个数字。可以采用哈希表。第一次扫描时，在哈希表中出现更新一个字符出现的次数是O(n)，如果字符串长度是n，那么第一次扫描的时间复杂度是O(n)。第二次扫描时，同样O(1)能读出一个字符出现的次数。
public Character firstNotRepeating(String str){
if(str == null)
return null;
char[] strChar = str.toCharArray();
LinkedHashMap<Character,Integer> hash = new LinkedHashMap<Character,Integer>();
for(char item:strChar){
if(hash.containsKey(item))
hash.put(item, hash.get(item)+1);
else
hash.put(item, 1);
}
for(char key:hash.keySet())
{
if(hash.get(key)== 1)
return key;
}
return null;
}
LeetCode版解法
[First Unique Character in a String]https://leetcode.com/problems/first-unique-character-in-a-string/description/
public int firstUniqChar(String s) {
Map<Character, Integer> map = new LinkedHashMap<>();
Set<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if (set.contains(s.charAt(i))) {
if (map.get(s.charAt(i)) != null) {
map.remove(s.charAt(i));
}
} else {
map.put(s.charAt(i), i);
set.add(s.charAt(i));
}
}
return map.size() == 0 ? -1 : map.entrySet().iterator().next().getValue();
}
3.字符串的排列
solution：求整个字符串的排列，可以看成两步，首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步固定第一个字符，求后面所有字符的排列。这个时候仍然把后面的字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<Integer>();
int len = nums.length;
if (len == 0||nums == null) return res;
// 采用前后元素交换的办法，dfs解题
exchange(nums, 0, len);
return result;
}
public void exchange(int[] nums, int i, int len) {
// 将当前数组加到结果集中
if(i == len-1) {
List<Integer> list = new ArrayList<>();
for (int j=0; j<len; j++){
list.add(nums[j]);
}
res.add(list);
return ;
}
// 将当前位置的数跟后面的数交换，并搜索解
for (int j=i; j<len; j++) {
swap(nums, i, j);
exchange(nums, i+1, len);
swap(nums, i, j);
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
# 递归方式
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else {
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // element already exists, skip
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
}
