1.[Minimum Window Substring]https://leetcode.com/problems/minimum-window-substring/description/
solution:同樣是利用HashMap來存Dict，key保存word冰寻，value保存word出現(xiàn)的次數(shù)(要查找的串)辐董。然后來遍歷整個母串胀糜。因?yàn)檫@里是要求最短的包含子串的字符串悬嗓，所以中間是可以允許有非子串字符的，當(dāng)遇見非子串字符而count又沒到子串長度時堰乔，可以繼續(xù)走仓犬。當(dāng)count達(dá)到子串長度，說明之前遍歷的這些有符合條件的串超棺，用一個pre指針幫忙找向族，pre指針幫忙找第一個在HashMap中存過的，并且找到后給計數(shù)加1后的總計數(shù)是大于0的棠绘，判斷是否為全局最小長度炸枣，如果是，更新返回字符串res弄唧，更新最小長度适肠，如果不是，繼續(xù)找候引。
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.第一個只出現(xiàn)一次的字符
solution：需要一個數(shù)據(jù)容器來存放每個字符的出現(xiàn)次數(shù)侯养。在這個數(shù)據(jù)容器中可以根據(jù)字符來查找它出現(xiàn)的次數(shù)，也就是說這個容器的作用是把每一個字符映射成一個數(shù)字澄干」淇可以采用哈希表。第一次掃描時麸俘，在哈希表中出現(xiàn)更新一個字符出現(xiàn)的次數(shù)是O(n)辩稽，如果字符串長度是n，那么第一次掃描的時間復(fù)雜度是O(n)从媚。第二次掃描時逞泄，同樣O(1)能讀出一個字符出現(xiàn)的次數(shù)。
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：求整個字符串的排列拜效，可以看成兩步喷众，首先求所有可能出現(xiàn)在第一個位置的字符，即把第一個字符和后面所有的字符交換紧憾。第二步固定第一個字符到千，求后面所有字符的排列。這個時候仍然把后面的字符分成兩部分：后面字符的第一個字符赴穗，以及這個字符之后的所有字符憔四。然后把第一個字符逐一和它后面的字符交換膀息。
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) {
// 將當(dāng)前數(shù)組加到結(jié)果集中
if(i == len-1) {
List<Integer> list = new ArrayList<>();
for (int j=0; j<len; j++){
list.add(nums[j]);
}
res.add(list);
return ;
}
// 將當(dāng)前位置的數(shù)跟后面的數(shù)交換了赵，并搜索解
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);
}
}
}
}
