11. 盛最多水的容器
- 11.1 思路
- 11.2 代码
12. 整数转罗马数字
- 12.1 思路
- 12.2 代码
13. 罗马数字转整数
- 13.1 思路
- 13.2 代码
14. 最长公共前缀
- 14.1 思路
- 14.2 代码
15. 三数之和
- 15. 1 思路
- 15.2 代码
16. 最接近的三数之和。
- 16.1 思路
- 16.2 代码
17.电话号码的字母组合
- 17.1 思路
- 17.2 代码
18.四数之和。
- 18.1 思路
- 18.2 代码
19. 删除链表的倒数第N的节点。
- 19.1 思路
- 19.2 代码
20 有效的括号
- 20.1 思路
- 20.2 代码

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

11.1 思路

可以用单调栈或者单调队列来做，但是麻烦，
直接来吧。双指针一个指向左边，一个指向最右边。
哪边的高度比较短就把哪边的指针往中间走。
每次都算一下面积。

why？因为有一个指针先到最优解的边界，另外一个指针也一定会走到。。
就好像左指针已经在最优解的边界上了，右边那个指针指向的高度一定是小于左边那个指针的高度的。

11.2 代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        for (int i = 0, j = height.size() - 1; i < j; )
        {
            res = max(res, 
                min(height[i], height[j]) * (j - i));
            if (height[i] > height[j]) j -- ;
            else i ++ ;
        }
        return res;
    }
};

12. 整数转罗马数字

模拟题，找规律的题
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。

示例 1:

输入: num = 3
输出: “III”

12.1 思路

减去基准值，加上对应的字母。直到变成0为止。

要是找不到规律，就直接暴力写，千位百位十位的对应。

12.2 代码

class Solution {
public:
    string intToRoman(int num) {
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string reps[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        string res;
        // 从大到小依次减去。
        for (int i = 0; i < 13; i ++ )
            while(num >= values[i])
            {
                num -= values[i];
                res += reps[i];
            }
        return res;
    }
};

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

13.1 思路

除了4 9 那就是都是加起来就行。
字母要是比下面那一个字母小，就减，不然就加。、、

13.2 代码

class Solution {
public:
    int romanToInt(string s) {
        // 字母映射成数字、
        unordered_map<char, int> hash;
        hash['I'] = 1, hash['V'] = 5;
        hash['X'] = 10, hash['L'] = 50;
        hash['C'] = 100, hash['D'] = 500;
        hash['M'] = 1000;

        int res = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            // 后面有字符 并且当前字符小于后面的字符，就要减去。
            if (i + 1 < s.size() && hash[s[i]] < hash[s[i + 1]])
                res -= hash[s[i]];
            else
                res += hash[s[i]];
        }

        return res;
    }
};

ctrl + f 查找。
ctrl + h 替换。

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

14.1 思路

枚举题目，逐个判断。
时间复杂度起码是所有字符串长度之和。

首先看看第一个字符，然后看第二个字符，反正就是不断地试探~直到不全一样了。
一重循环枚举位置上的字符，二重循环枚举所有的字符串。

【用二分不如不用二分，加了一个log的时间复杂度。】如果找的是不连续的子序列，那么久只能找两个的，
并且只能用dp。

14.2 代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        // 初始为空，直接返回就可以。
        if (strs.empty()) return res;

        for (int i = 0;; i ++ ) {
            // 直接没有
            if (i >= strs[0].size()) return res;
            char c = strs[0][i];
            // 枚举所有的字符串上的对应位置的字符是否相等。
            for (auto& str: strs)
                if (str.size() <= i || str[i] != c)
                    return res;
            res += c;
        }

        return res;
    }
};

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 1 2 3 和 2 3 1是重复的。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

15. 1 思路

最优秀的：双指针。—-》有序。能降低一个数量级

先枚举第一个位置，后面两个用双指针。
i < j < k:。
j k 是时间复杂度 n^2
i 是时间复杂度 n。 ===》总时间复杂度n^ 2

i 固定之后

去重：nums[i] 和上面一个元素相同的就跳过。

i 和 j 都要去重。k不用了，因为k 是由i j 决定的。如果有多个k

哈希表，但是空间复杂度比较高。

15.2 代码

class Solution {
public:
 vector<vector<int>> threeSum(vector<int>& nums) {
     vector<vector<int>> res;
     sort(nums.begin(), nums.end());

     for (int i = 0; i < nums.size(); i ++ ) {
         // i > 0 并且 i位置的元素 和 他上面那个元素相同，就直接跳过去重。
         if (i && nums[i] == nums[i - 1]) continue;
         for (int j = i + 1, k = nums.size() - 1; j < k; j ++ ) {
             // 去重。
             if (j > i + 1 && nums[j] == nums[j - 1]) continue;

             // 没有重叠。因为这里找到的k就是相同数值的最左边的k
             while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k -- ;

             if (nums[i] + nums[j] + nums[k] == 0) {
                 res.push_back({nums[i], nums[j], nums[k]});
             }
         }
     }

     return res;
 }
};

16. 最接近的三数之和。

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

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

16.1 思路

这个思路可以直接借鉴上面的~。大于等于target的最小数或者小于等于target的最大数。
保证答案只有一个，不用去充。

三重for循环。
双指针，先枚举i，然后双指针j k。

固定i，枚举j，找一个最小的k 让 numsi + numsj + numsk 大于等于k。
k-1 就是小于target

16.2 代码

class Solution {
    public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        // 存一个差值，存一个和。
        pair<int, int> res(INT_MAX, INT_MAX);
        for (int i = 0; i < nums.size(); i ++ )
            for (int j = i + 1, k = nums.size() - 1; j < k; j ++ ) {
                while (k - 1 > j && nums[i] + nums[j] + nums[k - 1] >= target) k -- ;

                int s = nums[i] + nums[j] + nums[k];
                // 不一定能找到k 让三数之和大于target
                res = min(res, make_pair(abs(s - target), s));
                if (k - 1 > j) {
                    s = nums[i] + nums[j] + nums[k - 1];
                    // 这里一定是小于target的。
                    res = min(res, make_pair(target - s, s));
                }
            }
        return res.second;
    }
};

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

17.1 思路

经典的dfs问题，画一个递归树。

递归的时候，要存方案：path，要存当前第几位，index。

时间复杂度：和长度有关，最坏每种情况有4中选择，4的n次方。得到一种方案需要n的时间复杂度，一共有4的n次方种选择。

全排列的模板题：递归实现排列型枚举。

path变得话，就需要恢复现场。

17.2 代码

class Solution {
public:
    vector<string> ans;
    string strs[10] = {
        "", "", "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);
        }
    }
};

18.四数之和。

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

18.1 思路

双指针优化可以降低一个数量级的时间复杂度。
如果要求变了的话，用哈希表不是很容易做。先枚举两个变量，然后双指针指向两个变量。
去重也是碰到和前面的数相同，就跳过。

如果是n个数的话，就要用动态规划了，是一个背包问题。

18.2 代码

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 ++ ) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                for (int k = j + 1, u = nums.size() - 1; k < u; k ++ ) {
                    if (k > j + 1 && nums[k] == nums[k - 1]) continue;
                    while (u - 1 > k && nums[i] + nums[j] + nums[k] + nums[u - 1] >= target) u -- ;

                    if (nums[i] + nums[j] + nums[k] + nums[u] == target) {
                        res.push_back({nums[i], nums[j], nums[k], nums[u]});
                    }
                }
            }
        }

        return res;
    }
};

19. 删除链表的倒数第N的节点。

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

19.1 思路

虚拟头结点，
核心是找到要被删除的节点的上一个节点。

快慢指针也是可以的，总长度是一样的。

19.2 代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int k) {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        int n = 0;
        for (auto p = dummy; p; p = p->next) n ++ ;

        auto p = dummy;
        for (int i = 0; i < n - k - 1; i ++ ) p = p->next;
        p->next = p->next->next;

        return dummy->next;
    }
};

20 有效的括号

20.1 思路

经典的题目，用栈。
男生找一个离他最近的对上眼缘的妹子。
不合法的情况：剩下妹子或者男生找不到有眼缘的妹子。

可以考dfs dp 卡特兰数等等。

20.2 代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;

        for (auto c : s) {
            if (c == '(' || c == '[' || c == '{') stk.push(c);
            else {
                // 左右括号的ascii码相差不会大于2.
                if (stk.size() && abs(stk.top() - c) <= 2) stk.pop();
                else return false;
            }
        }

        return stk.empty();
    }
};

算法

Week2 11~20

11. 盛最多水的容器

11.1 思路

11.2 代码

12. 整数转罗马数字

12.1 思路

12.2 代码

13. 罗马数字转整数

13.1 思路

13.2 代码

14. 最长公共前缀

14.1 思路

14.2 代码

15. 三数之和

15. 1 思路

15.2 代码

16. 最接近的三数之和。

16.1 思路

16.2 代码

17.电话号码的字母组合

17.1 思路

17.2 代码

18.四数之和。

18.1 思路

18.2 代码

19. 删除链表的倒数第N的节点。

19.1 思路

19.2 代码

20 有效的括号

20.1 思路

20.2 代码