LeetCode 刷题2

于由KrMzyc发布

011. 盛最多水的容器

给你 n 个非负整数 a_1，a_2，…，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

提示：

  • $n height.length$
  • $2 <= n <= 10^5$
  • $0 <= height[i] <= 104$

AC Code

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;
    }
};

012. 整数转罗马数字

罗马数字包含以下七种字符：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"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • $1 <= num <= 3999$

AC Code

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<=12; i++)
        {
            while (num>=values[i])
            {
                num-=values[i];
                res+=reps[i];
            }
        }
        return res;
    }
};

013. 罗马数字转整数

罗马数字包含以下七种字符: 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 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3

示例 2:

输入: "IV"
输出: 4

示例 3:

输入: "IX"
输出: 9

示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • $1 <= s.length <= 15$
  • $s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)$
  • 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
  • $IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX $。

AC Code

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;
    }
};

014. 最长公共前缀

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

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

示例 1：

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

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

  • $1 <= strs.length <= 200$
  • $0 <= strs[i].length <= 200$
  • $strs[i] 仅由小写英文字母组成$

AC Code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if (!strs.size()) 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;
    }
};

015.三数之和

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

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

示例 1：

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

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

题意分析

  • 双指针算法

  • $i$ 的移动必须每次为不同的数

AC Code

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++)
        {
            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;
                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;
    }
};

016. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

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

提示：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

题意分析

  • $nums[i]+nums[j]+nums[k]>=target\ 的最小值$
  • $nums[i]+num[j]+nums[k-1]<target\ 的最大值$

AC Code

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        pair<int ,int> res(INT_MAX,INT_MIN);
        sort(nums.begin(), nums.end());
        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 sum=nums[i]+nums[j]+nums[k];
                res=min(res,make_pair(abs(sum-target),sum));
                if (k-1>j)
                {
                    int sum=nums[i]+nums[j]+nums[k-1];
                    res=min(res,make_pair(abs(target-sum),sum));
                }
            }
        }

        return res.second;
    }
};

017. 电话号码的数字组合

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

AC Code

class Solution {
public:

    vector<string> ans;
    string str[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:str[digits[u]-'0'])
                dfs(digits,u+1,path+c);
        }
    }
};

018. 四数之和

给你一个由 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]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

AC Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector <vector<int>> res;
        sort(nums.begin(), nums.end());
        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(k<u-1 && nums[i]+nums[j]+nums[k]+nums[u-1]>=target) u--;
                    if (nums[i]+nums[j]-target==-nums[k]-nums[u])       //防止溢出
                        res.push_back({nums[i],nums[j],nums[k], nums[u]});
                }
            }
        }
        return res;
    }
};

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

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

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

AC Code

/**
 * 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 n) {
        auto dummy=new ListNode(-1);          //创建虚拟头节点
        dummy->next=head;
        int len=0;
        for (auto p=dummy; p!=NULL; p=p->next) len++;
        auto p=dummy;
        for (int i=0; i<len-n-1; i++) p=p->next;
        p->next=p->next->next;

        return dummy->next;
    }
};

020. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

AC Code

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

        for (auto c:s)
        {
            if (c=='(' || c=='{' || c=='[') stk.push(c);
            else
            {
                if (stk.size() && abs(stk.top()-c)<=2) stk.pop();
                else return false;
            }
        }
        return stk.empty();
    }
};
分类： 算法集

0 条评论

发表评论

Avatar placeholder

邮箱地址不会被公开。 必填项已用*标注

相关文章

算法集

线代基础

线性代数基础部分笔记备份。。。 线代基础 4-8

算法集

英语语法

英语备份22-2-25

算法集

高数基础

备份更新：2022-3-15 基础篇补充 2022-3-15 补充