LeetCode 特训 ---- Week1网站首页 技术杂谈

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> inds;
        for (int i = 0; i < nums.size(); i ++) {
            int distance = target - nums[i];
            //不是ans, 加入hash表中
            if (inds.empty() || inds.find(distance) == inds.end()) {
                inds[nums[i]] = i;
                continue;
            } 
            return {inds[distance], i};
        }
        return {-1, -1};
    }
};

方式2：很明显借助排序之后结果用左右指针遍历搜索也可以达到目的，反正只要存在答案，我们遍历所有可能成为答案的情况就一定可以找到结果。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::vector<int> copy_nums(nums.begin(), nums.end());
        std::sort(nums.begin(), nums.end()); //sort
        int l = 0, r = nums.size() - 1; //左右指针记录ans
        while (l < r) {
            if (nums[l] + nums[r] == target) {
                break;
            } else {
                if (nums[l] + nums[r] < target) {
                    l ++;
                } else {
                    r --;
                }
            }
        }
        if (l >= r) {
            return {-1, -1};
        }
        std::vector<int> ans;
        for (int i = 0; i < nums.size(); i ++) {
            if (copy_nums[i] == nums[l] 
            || copy_nums[i] == nums[r]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

最长回文子串

力扣

解题思路：

1. 因为是子序列问题，不清楚边界，方式1，在每一个位置都可能是结果，从中间向两边自由扩散获取结果。(老哥给的经验，边界不明确的问题，可以直接的进行一个一点点的扩大，一点点的从中间向两边扩散找边界)

//边界问题是写双指针最应该注意的.
class Solution {
    //寻找以lbegin, rbegin左右扩散的最长回文子串
    std::string subPalindrome(std::string& s, int lbegin, int rbegin) {
        int l = lbegin, r = rbegin, n = s.size();
        while (l >= 0 && r < n && s[l] == s[r]) {
            l --, r ++;
        }
        //l位置不可取 【l+1, r-1】区间元素个数(r-1-l-1+1) = (r-l-1)个
        return s.substr(l + 1, r - l - 1);
    }
public:
    string longestPalindrome(string s) {
        std::string ans = "";
        for (int i = 0; i < s.size(); i++) {
            std::string s1 = subPalindrome(s, i, i);//奇数串 
            std::string s2 = subPalindrome(s, i, i + 1);//偶数串
            ans = ans.size() >= s1.size() ? ans : s1; 
            ans = ans.size() >= s2.size() ? ans : s2; 
            //std::cout << ans << std::endl;
        }
       return ans;
    }
};

2. 可以使用动态规划，记忆化搜索的方式，用空间来提高效率。

删除有序数组中的重复项

力扣力扣

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int last = 0, front = 0;
        while (front < nums.size()) {
            if (nums[last] != nums[front]) {   //非重复, 符合题意的值，放入slow结果序列
                nums[++last] = nums[front]; 
            }
            front ++;                          //前指针继续向前探路，寻求非重复值
        }
        return last + 1;
    }
};

删除有序数组中的重复项Ⅱ

力扣

核心思路还是前后（快慢）指针，只不过中间需要维护一个计数器

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int last = 0, front = 0, n = nums.size();
        int count = 0;
        int preval = nums[0];       //记录前面的遍历值
        while (front < n) {
            if (nums[front] != preval) {//一个子序列值遍历完毕
                count = 0;
                preval = nums[front];
            }
            if (count < 2) {
                nums[last++] = nums[front];
            }
            front ++;           //向后寻求符合要求的值，
            count ++;           //计数
        }
        return last;
    }
};

删除链表中的重复元素

力扣

解题思路还是哪个思路，向后寻找非重复元素链接到前面去就OK了。前面的p指针相当于是做数组题目时候的last指针，维护着结果序列

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return nullptr;
        ListNode* last = head, *front = head;
        while (front) {
            if (last->val != front->val) {  //非重复值，留下来.
                last->next = front;
                last = last->next;
            }
            front = front->next;  //向前探路
        }
        last->next = nullptr;
        return head;
    }
};

移动0

力扣

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int last = 0, front = 0, n = nums.size();
        while (front < n) {
            if (nums[front] != 0) {     //寻求到非零数字, 放到last结果序列中
                nums[last++] = nums[front];
            } 
            front ++;                   //向后寻求非零数字
        }
        //将后续制0
        while (last < n) {
            nums[last++] = 0;
        }
    }
};

快慢指针，前后指针的核心思想在那里？

慢指针停留在后面，保留的是最终结果，快指针跑在前面探路，寻找的是可以留下来当作结果的值。（符合题意，需要留下的值）

旋转链表

力扣

思路：很明显，右边移动几个位置，相当于是头结点换成了右边的第k%num个结点。所以很自然的可以想到先成环，再断开。链表的操作注意头部结点和边界问题。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr) { return nullptr; }
        int cnt = 1;
        ListNode* p = head;
        while (p->next) {//计算元素个数并且p走到尽头
            cnt ++;
            p = p->next;
        }
        p->next = head;//成环
        k %= cnt;
        // 走到cnt-k节点处断开
        int n = cnt - k; 
        p = head;
        while (--n) {
            p = p->next;
        }
        ListNode* ans = p->next;
        p->next = nullptr;
        return ans;
    }
};

分隔链表

力扣

思路：很明显的按照题意走即可。遍历原链表拆成两个部分的子链表，然后两个子链表连起来就OK了。还是需要注意边界，结束位置要有nullptr，链表的题目往往难度不在思维，在乎对于指针的控制，以及边界的顾及。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == nullptr) { return nullptr; }
        ListNode h1, h2, *t1, *t2;//记录两条链表的头尾
        t1 = &h1, t2 = &h2;
        ListNode *p = head; 
        while (p) {
            if (p->val < x) {
                t1->next = p;
                t1 = t1->next;
            } else {
                t2->next = p;
                t2 = t2->next;
            }
            p = p->next;
        }
        t1->next = h2.next;//中间衔接
        t2->next = nullptr;//末尾制空，否则死循环了 细节。。。
        return h1.next;
    }
};