关于算法:上岸算法-I-LeetCode-Weekly-Contest-216解题报告

No.1 查看两个字符串数组是否相等

解题思路

String.join!!!

代码展现

class Solution {

public boolean arrayStringsAreEqual(String[] word1, String[] word2) {return String.join("", word1).equals(String.join("", word2));
}

}

No.2 具备给定数值的最小字符串

解题思路

贪婪, 每次用的字符越小越好.

代码展现

class Solution {

public String getSmallestString(int n, int k) {StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        int c = 1;
        while ((n - i - 1) * 26 + c < k) c++;
        k -= c;
        sb.append((char) (c - 1 + 'a'));
    }
    return sb.toString();}

}

No.3 生成均衡数组的计划数

解题思路

前缀和稍作改变: 只蕴含原奇数下标的前缀和以及偶数下标的前缀和.

应用这两个前缀和就能够疾速计算出删除一个数字后的新奇偶下标的元素和.

代码展现

class Solution {

public int waysToMakeFair(int[] nums) {// oddSum[i] 示意 i 地位之后的所有原奇数下标元素的和
    // oddSum[0] == oddSum[1], oddSum[2] == oddSum[3]...
    int[] oddSum = new int[nums.length + 1];  // + 1 防止越界
    int[] eveSum = new int[nums.length + 1];
    int n = nums.length;
    oddSum[n - 1] = (n - 1) % 2 == 1 ? nums[n - 1] : 0;
    eveSum[n - 1] = (n - 1) % 2 == 0 ? nums[n - 1] : 0;
    for (int i = n - 2; i >= 0; i--) {oddSum[i] = oddSum[i + 1] + (i % 2 == 1 ? nums[i] : 0);
        eveSum[i] = eveSum[i + 1] + (i % 2 == 0 ? nums[i] : 0);
    }

    int res = 0;
    for (int i = 0; i < n; i++) {int odd = oddSum[0] - oddSum[i] + eveSum[i + 1];
        int eve = eveSum[0] - eveSum[i] + oddSum[i + 1];
        res += odd == eve ? 1 : 0;
    }
    return res;
}

}

No.4 实现所有工作的起码初始能量

解题思路

实际上咱们并不需要关怀真正的程序, 只须要关怀“差值”和最大的启动值就能够了.

tot 示意理论耗费的总能量和.

minDiff 示意启动值和理论消耗的差中的最小值.

maxStart 示意所有工作中, 起始能量最高的.

最终答案是 tot + minDiff 或 maxStart

代码展现

class Solution {

public int minimumEffort(int[][] tasks) {
    int tot = 0, minDiff = 10000, maxStart = 0;
    for (int[] task : tasks) {tot += task[0];
        maxStart = Math.max(maxStart, task[1]);
        minDiff = Math.min(minDiff, task[1] - task[0]);
    }
    return Math.max(maxStart, tot + minDiff);
}

}