# Leet-code

**Repository Path**: msren/leet-code

## Basic Information

- **Project Name**: Leet-code
- **Description**: 力扣日常算法题目的练习，对算法基础的巩固提升。（Leet_code practicing）
加油！！
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2022-06-04
- **Last Updated**: 2025-01-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Leet-code题目分模块总结

# 栈相关

## 1.应用场景
![输入图片说明](https://foruda.gitee.com/images/1660263384397126894/无标题.png "无标题.png")
### (1)逆波兰表达式
方法一： :bowtie: 
```
class Solution {

    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }


    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}
```
方法二： :bowtie: 
>经验 用数组模拟栈，因为栈的底层可以用顺序表（数组）来实现，数组比栈更加灵活。可以通过控制有效长度来模拟栈的入栈和出栈

> 方法一使用栈存储操作数。也可以使用一个数组模拟栈操作。

如果使用数组代替栈，则需要预先定义数组的长度。对于长度为 n的逆波兰表达式，显然栈内元素个数不会超过 n，但是将数组的长度定义为 n 仍然超过了栈内元素个数的上界。那么，栈内元素最多可能有多少个？

对于一个有效的逆波兰表达式，其长度 n一定是奇数，且操作数的个数一定比运算符的个数多 1 个，即包含 n+1/2​ 个操作数和 n-1/2​ 个运算符。考虑遇到操作数和运算符时，栈内元素个数分别会如何变化：

    如果遇到操作数，则将操作数入栈，因此栈内元素增加 1 个；

    如果遇到运算符，则将两个操作数出栈，然后将一个新操作数入栈，因此栈内元素先减少 2个再增加 1 个，结果是栈内元素减少 1 个。

由此可以得到操作数和运算符与栈内元素个数变化的关系：遇到操作数时，栈内元素增加 1个；遇到运算符时，栈内元素减少 1 个。


```
class Solution {
    public int evalRPN(String[] tokens) {
        int n = tokens.length;
        int[] stack = new int[(n + 1) / 2];
        int index = -1;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            switch (token) {
                case "+":
                    index--;
                    stack[index] += stack[index + 1];
                    break;
                case "-":
                    index--;
                    stack[index] -= stack[index + 1];
                    break;
                case "*":
                    index--;
                    stack[index] *= stack[index + 1];
                    break;
                case "/":
                    index--;
                    stack[index] /= stack[index + 1];
                    break;
                default:
                    index++;
                    stack[index] = Integer.parseInt(token);
            }
        }
        return stack[index];
    }

```
 :facepunch: 逆波兰数与卡塔兰数顶级理解好文
[https://www.it610.com/article/5789770.htm](https://www.it610.com/article/5789770.htm)
### 227. 基本计算器 II
![输入图片说明](https://foruda.gitee.com/images/1660266045295871576/无标题.png "无标题.png")

```
class Solution {
    public int calculate(String s) {
        int preSign='+';
        Stack<Integer> stack=new Stack<>();
        int length=s.length();
        for(int i=0;i<length;i++)
        {
            int ch=s.charAt(i);
            if(ch==' ')
            {
                continue;
            }
            
        if(ch>='0'&&ch<='9'){
            int num=0;
            while(i<length&&(ch=s.charAt(i))>='0'&&ch<='9'){
                num=num*10+ch-'0';
                i++;
            }
          i--;

        if(preSign=='*')
        {
            stack.push(num*stack.pop());
        }else if(preSign=='/'){
            stack.push(stack.pop()/num);
        }else if(preSign=='+'){
            stack.push(num);
        }else if(preSign=='-'){
            stack.push(-num);
        }
    }else{
        preSign=ch;
    }
 }
 int res=0;
 while(!stack.empty()){
     res+=stack.pop();
 }
return res;

    }
}
```

 
**知识盲点** 
>对于比较运算符==，>,<等，如果是普通类型之间的比较一般是转换成数字
比较运算符
![输入图片说明](https://foruda.gitee.com/images/1660270139948234692/qq截图20220808223603.png "QQ截图20220808223603.png")

### 1047. 删除字符串中的所有相邻重复项
用栈解决

>我们遍历字符串中的所有字母：
1，如果栈为空
就把当前字母加入到栈中。
2，如果栈不为空
如果当前字母等于栈顶元素，说明他俩是相邻且相同的，让他俩同时消失。
如果当前字母不等于栈顶元素，说明他俩是相邻但不相同，直接让当前字母入栈。


```
public String removeDuplicates(String S) {
 char[] chars = S.toCharArray();
 Stack<Character> stack = new Stack<>();
 int index = 0;
 int length = S.length();
 while (index < length) {
 char current = chars[index++];
 if (!stack.empty() && stack.peek() == current) {
 //如果栈顶的值和当前遍历的值相同，他两直接消失
 stack.pop();
 } else {
 //如果栈为空，或者栈顶元素和当前值不相同，就把当前值压入栈
 stack.push(current);
 }
 }
 //下面是把栈中的元素转化为字符串
 StringBuilder stringBuilder = new StringBuilder(stack.size());
 while (!stack.empty())
 stringBuilder.append(stack.pop());
 return stringBuilder.reverse().toString();
 }

```

用数组模拟栈解决（yyds）

```
class Solution {
    public String removeDuplicates(String s) {
        char [] str=s.toCharArray();
        int peek=-1;
        for(int i=0;i<str.length;i++){
            if(peek==-1||str[peek]!=str[i]){
                //模拟入栈
                str[++peek]=str[i];
            }else{
                //模拟出栈
                peek--;
            }
        }
        //字符数组转换为字符串
        return String.valueOf(str,0,peek+1);

    }
}
```
直接利用StringBuilder模拟栈(yyds)--优选

```
class Solution {
    public String removeDuplicates(String s) {
        StringBuffer stack = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                stack.deleteCharAt(top);
                --top;
            } else {
                stack.append(ch);
                ++top;
            }
        }
        return stack.toString();
    }
}


```
直接利用StringBuilder进一步优化

```
class Solution {
    public String removeDuplicates(String s) {
        StringBuilder p=new StringBuilder();
        int top=-1;//阀门
        for(int i=0;i<s.length();i++){
            char m=s.charAt(i);
            //top!=-1模拟栈为空
            if(top!=-1&&p.charAt(top)==m){
                //这两句达到了出栈的效果
                p.deleteCharAt(top);
                top--;
        //用continue可你模拟达到else的效果
                continue;
            }
            p.append(m);
            ++top;
        }
        return p.toString();
    }
}
```
 ** :raised_hands: 扩展知识盲点** 
StringBuilder下的方法
![输入图片说明](https://foruda.gitee.com/images/1660270009441029791/qq截图20220812100512.png "QQ截图20220812100512.png")

### 519 单调栈解下一个更大元素 I
>一但要求下一个更大的元素，就是用单调栈解，力扣题库相似的题目都是这个解法

暴力：

```
class Solution {

    public int check(int s,int[] nums2)
    {
        for(int i=0;i<nums2.length;i++)
        {
            if(s==nums2[i])
            {
                return i;
            }
        }
        return -1;

    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m=nums1.length;
        int n=nums2.length;
        int [] res=new int[m];
        Arrays.fill(res,-1);
        for(int i=0;i<m;i++)
        {
            int s=nums1[i];
            int j=check(s,nums2);
            for(int k=j+1;k<n;k++)
            {
                if(nums2[k]>s)
                {
                    res[i]=nums2[k];
                    break;
                }
            }
        }
        return res;


    }
}
```
单调栈

```
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
```

### 519 单调栈解下一个更大元素 ⅠⅠ

```
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer>stack=new Stack<>();
        int n=nums.length;
        int [] res =new int [n];
        Arrays.fill(res,-1);
        //数组长度走两遍来模拟循环
        for(int i=0;i<(n<<1);i++)
        {
            int index=i%n;
        while(!stack.empty()&&nums[stack.peek()]<nums[index]){
            res[stack.pop()]=nums[index];
            }
            stack.push(index);
        }
        return res;
    }
}
```
### 模板总结
![输入图片说明](https://foruda.gitee.com/images/1660271204184858446/qq截图20220812102622.png "QQ截图20220812102622.png")

```
 int res[] = new int[length];
 Stack<Integer> stack = new Stack<>();
 for (int i = 0; i < length; i++) {
 while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
 res[stack.pop()] = nums[i];
 //当前元素的下标入栈
 stack.push(i);
 }
```
## 946. 验证栈序列
类似于单调栈的模板，知识大于小于改成了==

```
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for(int i=0;i<pushed.length;i++)
        {
            stack.push(pushed[i]);
            while(!stack.isEmpty()&&stack.peek()==popped[j])
            {
                stack.pop();
                j++;
            }

        }
        return stack.isEmpty();

    }
}
```
![输入图片说明](%E9%A2%9C%E8%89%B2%E4%BD%A0.png)

# 二叉树相关
## 1.二叉树遍历的非递归方法
### 前序遍历

```
public void preDisplay2(Visitor<E> visitor){

        if(root==null||visitor==null)return;
        Node<E> node=root;
        Stack<Node<E>> stack=new Stack<>();
        while(true) {
            if (node != null) {
                if (visitor.visit(node.element)) {
                    return;
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
                node = node.left;
            }else if(stack.isEmpty()){
                return;
            }else{
                node=stack.pop();
            }
        }
    }
```
### 中序遍历

```
 public void inorderDisplay2(Visitor<E> visitor){
        if(root==null||visitor==null)return ;
        Node<E> node=this.root;
        Stack<Node<E>> stack=new Stack<>();
        while(true){

            if(node!=null){
                stack.push(node);
                node=node.left;
            }else if(stack.isEmpty())
            {
                return;
            }else{
                node=stack.pop();
                if(visitor.visit(node.element)){
                    return ;
                }
                node=node.right;
            }

        }
    }
```





## 99. 恢复二叉搜索树

> 利用中序遍历的有序性，记录当前遍历的数的前一个数，根据遍历的特点，判定是否符合要求。
>例如中序遍历的结果本应该是【1，3，5，7，9，10】但是3，7错误的交换，导致结果变成【1，7，5，3，9，10】.易知中序遍历的顺序是从小到大，当第一次出现前面的数比后面的数大的情况
则可以判定第一个交换元素，第二次出现前面的数比后面的数大的情况可以确定第二个交换的数

>二叉搜索树的定义是：若它的左子树不空，则左子树上所有结点的值均小于
它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的
值；它的左、右子树也分别为二叉搜索树。
``` 

 ** **1.递归法**  ** 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 //清楚二叉树的特点：中序遍历是有序的
class Solution {
//pre,first,second分别记录当前遍历的前一个数字，第一次出现问题的位置，第二次出现问题的位置
    private TreeNode pre;
    private TreeNode first;
    private TreeNode second;
    public void inorderDisplay(TreeNode node)
    {
        if(node==null)
        {
            return;
        }
        inorderDisplay(node.left);
//first==null这是第一次出现错误的位置，之前还未找到错误情况
        if(first==null&&pre!=null&&pre.val>node.val)
        {
            first=pre;
        }
//first!=null已经找到第一次出现问题的元素，现在是在判定第二处错误，first起到一个阀门的作用
        if(first!=null&&pre.val>node.val){
            second=node;
        }
        pre=node;
        inorderDisplay(node.right);


    }
    public void recoverTree(TreeNode root) {
        inorderDisplay(root);
//找到问题后交换回来
        int temp=first.val;
        first.val=second.val;
        second.val=temp;
    }

}
```

## 101. 对称二叉树
//以下写法会产生逻辑上的错误

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean check(TreeNode p,TreeNode q){
        if(p==null&&q==null)
        {
            return true;
        }
        if(p==null||q==null){
            return false;
        }
       if(p.val!=q.val)
       {
           return false;
       }
       check(p.left,q.right);
       check(p.right,q.left);
       return true;
    }
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);

    }
}
```


![输入图片说明](%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91%E5%9B%BE%E8%A7%A3.png)



## 100. 相同的树

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean check(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }
        return p.val==q.val&&check(p.left,q.left)&&check(p.right,q.right);
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return check(p,q);

    }
}
```

## 对称二叉树，相同的树模板总结



![输入图片说明](2.png)


## 662. 二叉树最大宽度(中等)

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Deque<TreeNode> queue=new LinkedList<>();
        int usedSize=0;
        root.val=1;
        int max=0;
        queue.offer(root);
        while(!queue.isEmpty()){
            usedSize=queue.size();
        int left=queue.peekFirst().val;
        int right=queue.peekLast().val;
        max=Math.max(max,right-left+1);
        for(int i=0;i<usedSize;i++){
            TreeNode node=queue.poll();
            int temp=node.val;
            if(node.left!=null){
                node.left.val=temp*2;
                queue.offer(node.left);
            }
            if(node.right!=null)
            {
                node.right.val=temp*2+1;
                queue.offer(node.right);
            }
        }
        }
        return max;
    }
}
```




![输入图片说明](%E6%97%A0%E6%A0%87%E9%A2%98.png)


## 96. 不同的二叉搜索树(简单)

```
class Solution {
    public int numTrees(int n) {
        if(n==1||n==0)
        {
            return 1;
        }
        int sum=0;
        for(int i=1;i<=n;i++)
        {
           int left=numTrees(i-1);
           int  right=numTrees(n-i);
            sum+=left*right;
        }
        return sum;
    }
}
```

![输入图片说明](%E6%97%A0%E6%A0%87%E9%A2%98.png)

## 98. 验证二叉搜索树（利用中序遍历和二叉搜索树的有序性转化为数组中进行操作）

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void inorderDisplay(TreeNode root,List<Integer>list )
    {
        if(root==null)
        {
            return;
        }
        inorderDisplay(root.left,list);
        list.add(root.val);
        inorderDisplay(root.right,list);
    }
    public boolean isValidBST(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        inorderDisplay(root,list);
        for(int i=0;i<=list.size()-2;i++)
        {
            if(list.get(i)>=list.get(i+1))
            {
                return false;
            }
        }
       return true;
    }
}
```
写法二（借鉴：此方法的优化）
这样写不用单独再开辟一个顺序表，并且避免不断调用get（）方法大大提高了效率。（运用标记记录当前节点的大小）

```
class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}
```

## 104. 二叉树的最大深度


```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
        int height=0;
        int levelSize = 1;
        Queue<TreeNode> queue =new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode ret=queue.poll();
            levelSize--;
            if(ret.left!=null){
                queue.offer(ret.left);
            }
            if(ret.right!=null){
                queue.offer(ret.right);
            }
            if (levelSize == 0) { // 意味着即将要访问下一层
				levelSize = queue.size();
				height++;
			}
        }
        return height;
    }
}
```
方法二：

```
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
     return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}
```
## 110. 平衡二叉树
(再不在节点类中额外添加height成员变量的前提下)
和AVL树中的思路一样，只是这里节点类型是已经定义好了，没有额外的height成员变量
但是这里用到了两次递归（效率不高）

```
class Solution {
    private int heightAbs (TreeNode node){
        if(node==null)
        {
            return 0;
        }
        return Math.max(heightAbs(node.left),heightAbs(node.right))+1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null)
        {
            return true;
        }
        return Math.abs(heightAbs(root.left)-heightAbs(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
}
```

法二
```
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}
```
## 111. 二叉树的最小深度
与最大高度进行比较

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
     return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}
```
最小高度

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
        if(root.left==null&&root.right!=null)
        {
            return 1+minDepth(root.right);
        }
        if(root.left!=null&&root.right==null)
        {
            return 1+minDepth(root.left);
        }
        return 1+Math.min(minDepth(root.left),minDepth(root.right));
    }
}
```

为什么最小深度就要进行单子树为空判断

```
 if(root.left==null&&root.right!=null)
        {
            return 1+minDepth(root.right);
        }
        if(root.left!=null&&root.right==null)
        {
            return 1+minDepth(root.left);
        }
```
因为如果直接执行这个语句：空的子树返回0一定会最小的，深度恒为1

```
  return 1+Math.min(minDepth(root.left),minDepth(root.right));
```






# 字符串相关
## 反转字符串相关

### 344. 反转字符串（简单双指针）
1.写法一

```
class Solution {
    public void reverseString(char[] s) {
         int p=0;
        int q=s.length-1;
        while(p<q)
        {
            char temp=s[p];
            s[p]=s[q];
            s[q]=temp;
            p++;
            q--;
        }
    }
}
```
2.写法二：
```
class Solution {
    public void reverseString(char[] s) {
        for (int i = 0, j = s.length - 1; i < j; i++, j--) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
        }
    }
}

```

### 541. 反转字符串 II
java的一般写法

```
class Solution {

    private String check(char [] ret,int pos,int end)
    {
        while(pos<end){
            char temp=ret[pos];
            ret[pos]=ret[end];
            ret[end]=temp;
            pos++;
            end--;
        }
        return ret.toString();
    }
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
//注意这里的设计思想，对于特定节点段有特定要求的题要调整for循环只对特定的要求区间进行处理
            check(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }
}
```

### 557. 反转字符串中的单词 III

```
class Solution {
    public String reverseString(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            ++left;
            --right;
        }
        return new String(chars);
    }
    public String reverseWords(String s) {
        StringBuilder str=new StringBuilder();
        String [] words=s.split(" ");
        //字符串数中利用索引代表元素-->代表的是一串地址。
        //用不到索引的地方优先考虑for-each循环
        for(String word:words){
            if(str.length()!=0)
            {
                str.append(" ");
            }
            str.append(reverseString(word));
        }

        return str.toString();
    }

}
```
# 双指针相关
## （1）两个数组的交集
## 349. 两个数组的交集，350. 两个数组的交集 II模板总结

![输入图片说明](s.png)
# 堆相关（优先级对列）
## 1.topk问题
## 347. 前 K 个高频元素



```
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //map分别存储元素与其对应的元素
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            //数组中已经有这个元素了
            if(map.containsKey(num))
            {
                map.put(num,map.get(num)+1);
            }else{
                //第一次加入
                map.put(num,1);
            }
        }
    
    PriorityQueue<Integer> queue=new PriorityQueue<>( 
        (o1,o2)->map.get(o1)-map.get(o2)
    );
       for(int num:map.keySet())
        {
            if(queue.size()<k)
            {
                queue.add(num);
            }else{
        if(map.get(num)>=map.get(queue.peek()))
                {
                    queue.poll();
                    queue.add(num);
                }
            }
        }
    int[] arr=new int[queue.size()];
    int i=0;
    while(i<arr.length)
    {
        arr[i++]=queue.poll();
    }
    return arr;
    }
}
```


![输入图片说明](%E6%97%A0%E6%A0%87%E9%A2%98.png)


## （2）506. 相对名次

```
class Solution {
    public String[] findRelativeRanks(int[] score) {
        int n=score.length;
        //辅助数组记录数据以及他的初始位置
        int [][]arr=new int[n][2];
        String [] dest={ "Gold Medal","Silver Medal","Bronze Medal"};
        for(int i=0;i<n;i++)
        {

            arr[i][0]=score[i];
            arr[i][1]=i;
        }
         Arrays.sort(arr,(o1,o2)->o2[0]-o1[0]);
         String[] result=new String [n]; 
        for(int i=0;i<n;i++)
        {
                if(i>=3)
                {
                    result[arr[i][1]]=String.valueOf(i+1);
                }else{

                    result[arr[i][1]]=dest[i];
                }
        }
        return result;
    }
}
```



```
class Solution {
    public String[] findRelativeRanks(int[] score) {
        Map<Integer,Integer> map=new HashMap<>();
        PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->o2-o1);
        for(int i=0;i<score.length;i++)
        {
            map.put(score[i],i);
             queue.add(score[i]);
        }
         String [] ret=new String [score.length];
         int flag=0;
    while(!queue.isEmpty()){
        int index=map.get(queue.poll());
        flag++;
        switch(flag){
            case 1:
            ret[index]="Gold Medal";
            break;
            case 2:
            ret[index]="Silver Medal";
            break;
            case 3:
            ret[index]="Bronze Medal";
            break;
            default:
            ret[index]=String.valueOf(flag);
        }
    }
    return ret;
    }
}


```