0. Leetcode 917. Just Reverse Letters

Given a string s , reverse the string according to the following rules:
All non-English letters remain in their original positions.
All English letters (lowercase or uppercase) are reversed.
Returns the reversed s .

Analysis and Answers

Borrowing the idea of ​​double pointers, to change the order of all letters in a word, you only need to pair the beginning and end to find the corresponding letter position. Therefore, let i start from the beginning, and j search for letters from the end. After finding them, exchange them until i > = J, indicating that all letters in the word have been exchanged

class Solution {
public:
    string reverseOnlyLetters(string s) {
        for (int i = 0, j = s.size() - 1; i < j;) {
            while (!(tolower(s[i]) >= 'a' && tolower(s[i]) <= 'z') && i < j) {
                i++;
            }

            while (!(tolower(s[j]) >= 'a' && tolower(s[j]) <= 'z') && i < j) {
                j--;
            }

            if (i >= j) {
                break;
            } else {
                char tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
            }

            // After the swap, move the pointer to the next character to be judged
            i++;
            j--;
        }

        return s;
    }
};

The time complexity of the algorithm is O ( N ) O(N) O(N)

1. Leetcode 167. Sum of Two Numbers II - Input Sorted Array

Given an integer array numbers with subscripts starting from 1, the array has been arranged in non-decreasing order, please find two numbers from the array whose sum is equal to the target number target. If the two numbers are numbers[index1] and numbers[index2] respectively, then 1 < = index1 < index2 < = numbers length .
Returns the subscripts index1 and index2 of these two integers as an integer array [index1, index2] of length 2.
You can assume that each input corresponds to a unique answer, and you cannot reuse the same elements.
The solution you design must use only constant-level extra space.

Analysis and Answers

Solution 1: Binary Search
For this problem, traverse the array from beginning to end, and for each number num, binary search to see if target - num exists in the array.

class Solution {
public:
    int findPos(vector<int>& numbers, int low, int high, int target) {
        int l(low), r(high);
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (numbers[mid] < target) {
                l = mid + 1;
            } else if (numbers[mid] > target) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        
        return -1;
    }

    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        bool find(false);
        for (int i = 0; i < numbers.size(); ++i) {
            int idx = findPos(numbers, i+1, numbers.size() - 1, target - numbers[i]);
            if (idx > 0) {
                result.push_back(i+1);
                result.push_back(idx+1);
                break;
            }
        }
        return result;
    }
};

The time complexity of the algorithm is O ( N l o g N ) O(NlogN) O(NlogN)
Solution 2: Double pointer
Let the two pointers point to the first number and the last number respectively. If the sum of the two numbers is greater than target, the tail pointer is moved forward; if the sum of the two numbers is greater than the target, the first pointer is moved backward.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        int i(0), j(numbers.size() - 1);
        while (i < j) {
            if (numbers[i] + numbers[j] < target) {
                i++;
            } else if (numbers[i] + numbers[j] > target) {
                j--;
            } else {
                result.push_back(i + 1);
                result.push_back(j + 1);
                break;
            }
        }
        
        return result;
    }
};

The time complexity of the algorithm is O ( N ) O(N) O(N)

2. Leetcode 165. Compare version numbers

You are given two version numbers version1 and version2 , please compare them.
The version number consists of one or more revision numbers, each of which is connected by a '.'. Each revision number consists of multiple digits, possibly including leading zeros. Each version number contains at least one character. Revision numbers are numbered from left to right, with subscripts starting at 0, with the leftmost revision numbered at 0, the next revision at 1, and so on. For example, both 2.5.33 and 0.1 are valid version numbers.
When comparing version numbers, compare their revision numbers in order from left to right. When comparing revision numbers, simply compare the integer value ignoring any leading zeros. That is, revision number 1 and revision number 001 are equal. If the version number does not specify a revision number at a subscript, the revision number is treated as 0. For example, version 1.0 is smaller than version 1.1, because they have the same revision number with subscript 0, while the revision numbers with subscript 1 are 0 and 1 respectively, 0 < 1
The return rules are as follows:
Returns 1 if version1 > version2,
Returns -1 if version1 < version2,
Otherwise return 0.

Analysis and Answers

Let the two pointers point to the head of the string, move the pointer r backward until the character . is found, then take the string from the pointers and compare them. Repeat this process until the traversal is complete.

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int l0(0), r0(0);
        int l1(0), r1(0);
        int result(0);
        
        version1 += ".";
        version2 += ".";
        while (r0 < version1.size() || r1 < version2.size()) {
            string str1 = "0";
            string str2 = "0";
            if (r0 < version1.size()) {
                while (version1[r0] != '.') {
                    r0++;
                }
                while (version1[l0] == '0') {
                    l0++;
                }
                if (r0 - l0 > 0) {
                    str1 = version1.substr(l0, r0 - l0);
                }
            }
            
            if (r1 < version2.size()) {
                while (version2[r1] != '.') {
                    r1++;
                }
                while (version2[l1] == '0') {
                    l1++;
                }
                if (r1 - l1 > 0) {
                    str2 = version2.substr(l1, r1 - l1);
                }
            }
            
            if (stoi(str1) < stoi(str2)) {
                result = -1;
                break;
            } else if (stoi(str1) > stoi(str2)) {
                result = 1;
                break;
            }
            
            r0++;
            l0 = r0;
            r1++;
            l1 = r1;
        }
        
        return result;
    }
};

The time complexity of the algorithm is O ( N ) O(N) O(N)

3. Leetcode 443. Compressed Strings

Given a character array chars , use the following algorithm to compress:
Start with an empty string s. For each group of consecutive repeating characters in chars :
If the set is of length 1, append characters to s.
Otherwise, append characters to s, followed by the length of the group.
The compressed string s should not be returned directly, it needs to be dumped into the character array chars. Note that if the group length is 10 or more, it will be split into multiple characters in the chars array.
Please return the new length of the array after modifying the input array.
You must design and implement an algorithm that uses only constant extra space to solve this problem.

Analysis and Answers

Let the pointer i be the write pointer to record the position of the written character; the pointer j as the read pointer, record the position of the read character, move the pointer j backward until the new character is different from the previous character, then use the pointer i to write. Repeat this process until the traversal is complete.

class Solution {
public:
    int compress(vector<char>& chars) {
        int i(0), j(1);
        char preChar = chars[0];
        int count = 1;
        string cstr;
        while (j < chars.size()) {
            if (preChar != chars[j]) {
                chars[i++] = preChar;
                if (count > 1) {
                    cstr = to_string(count);
                    for (int k = 0; k < cstr.size(); ++k) {
                        chars[i++] = cstr[k];
                    }
                }
                preChar = chars[j];
                count = 1;
            } else {
                count++;
            }
            j++;
        }
        chars[i++] = preChar;
        if (count > 1) {
            cstr = to_string(count);
            for (int k = 0; k < cstr.size(); ++k) {
                chars[i++] = cstr[k];
            }
        }

        return i;
    }
};

The time complexity of the algorithm is O ( N ) O(N) O(N)

Summarize

Using double pointers can effectively reduce the time complexity and simplify the problem.