【LeetCode刷题】Java随缘更新_leetcode 刷 java

LeetCode刷题

前言：
LeetCode是一个在线编程练习平台，提供了大量的算法题目，可以帮助程序员提高编程能力和解决问题的能力。刷LeetCode的好处包括：

1. 锻炼解决问题的思维能力，提高编程能力。
2. 加深对计算机科学中经典数据结构的深刻理解，从而可以快速用合适的数据结构去解决现实中的问题。
3. 可以锻炼自己的代码风格和规范，提高代码质量。
4. 可以学习到其他程序员的优秀代码，从中汲取灵感和经验。
5. 可以参加LeetCode上的竞赛活动，与其他程序员一较高下。

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

class Solution {
    // 主函数
    public String longestPalindrome(String s) {
        // 记录最长回文串
        String res = "";

        // 穷举以所有点（奇数一个点，偶数两个点）为中心的回文串
        for (int i = 0; i < s.length(); i++) {
            // 当回文串是奇数时，由一个中心点向两边扩散
            String s1 = palindrome(s, i, i);
            // 当回文串是偶数时，由中间的两个中心点向两边扩散
            String s2 = palindrome(s, i, i + 1);

            // 三元运算符：判断为真时取冒号前面的值，为假时取冒号后面的值
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }

        return res;
    }

    // 辅助函数：寻找回文串
    private String palindrome(String s, int left, int right) {
        // 在区间 [0, s.length() - 1] 中寻找回文串，防止下标越界
        while (left >=0 && right < s.length()) {
            // 是回文串时，继续向两边扩散
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        }

        // 循环结束时的条件是 s.charAt(left) != s.charAt(right), 所以正确的区间为 [left + 1, right), 方法 substring(start, end) 区间是 [start, end), 不包含 end
        return s.substring(left + 1, right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

最接近的三数之和

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

返回这三个数的和。

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

示例 1：

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

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

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);
        int closestNum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int l = i + 1, r = nums.length - 1;
            while (l < r){
                int threeSum = nums[l] + nums[r] + nums[i];
                if (Math.abs(threeSum - target) < Math.abs(closestNum - target)) {
                    closestNum = threeSum;
                }
                if (threeSum > target) {
                    r--;
                } else if (threeSum < target) {
                    l++;
                } else {
                    // 如果已经等于target的话, 肯定是最接近的
                    return target;
                }

            }

        }

        return closestNum;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2:

输入：s = “aa”, p = “a*”
输出：true
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3：

输入：s = “ab”, p = “."
输出：true
解释：".” 表示可匹配零个或多个（‘*’）任意字符（‘.’）。

提示：

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

class Solution {
    public boolean isMatch(String s, String p) {
        //dp[i][j] 表示 s 中前 i 个字符是否能由 p 中前 j 个字符匹配
        // 1 s[i - 1] == p[j - 1] 即：当前两个字符相等
        //     考察 s(0, i - 2) ; p(0, j - 2)
        //     dp[i][j] = dp[i - 1][j - 1]
        // 2 p[j - 1] == '.' 即：说明 . 可以匹配 s[i - 1]
        //     dp[i][j] = dp[i - 1][j - 1]
        // 3 s[i - 1] != p[j - 1] 即：当前两个字符不相等
        //    p[j - 1] == '*' (s[i - 1] == p[j - 2] || p[j - 2] == '.')
        //      说明 * 前面的元素与匹配当前 i - 1 元素
        //      让 p[j - 2] 重复 0 次 (删除第 j - 2 个元素)
        //          考察 s(0, i - 1) ; P(0, j - 3)  i 不动, j--
        //          dp[i][j] = dp[i][j - 2]
        //      让 p[j - 2] 重复 1 次 (使用第 j - 2 个元素来 抵消 )
        //          考察 s(0, i - 2) ; p(0, j - 3)  i--. j 左移两位
        //          dp[i][j] = dp[i - 1][j - 3]
        //      让 p[j - 2] 重复 > 1 次 (拿出一个第 j - 2 个元素, 相当于添加一个该元素)
        //          考察 s(0, i - 2) ; p(0, j - 1)  j 不动, i--
        //          dp[i][j] = dp[i - 1][j]
        //
        //    p[j - 1] == '*' (s[i - 1] != p[j - 2])
        //      说明 * 前面的元素 j - 2 与当前 i - 1 元素不相等
        //          让 j 左移一位 (删除第 j - 2 个元素) 
        //          考察 s(0, i - 1) ; p(0, j - 3)
        //          dp[i][j] = dp[i][j - 2]

        int nS = s.length();
        int nP = p.length();
        boolean[][] dp = new boolean[nS + 1][nP + 1];
        //初始化, 空字符串匹配
        dp[0][0] = true;

        //若 s 为空串
        //  p[j - 1] == '*' 说明可以删除掉 p[j - 2]
        //      考察 p(0, j - 3)
        //      dp[0][j] = dp[0][j - 2]
        //  p[j - 1] != '*' 说明 s, p 肯定不匹配
        for (int j = 1; j <= nP; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= nS; i++) {
            for (int j = 1; j <= nP; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }else if (p.charAt(j - 1) == '*') {
                    // * 号前面一个字符 j - 2 匹配当前 i - 1字符, 三种情况
                    if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                        //删除, 考察 s(0, i) ; p(0, j - 3)
                        //抵消, 考察 s(0, i - 1) ; p(0, j - 3)
                        //重复, 考察 s(0, i - 1) ; p(0 , j - 1)
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                    }else {
                        // * 号前面一个字符 j - 2 != 当前 i - 1字符
                        //删除, 考察 s(0, i) ; p(0, j - 3)
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[nS][nP];
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false

提示：

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

class Solution {
    public boolean isValid(String s) {
        Stack<Character>stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

算法题

问题一

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

/**
 * 给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
 *
 * 数据范围：0 \le n \le 1000 , 0 \le k \le 1000≤n≤1000,0≤k≤100，数组中每个元素的值满足 0 \le val \le 1000≤val≤100
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)
 *
 * 输入：
 * [1,2,3,3,3,3,4,5],3
 * 复制
 * 返回值：
 * 4
 *
 * 输入：
 * [1,3,4,5],6
 * 复制
 * 返回值：
 * 0
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解决方案1：暴力算法

 public static int method1(int array[],int target){
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if(array[i] == target){
                count ++;
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9

解决方案2：折半查找

//先找到与target值相同的数组下标index,然后向两边进行遍历
//count的值即为target的个数

public int method2(int [] array , int k) {
        int low=0;
        int high=array.length-1;
        int count=0;
        while(low<=high){
            int mid=low+(high-low)/2;
            if(array[mid]<k){
                low=mid+1;
            }else if(array[mid]>k){
                high=mid-1;
            }else{
                count++;
                int index1=mid-1;
                int index2=mid+1;
                while(index1>=0 && array[index1]==k){
                    count++;
                    index1--;
                }
                while(index2<array.length && array[index2]==k){
                    count++;
                    index2++;
                }
                break;
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

解决方案3：折半查找

//思路：先找到target的起始位置startIndex,再找到target的末位位置endIndex，用末位-起始位置+1得到具体个数
//count = endIndex - startIndex + 1;

//计算个数
 public static int method3(int [] array , int k) {
        return getEndIndex(array,k) - getStartIndex(array,k) + 1;
    }

 /**
     * 获取第一次出现元素的位置
     * @return
     */
    public static int getStartIndex(int array[],int target){
        int startIndex = 0;
        int endIndex = array.length - 1;
        int mid = (startIndex + endIndex)/2;
        while (startIndex < endIndex){
            if(array[mid] < target){
                endIndex = mid - 1;
            }else if(array[mid] > target){
                startIndex = mid + 1;
            }else  if(mid - 1 >=0 && array[mid- 1] == target){
                startIndex--;
            }else return mid;
            mid =( startIndex + endIndex)/2;
        }
        return 0;
    }


    /**
     * 获取最后一次出现元素的位置
     * @return
     */
    public static int getEndIndex(int array[],int target){
        int start = 0;
        int end = array.length - 1;
        int mid = (start + end)/2;
        while (start <= end){
            if(array[mid] < target){
                start = mid + 1;
            }else if(array[mid] >target){
                start = mid + 1;
            }else  if(mid + 1 < array.length && array[mid +1] == target){
                end ++;
            }else return mid;
            mid = (start + end)/2;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50