头像

mxyzptlk13


访客:10845

离线:4天前


活动打卡代码 LeetCode 14. 最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String common = strs[0];
        int n = strs.length;

        for (int i = 1; i < n; i++) {
            common = get(common, strs[i]);
        }

        return common;
    }

    public String get(String a, String b) {
        int n = a.length(), m = b.length();
        String common = "";
        for (int i = 0; i < Math.min(n, m); i++) {
            if (a.charAt(i) == b.charAt(i)) {
                common += Character.toString(a.charAt(i));
            }
            else break;
        }

        return common;
    }
}



class Solution {
    List<String> ro = Arrays.asList(new String[]{"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"});
    int[] intNumber = new int[]{1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
    public int romanToInt(String s) {
        if (s.length() == 0) return 0;
        int res = 0;
        int index = -1;

        if (s.length() > 1) {
            index = idx(s.substring(0, 2));
            if (index != -1) {
                res += intNumber[index];
                return res + romanToInt(s.substring(2));
            }
        }

        index = idx(Character.toString(s.charAt(0)));
        res += intNumber[index];
        return res + romanToInt(s.substring(1));
    }

    int idx(String s) {
        for (int i = 0; i < 13; i++) {
            if (ro.get(i).equals(s)) return i;
        }

        return -1;
    }
}



class Solution {
    public String intToRoman(int num) {
        String res = "";
        int th = num / 1000;
        if (th > 0){
            for (int i = 0; i < th; i++) res += "M";
            return res + intToRoman(num - th * 1000);
        }

        int hun = num / 100;
        if (hun == 9) return "CM" + intToRoman(num - 900);

        if (hun >= 5) return "D" + intToRoman(num - 500);

        if (hun == 4) return "CD" + intToRoman(num - 400);

        if (hun > 0) {
            for (int i = 0; i < hun; i++) res += "C";
            return res + intToRoman(num - hun * 100);
        }

        int ten = num / 10;
        if (ten == 9) return "XC" + intToRoman(num - 90);
        if (ten >= 5) return "L" + intToRoman(num - 50);
        if (ten == 4) return "XL" + intToRoman(num - 40);

        if (ten > 0) {
            for (int i = 0; i < ten; i++) res += "X";
            return res + intToRoman(num - ten * 10);
        }

        int one = num;

        if (one == 9) return "IX";
        if (one >= 5) return "V" + intToRoman(num - 5);
        if (one == 4) return "IV";

        for (int i = 0; i < one; i++) {
            res += "I";
        }

        return res;
    }

}



class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0, r = n - 1;
        int res = 0;
        while (l < r) {
            int temp = (r - l) * Math.min(height[l], height[r]);
            res = Math.max(res, temp);
            if (height[l] < height[r]) l++;
            else r--;
        }

        return res;
    }
}



class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        s = " " + s;
        p = " " + p;

        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;

        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j + 1 <= m && p.charAt(j + 1) == '*') continue;
                if (p.charAt(j) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                        if (i - 1 >= 0) dp[i][j] |= dp[i - 1][j];
                    }
                }
                else {
                    if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                        if (i - 1 >= 0) dp[i][j] = dp[i - 1][j - 1];
                    }
                    else dp[i][j] = false;
                }
            }
        }
        return dp[n][m];
    }
}


活动打卡代码 LeetCode 9. 回文数

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) return false;

        StringBuilder sb = new StringBuilder(Integer.toString(x));
        String a = sb.toString();
        sb.reverse();

        String b = sb.toString();

        return a.equals(b);
    }
}



class Solution {
    public int myAtoi(String str) {
        long res = 0;
        boolean pre = true;

        int neg = 1;

        int n = str.length();

        char[] chars = str.toCharArray();
        for (int i = 0; i < n; i++) {
            if (!pre && !(chars[i] >= '0' && chars[i] <= '9')) break;
            if (pre && chars[i] == ' ') continue;
            if (pre && chars[i] == '-') {
                neg = -1;
                pre = false;
                continue;
            }
            if (pre && chars[i] == '+') {
                pre = false;
                continue;
            }

            if (pre && !(chars[i] >= '0' && chars[i] <= '9')) break;
            pre = false;
            res = res * 10 + (chars[i] - '0');
            res = Math.min(1l << 32, res);

        }

        res *= neg;

        if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;

        return (int) res;
    }
}


活动打卡代码 LeetCode 7. 整数反转

mxyzptlk13
1个月前
class Solution {
    public int reverse(int x) {
        boolean neg = x < 0;
        String s = Integer.toString(x);

        if (neg) s = s.substring(1);

        StringBuilder sb = new StringBuilder(s);

        sb.reverse();

        s = sb.toString();

        long res = Long.parseLong(s);

        if (neg) res = -res;

        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) return 0;

        return (int) res;
    }
}


活动打卡代码 LeetCode 6. Z 字形变换

mxyzptlk13
1个月前
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        String res = "";
        int k = 2 * numRows - 2;
        int n = s.length();

        for (int i = 0; i < n; i += k) {
            res += Character.toString(s.charAt(i));
        }

        for (int i = 1; i < numRows - 1; i++) {
            for (int j = 0; i + j * k < n; j++) {
                int a = i;
                int b = k - i;

                a += j * k;
                b += j * k;

                if (a < n) res += Character.toString(s.charAt(a));
                if (b < n) res += Character.toString(s.charAt(b));
            }
        }

        for (int i = numRows - 1; i < n; i += k) {
            res += Character.toString(s.charAt(i));
        }

        return res;
    }
}



mxyzptlk13
1个月前
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int l = 0, n = s.length();
        char[] arr = s.toCharArray();

        int res = 0;

        for (int r = 0; r < n; r++) {
            int count = map.getOrDefault(arr[r], 0);
            map.put(arr[r], count + 1);
            while (map.get(arr[r]) > 1) {
                map.put(arr[l], map.get(arr[l]) - 1);
                l++;
            }

            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}