Java每日一练(20230416) 三数之和、基本计算器、通配符匹配-阿里云开发者社区

Java每日一练(20230416) 三数之和、基本计算器、通配符匹配

2024-01-30 38

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Java每日一练(20230416) 三数之和、基本计算器、通配符匹配

1. 三数之和

给你一个包含 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

出处：

https://edu.csdn.net/practice/25743533

代码：

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
public class threeSum {
    public static class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>();
            int cur, left, right;
            cur = 0;
            while (cur < nums.length) {
                if (nums[cur] > 0)
                    break;
                left = cur + 1;
                right = nums.length - 1;
                while (left < right) {
                    int n = nums[cur] + nums[left] + nums[right];
                    if (n == 0) {
                        List<Integer> r = new ArrayList<Integer>();
                        r.add(nums[cur]);
                        r.add(nums[left]);
                        r.add(nums[right]);
                        result.add(r);
                        int t = left + 1;
                        while (t < right && nums[t] == nums[left])
                            t++;
                        left = t;
                        t = right - 1;
                        while (t > left && nums[t] == nums[right])
                            t--;
                        right = t;
                    } else if (n > 0) {
                        int t = right - 1;
                        while (t > left && nums[t] == nums[right])
                            t--;
                        right = t;
                    } else {
                        int t = left + 1;
                        while (t < right && nums[t] == nums[left])
                            t++;
                        left = t;
                    }
                }
                int t = cur + 1;
                while (t < nums.length && nums[t] == nums[cur])
                    t++;
                cur = t;
            }
            return result;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(s.threeSum(nums));
    }
}

输出：

[[-1, -1, 2], [-1, 0, 1]]

2. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：

输入：s = "1 + 1"

输出：2

示例 2：

输入：s = " 2-1 + 2 "

输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"

输出：23

提示：

1 <= s.length <= 3 * 10^5
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式

出处：

https://edu.csdn.net/practice/25743534

代码：

import java.util.*;
public class calculate {
    public static class Solution {
        public double calculate(String s) {
            List<Character> list = new ArrayList<>();
            for(int i = 0; i < s.length(); i++)
                list.add(s.charAt(i));
            return helper(list);
        }
        public double helper(List<Character> s){
            Stack<Double> stack = new Stack<>();
            char sign = '+';
            double num = 0, res = 0;
            while(s.size() > 0)
            {
                char c = s.remove(0);
                if (Character.isDigit(c))
                {
                    num = 10 * num + (c - '0');  //包含大于等于10的数字
                }
                if (c == '(')
                    num = helper(s);
                if ((!Character.isDigit(c) && c != ' ') || s.size() == 0)
                {
                    if (sign == '+')
                        stack.push(num);
                    else if (sign == '-')
                        stack.push(-num);
                    else if (sign == '*')
                    {
                        stack.push(stack.pop() * num);
                    }
                    else if (sign == '/')
                    {
                        stack.push(stack.pop() / num);
                    }
                    sign = c;
                    num = 0;
                }
                if (c == ')')
                {
                    break;
                }
            }
            while (!stack.isEmpty()){
                res += stack.pop();
            }
            return res;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String cal = "(1+(4+5+2)-3)+(6+8)";
        System.out.println(s.calculate(cal));
    }
}

输出：

23.0

3. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

输入:s = "aa"p = "a"

输出: false

解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa"p = "*"

输出: true

解释: '*' 可以匹配任意字符串。

示例 3:

输入:s = "cb"p = "?a"

输出: false

解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:s = "adceb"p = "*a*b"

输出: true

解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:s = "acdcb"p = "a*c?b"

输出: false

以下程序实现了这一功能，请你填补空白处内容：

···Java
class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] value = new boolean[p.length() + 1][s.length() + 1];
        value[0][0] = true;
        for (int i = 1; i <= s.length(); i++) {
            value[0][i] = false;
        }
        for (int i = 1; i <= p.length(); i++) {
            if (p.charAt(i - 1) == '*') {
                value[i][0] = value[i - 1][0];
                for (int j = 1; j <= s.length(); j++) {
                    value[i][j] = (value[i][j - 1] || value[i - 1][j]);
                }
            } else if (p.charAt(i - 1) == '?') {
                value[i][0] = false;
                for (int j = 1; j <= s.length(); j++) {
                    value[i][j] = value[i - 1][j - 1];
                }
            } else {
                value[i][0] = false;
                for (int j = 1; j <= s.length(); j++) {
                    ____________________;
                }
            }
        }
        return value[p.length()][s.length()];
    }
}
···

出处：

https://edu.csdn.net/practice/25743536

代码：

import java.util.*;
public class calculate {
    public static class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] value = new boolean[p.length() + 1][s.length() + 1];
        value[0][0] = true;
        for (int i = 1; i <= s.length(); i++) {
            value[0][i] = false;
        }
        for (int i = 1; i <= p.length(); i++) {
            if (p.charAt(i - 1) == '*') {
                value[i][0] = value[i - 1][0];
                for (int j = 1; j <= s.length(); j++) {
                    value[i][j] = (value[i][j - 1] || value[i - 1][j]);
                }
            } else if (p.charAt(i - 1) == '?') {
                value[i][0] = false;
                for (int j = 1; j <= s.length(); j++) {
                    value[i][j] = value[i - 1][j - 1];
                }
            } else {
                value[i][0] = false;
                for (int j = 1; j <= s.length(); j++) {
                    value[i][j] = s.charAt(j - 1) == p.charAt(i - 1) && value[i - 1][j - 1];
                }
            }
        }
        return value[p.length()][s.length()];
    }
}
    public static void main(String[] args) {
        Solution sol = new Solution();
        String s = "adceb", p = "*a*b";
        System.out.println(sol.isMatch(s, p));
    }
}