#include <iostream>

using namespace std;

int main(){
    string s;
    cin >> s;
    
    int oldSize = s.size();
    // cnt 用来记录字符串中的数字的个数
    int cnt=0;
    for (int i=0; i<s.size();i++){
        if (s[i] >= '0' && s[i] <='9') cnt += 1;
    }
    // 新数组大小
    
    int newSize = s.size()+cnt*5;
    // 扩充数组
    s.resize(newSize);
    
    // 使用双指针
    int oldIndex = oldSize-1, newIndex = newSize-1;
    
    // 从后向前遍历原数组
    while(oldIndex >= 0){
        if (s[oldIndex] >= '0' && s[oldIndex] <= '9'){
            
            s[newIndex] = 'r';
            s[newIndex-1] = 'e';
            s[newIndex-2] = 'b';
            s[newIndex-3] = 'm';
            s[newIndex-4] = 'u';
            s[newIndex-5] = 'n';
            
            newIndex = newIndex-6;
            oldIndex--;
            
        }else{
            s[newIndex] = s[oldIndex];
            newIndex--;
            oldIndex--;
        }
    }
    cout << s << endl;
}

4. 反转字符串里的单词

link: LeetCode 151

思路：

首先去除字符串中的多余空格（此处因为对字符串的长度进行了更改，因此需要返回新的字符串）
翻转整个字符串（此时传入的 start 和 end 是新的字符串的 start 和 end）
翻转每个单词（需要遍历字符串，使用双指针找到每个单词的起始位置和终止位置，然后将单词进行翻转）

有很多细节

class Solution {

    public String reverseWords(String s) {

        // 1. 去除多余的空格

        StringBuilder sb = reverseSpace(s);

        // 2. 翻转整个字符串

        reverseString(sb, 0, sb.length()-1);

        // 3. 遍历字符串, 翻转每一个单词

        reverseEachWord(sb);

  

        return sb.toString();

    }

  

    // 1. 去除多余的空格

    public StringBuilder reverseSpace(String s){

        StringBuilder resBuilder = new StringBuilder();

        // 首先去除开头和结尾的空格

        int start = 0, end = s.length()-1;

        while(s.charAt(start) == ' ') start++;

        while(s.charAt(end) == ' ') end--;

  

        // 遍历整个字符串, 去除多余的空格

        while(start <= end){

            if (s.charAt(start) != ' ' || s.charAt(start-1) != ' '){

                resBuilder.append(s.charAt(start));

            }

            start++;

        }

        return resBuilder;

  
  

    }

  

    // 2. 翻转整个字符串 左闭右闭

    public void reverseString(StringBuilder sb, int start, int end){

        while(start < end){

            char temp = sb.charAt(start);

            sb.setCharAt(start, sb.charAt(end));

            sb.setCharAt(end, temp);

            start++;

            end--;

        }

    }

    // 3. 遍历字符串, 翻转每一个单词

    public void reverseEachWord(StringBuilder sb){

        // left: 单词的开头  right：单词的结尾

        int left=0,right=1, len=sb.length();

        while(left < len){

            // 寻找到单词后面的空格的索引

            while(right < len && sb.charAt(right) != ' ') right++;

            // 进行翻转

            reverseString(sb, left, right-1);

            // 更新新的单词在开头

            left = right+1;

            right = left+1;

        }

    }

  
  
  
  

}

5. 翻转链表

思路：

使用双指针，pre 指向当前节点前面的节点，cur 指向当前节点，并用 temp 保存当前节点后面的节点
改变当前节点与前面节点的指针指向后，pre 和 cur 都向前移动一位，直到 cur=null

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode reverseList(ListNode head) {

        // 定义双指针

        ListNode preNode = null;

        ListNode curNode = head;

        while(curNode != null){

            ListNode tempNode = curNode.next;

            curNode.next = preNode;

            preNode = curNode;

            curNode = tempNode;

        }

  

        return preNode;

    }

}

6. 删除链表的倒数第N个节点

思路：

使用虚拟节点，从而保证删除头节点和删除其他节点的逻辑一致
使用双指针，fast指针先向前走N步，然后 slow 和fast 同时向前走，当fast指针走到最后一个节点的时候，slow指针正好指向要删除节点的前面的节点

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

       if (head == null) return null;

       ListNode virtualHead = new ListNode(-1, head);

       ListNode slow = virtualHead;

       ListNode fast = virtualHead;

  

       while(n-- > 0) fast = fast.next;

       while(fast.next != null) {

            slow = slow.next;

            fast = fast.next;

       }

       // 找到要删除节点的前面的节点

       slow.next = slow.next.next;

       return virtualHead.next;

  
  
  
  

    }

}

7. 链表相交

link: LeetCode

思路：

首先遍历两个链表，确定两个链表的长度差 gap
使用双指针，一个指向短链表，一个指向长链表，指向长链表的指针先移动 gap 步，然后两个指针一块移动，直到指向的节点相等或者到链表末尾为null

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int lenA = 0;

        int lenB = 0;

        ListNode cntA = headA;

        ListNode cntB = headB;

        while(cntA != null) { lenA++; cntA = cntA.next;}

  

        while(cntB != null) { lenB++; cntB = cntB.next;}

  

        // 保证A一直是长链表

        if (lenA < lenB){

            int temp = lenA;

            lenA = lenB;

            lenB = temp;

  

            ListNode tempNode = headA;

            headA = headB;

            headB = tempNode;

        }

  
  

        // 计算两个链表的长度差

        int gap = lenA - lenB;

  

        // 定义两个指针分别指向两个链表

        ListNode indexA = headA;

        ListNode indexB = headB;

        while(gap-- > 0){

            indexA = indexA.next;

        }

        while(indexA != null){

            if (indexA == indexB) return indexA;

            else{

                indexA = indexA.next;

                indexB = indexB.next;

            }

        }

  

        return null;

  
  
  

    }

}

8. 环形链表

link: LeetCode 142

思路：

首先通过快慢双指针确定两个指针在链表中相遇的位置，其中快指针每次走两步，慢指针每次都一步，因此快指针相对于慢指针每次多走了一步，因此如果有环，必定相遇（并且是在慢指针进入环的第一圈相遇）
寻找环的入口，再次定义两个指针，分别指向头节点 headIndex 和相遇的节点 metIndex

根据第一步的快慢指针可以得到等式： $2(x+y) = x + n(y+z) + y$ , 经过化简得到

x = n(y+z) - y = (n-1)(y+z) + z

因此在第二步定义的两个指针同时开始走，必定会在环的入口处相遇

9. 三数之和

link: LeetCode 15

注意：题目要求返回的是三元组，即满足条件的元素，不是下标；并且三元组不能重复

思路：

首先将数组按照从小到大的顺序排序
使用 $i$ 遍历整个数组
然后定义双指针，left=i+1, rigth=nums.length-1, 当三元组的和小于target，则 left 向右移动，如果三元组的和大于 target, 则right向左移动(临界条件 left < right)
去重

首先需要对三元组的第一个数 a = nums[i] 进行去重, 因为如果 nums[i]=nums[i-1], 之前已经对 nums[i-1] 进行了处理, 对 nums[i] 进行处理的结果是对nums[i-1]处理结果的子集，因为要求三元组不能重复, 因此需要去重
当满足题目条件后, 如果 nums[left] = nums[left-1], 则left继续向右移动; 如果 nums[right] = nums[right+1], right继续向左移动

10. 四数之和

link: LeetCode 18

思路： 在三数之和的基础上，再套上一层 for 循环

每一层for循环都需要去重

class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> resList = new ArrayList<>();

        // 将数组排序

        Arrays.sort(nums);

        if (nums.length < 4) return resList;

  

        for (int i=0; i<nums.length-3; i++){

            if (nums[i] > 0 && nums[i] > target) break;

            // 去重

            if (i > 0 && nums[i] == nums[i-1]) continue;

            for (int j=i+1; j<nums.length-2;j++){

                // 去重

                if (j > i+1 && nums[j] == nums[j-1]) continue;

  

                int left = j+1, right = nums.length-1;

                while(left < right){

                    int sum = nums[i] + nums[j] + nums[left] + nums[right];

                    if (sum == target){

                        resList.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        left++;

                        right--;

                        while(left < right && nums[left] == nums[left-1]) left++;

                        while(left < right && nums[right] == nums[right+1]) right--;

                    }

                    else if (sum > target) right--;

                    else if (sum < target) left++;

                }

  

            }

        }

        return resList;

  

    }

}

版权所有

版权归属：cloudinwind

本文链接：/review/qvl10fw2/

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)