two pointer

31. Next Permutation Medium

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

分析：

case1:
1,3,2,5,4

从右向左找到第一个顺序对，i点
1,3,2,5,4
    - -
    i
    
从i+1点向右找到大于nums[i]的最小值的位置
1,3,2,5,4
    -   -
    i   j

交换i，j的位置
1,3,4,5,2
    -   -
    i   j

对i之后的元素进行排序
1,3,4,2,5

case2:
4,3,2,1
没有找到逆序对，说明是permutation的最后一个，那么下一个就是permutation第一个

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length==1) return ;
        //从右向左找第一个顺序对
        int i = nums.length-2;
        while(i>=0){
            if(nums[i+1]>nums[i]) break;
            i--;
        }
        //从当前i向右找到大于它的最小元素
        int j=i+1;
        if(i>=0){
            for(int k = i+1;k){
                if(nums[i]k;
            }
        }
        //交换位置
        if(i>=0) swap(nums,i,j);
        //对于后续进行排序
        Arrays.sort(nums,i+1,nums.length);
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

 15. 3Sum

Medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

class Solution {
    public List> threeSum(int[] nums) {
        Arrays.sort(nums);
        List> result = new ArrayList();
        for(int i=0;i){
            if(i>0 && nums[i]==nums[i-1]) continue;
            int left = i+1,right = nums.length-1;
            while(left<right){
                if(nums[left]+nums[right]+nums[i]>0) right--;
                else if(nums[left]+nums[right]+nums[i]<0) left++;
                else {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;right--;
                }
                while(left>i+1 && left;
            }
        }
        return result;
    }
}

408. Valid Word Abbreviation Easy

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

• "s10n" ("s ubstitutio n")
• "sub4u4" ("sub stit u tion")
• "12" ("substitution")
• "su3i1u2on" ("su bst i t u ti on")
• "substitution" (no substrings replaced)

The following are not valid abbreviations:

• "s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
• "s010n" (has leading zeros)
• "s0ubstitution" (replaces an empty substring)

Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.

 Example 1:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true
Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i nternational iz atio n").

Example 2:

Input: word = "apple", abbr = "a2e"
Output: false
Explanation: The word "apple" cannot be abbreviated as "a2e".

Constraints:

• 1 <= word.length <= 20
• word consists of only lowercase English letters.
• 1 <= abbr.length <= 10
• abbr consists of lowercase English letters and digits.
• All the integers in abbr will fit in a 32-bit integer.

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i=0,j=0;
        while(jword.length()){
            if(word.charAt(i)==abbr.charAt(j)) {
                i++;j++;
            }
            else{
                if(!Character.isDigit(abbr.charAt(j)) || abbr.charAt(j)=='0') return false;//坑点，注意数字不能以0开头！
                int len = 0;
                while(j Character.isDigit(abbr.charAt(j))){
                    len=len*10+(abbr.charAt(j)-'0');
                    j++;
                }
                i = i+len;
            }
        }
        return i==word.length() && j==abbr.length();
    }
}

243. Shortest Word Distance Easy

Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

 Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Constraints:

• 1 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2

class Solution {
    public int shortestDistance(String[] wordsDict, String word1, String word2) {
        int left =-1,right = -1,result=wordsDict.length;
        for(int i=0;i){
            if(word1.equals(wordsDict[i])){
                left = i;
            }
            else if(word2.equals(wordsDict[i])){
                right = i;
            }
            if(left>=0 && right>=0) result = Math.min(Math.abs(right-left), result);
        }
        return result;
    }
}

244. Shortest Word Distance II Medium

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

• WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
• int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

 Constraints:

• 1 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2
• At most 5000 calls will be made to shortest.

class WordDistance {
    HashMap> map = new HashMap();

    public WordDistance(String[] wordsDict) {
        for(int i=0;i){
            List list = map.getOrDefault(wordsDict[i],new ArrayList());
            list.add(i);
            map.put(wordsDict[i],list);
        }
    }
    
    public int shortest(String word1, String word2) {
        int result = Integer.MAX_VALUE;
        List list1 = map.get(word1);
        List list2 = map.get(word2);
        int pos1 = 0;
        int pos2 = 0;
        while(pos1list2.size()){
            result = Math.min(Math.abs(list1.get(pos1)-list2.get(pos2)),result);
            if(list1.get(pos1)>list2.get(pos2)) pos2++;
            else pos1++;
        }
        return result;
    }
}

245. Shortest Word Distance III Medium

Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

 Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3

 Constraints:

• 1 <= wordsDict.length <= 105
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.

class Solution {
    public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
        int left =Integer.MAX_VALUE,right = -left,result=wordsDict.length;
        for(int i=0;i){
            if(word1.equals(wordsDict[i])){
                if(word1.equals(word2)){
                    right = left;
                }
                left = i;
            }
            else if(word2.equals(wordsDict[i])){
                right = i;
            }
            if(left>=0 && right>=0) result = Math.min(Math.abs(right-left), result);
        }
        return result;
    }
}

11. Container With Most Water Medium

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

class Solution {
    public int maxArea(int[] height) {
        int left = 0,right  = height.length-1;
        int result = 0;
        while(left<right){
            result = Math.max(result, (right-left) * Math.min(height[left],height[right]));
            if(height[left];
            else right--;
        }
        return result;
    }
}

443. String Compression Medium

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group's length is 1, append the character to s.
• Otherwise, append the character followed by the group's length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

 Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

 Constraints:

• 1 <= chars.length <= 2000
• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

class Solution {
    public int compress(char[] chars) {
        int i=0,j=0;
        StringBuffer sb = new StringBuffer("");
        for(i=0;i){
            if(chars[i]!=chars[j]){
                sb.append(chars[j]);
                if(i-j>1) sb.append(i-j);
                j=i;
            }
        }
        sb.append(chars[j]);
        if(i-j>1) sb.append(i-j);
        for(int k=0;k){
            chars[k]=sb.charAt(k);
        }
        return sb.length();
    }
}