LeetCode+ 16 - 20

最接近的三数之和

算法标签：数组、双指针、排序

LeetCode+ 11 - 15_小雪菜本菜的博客-CSDN博客

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums中选出三个整数，使它们的和与 target 最接近

最接近有两层含义：①大于等于 target 的最小数 ②小于等于 target 的最大数，一种在 t 右边，一种在 t 左边，两种情况都要考虑

题目保证只存在唯一答案，不需要考虑判重问题

最坏情况下，三重循环，枚举 i、j、k，每种答案枚举一遍，求一个最接近的就可以了，暴力求解

可以考虑用双指针优化，先把数组从小到大排序，因为有三个变量，不好直接用双指针，先枚举其中一个变量 i，枚举 i 后 nums[ i ] 固定，用双指针枚举 j 和 k，对于每一个 j 要找到一个最小的 k，使得 num[ i ] + nums[ j ] + nums[ k ] ≥ target，这样就可以枚举出大于等于 target 的最小值

接下来找一下另一种情况：小于等于 target 的最大值，没有必要重新写一遍整个代码，只要枚举出大于等于 target 的最小的 k，num[ i ] + nums[ j ] + nums[ k - 1 ] 必然＜ target，可以发现只要把 k - 1 带入就是小于 target 的最大数

对于每一个 i、j、k 都用这两种情况来更新一下最小值即可

nums[ i ] 是固定的，当 nums[ j ] 变大之后，num[ i ] + nums[ j ] + nums[ k ] 还是 ≥ target，所以 nums[ k ] 不可能变大，只能是不变或者变小

由于 j 增加的时候，k 一定减小，可以用双指针算法去掉一维

abs 函数的效率是 O(1) 的，pair 比较先比较 first，如果 first 相同再比较 second：C++ pair的比较大小

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        //排序
        sort(nums.begin(),nums.end());
        //需要求答案 存储的时候不仅要存差值还要存储和 需要用 pair 存储
        pair<int,int> res(INT_MAX,INT_MAX);
        //枚举 i j k
        for(int i = 0;i < nums.size();i++) {
            for(int j = i + 1,k = nums.size()- 1;j < k;j++) {
                //对于每一个 j 找一个最小的 k
                while(k - 1 > j && nums[i] + nums[j] +nums[k -1] >= target) k--;
                //总和
                int s = nums[i] + nums[j] + nums[k];
                //答案是最小的一个 注意 s - target 不一定大于等于 target,target 可能很大会出现小于等于target的情况
                res = min(res,make_pair(abs(s - target),s));
                if(k - 1 > j) {
                    s = nums[i] + nums[j] + nums[k - 1];
                    res = min(res,make_pair(target - s,s));
                } 
            }
        }
        return res.second;
    }
};

电话号码的字母组合

算法标签：哈希、字符串、回溯、暴搜、递归

给出一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合，每一个数字代表 3 ~ 4 个字符，给出摁的顺序，问：对应了多少种不同的字符序列？

样例中摁下 23，2 有 abc 三种选择，3 有 def 三种选择，相乘一共有九种选择

题目中给出一个不定长度的字符串，要求把它所有可能的组合输出，经典的 dfs 问题

下面给出递归搜索树，然后把递归搜索树转换成代码

递推和递归_小雪菜本菜的博客-CSDN博客

在递归的时候：①需要用 string path 存储路径 / 方案 ②需要用 int u 存储当前是第几位

怎么可以很方便地求出一个数字可以表示哪些字母呢？可以开一个数组来表示

整个算法的时间复杂度和长度有关，最坏情况下，每个数字有 4 种选择，时间复杂度最坏是 4^n，push_back 答案需要 O( n ) 的时间复杂度，字符串长度是 n，最终时间复杂度是 4^n × n

class Solution {
public:
    //外部变量记录答案
    vector<string> ans;
    //用一个数组来表示每一个数字所有可能的情况
    string strs[10] = {
        //0 1 为空
        "","","abc","def",
        "ghi","jkl","mno",
        "pqrs","tuv","wxyz",
    };
    vector<string> letterCombinations(string digits) {
        //如果字符串为空直接返回
        if(digits.empty()) return ans;
        //传入字符串 当前是第几位 最一开始路径为空
        dfs(digits,0,"");
        return ans;
    }
    void dfs(string& digits,int u,string path) {
        //如果等于最后一位,在答案中加入当前方案
        if(u == digits.size()) ans.push_back(path);
        else {
            //否则遍历当前这一位可以取哪些字符
            for(auto c : strs[digits[u] - '0'])
                dfs(digits,u + 1,path + c);
        }
    }
};

四数之和

算法标签：数组、双指针、排序

 

 

参考第 15 题 LeetCode+ 11 - 15_小雪菜本菜的博客-CSDN博客

四数之和暴力做法，四重循环时间复杂度为 O( n^4 )，双指针优化为 O( n^3 )

先枚举两个变量，后面两个变量用双指针算法优化成 O( n )，去重的方法和前面一样

每个指针如果和前一个数一样，就跳过，这样就可以不重不漏地找到所有方案( 如果和前一个数一样，就说明当前的状态前面已经枚举过了，而且只要当前这个数和前面那个数不一样，方案就一定完全不一样 )

三数之和先枚举其中一个数，四数之和先枚举其中两个数. . .

 i , j, k,u 加起来可能会溢出
把 nums[i] + nums[j] + nums[k] + nums[u] ==  targe    改成 nums[i] + nums[j] - target == - nums[k] - nums[u]
把 nums[i] + nums[j] + nums[k] + nums[u-1] >= target 改成 nums[i] + nums[j] >= target - (nums[k] + nums[u-1])

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //排序
        sort(nums.begin(),nums.end());
        //记录答案
        vector<vector<int>> res;
        //先枚举第一个指针 
        for(int i = 0;i < nums.size();i++ ) {
            //判断当前数如果等于上一个数就跳过
            if(i && nums[i] == nums[i - 1]) continue;
            //再枚举第二个指针
            for(int j = i + 1;j < nums.size();j++ ) {
                //j 不是第 1 个数 并且 nums[j] 等于上一个数 跳过
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;       
                //枚举第三个变量 从 j + 1 开始双指针算法
                for(int k = j + 1,u = nums.size() - 1;k < u;k++ ) {
                    if(k > j + 1 && nums[k] == nums[k - 1]) continue;
                    //对于这个 k 找到一个最小的 u 使得四数之和大于等于 target
                    while(u - 1 > k && nums[i] + nums[j] >= target - (nums[k] + nums[u-1])) u--;
                    //如果四数之和等于 target 就把当前方案加到答案中
                    if(nums[i] + nums[j] - target == - nums[k] - nums[u]) {
                        res.push_back({nums[i],nums[j],nums[k],nums[u]});
                    }
                }
            }
        }
        return res;
    }
};

删除链表的倒数第 N 个结点

算法标签：链表、双指针

 

 

 

给出一个链表，要求删除链表的倒数第 n 个节点

可能会删除头节点，凡是头节点会改变的情况，都可以加一个虚拟头节点，这样就一定不会删除头节点

删除倒数第 k 个点的核心就是：找到倒数第 k 个点的前一个点，然后让前一个点的 next 指针等于当前这个点的下一个指针

链表总长度是 n，要找倒数第 k 个点的前一个点，也就是倒数第 k + 1 个点，可以先遍历整个链表，求出链表的总长度 n，从头往后遍历到倒数第 k + 1 个点就可以了

从虚拟头节点开始，想找到倒数第 k + 1 个点需要跳多少步呢？跳 1 步可以跳到第 2 个点，要跳到倒数第 k + 1 个点，一共有 n 个点，倒数第 k + 1 个点也就是正数的 n + 1 - ( k + 1 )，也就是正数的第 n - k 个点

跳 1 步可以跳到第 2 个点，如果想跳到第 n - k 个点，需要跳 n - k - 1 步

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int k) {
        //建立一个虚拟头节点
        auto dummy = new ListNode(-1);
        dummy->next = head;
        //先求链表的总长度,每遍历一个点 n++,最后 n 就是链表总长度
        int n = 0;
        for(auto p = dummy;p;p = p->next) n++;

        //从虚拟头节点开始
        auto p = dummy;
        //需要跳 n - k - 1 步
        for(int i = 0;i < n - k - 1;i++ ) p = p->next;
        //删除
        p->next = p->next->next;
        //返回虚拟头节点的下一个位置 也就是真实的头节点
        return dummy->next;
    }
};

有效的括号

算法标签：栈、字符串

 

 

给定一个只包含 '('，')'，'{'，'}'，'['，']'的序列，判断序列是不是合法的

左括号是被动的，右括号是主动的

左括号只能原地等待，右括号可以找离它最近的一个没有被带走的左括号，并且和它要匹配

分析过程可以用栈来模拟

每次遇到一个左括号，把左括号加到栈顶，遇到右括号之后，此时栈顶元素就是离右括号最近的没有被带走的左括号，判断当前的右括号是否与它匹配，如果匹配，就把它带走，如果不匹配就说明不合法

一共有两种不合法的方案

①如果右括号找不到匹配的，就说明不合法

②如果最后剩下一些左括号也是不合法的

数据结构 --- c语言实现栈(数组栈 & 链式栈 & 双端栈 & 括号匹配问题)_小雪菜本菜的博客-CSDN博客

遇到左括号就把它放到栈顶，遇到右括号看栈顶是否与它匹配，如果不匹配就不合法，如果匹配就把栈顶弹出

最后结束的时候判断栈是否为空，如果是空的表示合法，如果不空表示不合法

class Solution {
public:
    bool isValid(string s) {
        //定义一个栈
        stack<char> stk;
        //从前往后枚举所有字符
        for(auto c : s) {
            //如果当前字符是左括号就把它加到栈里面
            if(c == '(' || c == '[' || c == '{') stk.push(c);
            //否则判断是不是匹配
            else {
                /*  左右括号的ASCII码不会离得特别远
                    如果两个括号是一对的话 那么它们之间ASCII码之间的差不会大于2
                */
                //如果栈里面有元素 并且栈顶元素的ASCII码与当前元素的ASCII码如果小于等于2的话说明是匹配的 删除栈顶
                if(stk.size() && abs(stk.top() - c) <= 2) stk.pop();
                //否则说明不匹配
                else return false;
            }
        }
        //如果栈为空表示合法 否则表示不合法
        return stk.empty();
    }
};