6.23号刷题

第一题 592. Fraction Addition and Subtraction

题目描述

求分数加减法算式的值，结果化为最简分数。

注意：

1. 输入字符串只包含0~9，+-/。输出亦然
2. 每个分数之前包含±号，若第一个分数为正数，省去+
3. 输入只包含有效的最简分数，分子分母范围[1, 10]。若分母为1，表示该分数实际上是一个整数。
4. 分数的个数范围[1, 10]
5. 分子分母的结果在32位带符号整数范围之内

算法

a1/b1 + a2/b2 = (a1*b2 + a2 * b1) / (b1 * b2)

根据这个公式进行计算，注意这里约分的方法，这个递归的求最大公约数的方法很好。

public class Solution {
    public String fractionAddition(String expression) {
        String[] fraces = expression.split("(?=[-, +])");
        String res = "0/1";
        for (String frac : fraces) res = add(res, frac);
        return res;
    }

    public String add(String frac1, String frac2) {
        int[] f1 = Stream.of(frac1.split("/")).mapToInt(Integer::parseInt).toArray(),
                f2 = Stream.of(frac2.split("/")).mapToInt(Integer::parseInt).toArray();
        int number = f1[0] * f2[1] + f1[1] * f2[0], demon = f1[1] * f2[1];
        String sign = "";
        if (number < 0) {sign = "-"; number *= -1;}
        return sign + number/gcd(number, demon) + "/" + demon/gcd(number, demon);
    }

    public static int gcd(int x, int y) {
        return x == 0 || y == 0 ? x + y : gcd(y, x % y);
    }
}

第二题 171. Excel Sheet Column Number

题目描述

相关题目：Excel 表格列标题

给定一个出现在Excel表格中的列标题，返回其对应的列号。

样例如题目描述。

算法

可以看错一个26进制的问题，比较简单

public class titleToNumber171 {
    public int titleToNumber(String s) {
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            result = result * 26 + (s.charAt(i) - 'A') + 1;
        }
        return result;
    }
}

第三题 168. Excel Sheet Column Title

题目描述

给定一个正整数，返回其在Excel表格中对应的列标题。

样例如上。

算法

与之前相似，都是26进制转换问题

public class Solution {
    public String convertToTitle(int n) {
        if (n < 1) return "";
        int now = n, remain = 0;
        String res = "";
        while (now != 0) {
            remain = now % 26;
            if (remain == 0) remain = 26;
            char c = (char) ('A' + remain - 1);
            res = c + res;
            if (now % 26 == 0) now = (now - 26) / 26;
            else now = (now - now % 26) / 26;
        }
        return res;    
    }
}

第四题 12. Integer to Roman

题目描述

将Integer 类型转为罗马数字

算法

public class intToRoman12 {
    public String intToRoman(int num) {
        int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(strs[i]);
            }
        }
        
        return sb.toString();
    }
}

第五题 13. Roman to Integer

题目描述

将罗马数字转换成Integer

算法

public class romanToInt13 {
    public int romanToInt(String s) {
        int[] nums = new int[s.length()];

        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'M':
                    nums[i]=1000;
                    break;
                case 'D':
                    nums[i]=500;
                    break;
                case 'C':
                    nums[i]=100;
                    break;
                case 'L':
                    nums[i]=50;
                    break;
                case 'X' :
                    nums[i]=10;
                    break;
                case 'V':
                    nums[i]=5;
                    break;
                case 'I':
                    nums[i]=1;
                    break;
            }
        }

        int sum = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] < nums[i + 1]) {
                sum -= nums[i];
            } else {
                sum += nums[i];
            }
        }

        return sum + nums[nums.length - 1];
    }
}

第六题 360. Sort Transformed Array

题目描述

利用式子y = a x^2 + b x + c将给定数组中的所有数计算一遍答案，然后按照顺序排好。要求时间复杂度O(n)

算法

如果a > 0开口向上，两边大中间小

如果a < 0,开口向下，两边小中间大

利用双向指针，完成整个排序

public class sortTransformedArray360 {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] res = new int[nums.length];
        if (nums.length < 3) return res;
        int left = 0, right = nums.length - 1;
        int i = a > 0 ? nums.length - 1 : 0;
        while (left <= right) {
            int numLeft = calculate(nums[left], a, b, c);
            int numRight = calculate(nums[right], a, b, c);
            if (a > 0) {
                if (numLeft > numRight) {
                    res[i--] = numLeft;
                    left++;
                }
                else {
                    res[i--] = numRight;
                    right--;
                }
            }

            else {
                if (numLeft > numRight) {
                    res[i++] = numRight;
                    right--;
                }
                else {
                    res[i++] = numLeft;
                    left++;
                }
            }
        }
        return res;
    }

    public int calculate(int num, int a, int b, int c) {
        return a * num * num + b * num + c;
    }
}

第七题 423. Reconstruct Original Digits from English

题目描述

给定一个非空字符串，包含一组乱序的英文字母表示的数字0-9，按递增序输出这些数字。

注意：

1. 输入只包含小写英文字母
2. 输入确保是有效的，并且一定可以转换为其原始数字。这意味着不会出现”abc”, “zerone”之类的非法输入
3. 输入长度小于50000

算法

zero: Only digit with z
two: Only digit with w
four: Only digit with u
six: Only digit with x
eight: Only digit with g

通过统计，最后计算出结果

public class Solution {
    public String originalDigits(String s) {
    int[] count = new int[10];
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (c == 'z') count[0]++;
        if (c == 'w') count[2]++;
        if (c == 'x') count[6]++;
        if (c == 's') count[7]++; //7-6
        if (c == 'g') count[8]++;
        if (c == 'u') count[4]++; 
        if (c == 'f') count[5]++; //5-4
        if (c == 'h') count[3]++; //3-8
        if (c == 'i') count[9]++; //9-8-5-6
        if (c == 'o') count[1]++; //1-0-2-4
    }
    count[7] -= count[6];
    count[5] -= count[4];
    count[3] -= count[8];
    count[9] = count[9] - count[8] - count[5] - count[6];
    count[1] = count[1] - count[0] - count[2] - count[4];
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i <= 9; i++){
        for (int j = 0; j < count[i]; j++){
            sb.append(i);
        }
    }
    return sb.toString();        
    }
}

第八题 319. Bulb Switcher

题目描述

有n盏初始处于关闭状态的灯泡。你首先打开所有的灯泡。然后，熄灭所有序号为2的倍数的灯泡。第三轮，切换所有序号为3的倍数的灯泡（开着的就关掉，关着的就打开）。第n轮，你只切换最后一只灯泡。计算n轮之后还有几盏灯泡亮着。

测试用例见题目描述。

算法

对于第i栈灯泡，当i的因子个数为奇数时，最终会是点亮状态，例如9的因子为1，3，9
而当i的因子个数为偶数时，最终会保持熄灭状态，例如8的因子为：1，2，4，8
当且仅当i为完全平方数时，其因子个数为奇数

public class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

第九题 415. Add Strings

题目描述

给定两个以字符串表示的非负整数num1, num2，返回num1与num2的和。

注意：

1. num1和num2的长度< 5100
2. num1和num2只包含数字0-9
3. num1和num2不包含前导0

你不能使用内置的BigInteger库，也不能直接把输入转换为整数。

算法

对应每一位相加，并标记进位符

public class Solution {
    public String addStrings(String num1, String num2) {
        int flag = 0, pointNum1 = num1.length() - 1, pointNum2 = num2.length() - 1;
        StringBuilder sb = new StringBuilder();

        while (pointNum1 >= 0 || pointNum2 >= 0 || flag == 1) {
            int x = pointNum1 < 0 ? 0 : num1.charAt(pointNum1--) - '0';
            int y = pointNum2 < 0 ? 0 : num2.charAt(pointNum2--) - '0';
            sb.append((x + y + flag) % 10);
            flag = (x + y + flag) / 10;
        }
        return sb.reverse().toString();        
    }
}