LeetCode Weekly Contest 172

5315.6と9からなる最大数
数字6と9だけからなる正の整数numをあげます.
最大1桁の数字を反転して、6を9にするか、9を6にするしかありません.
あなたが得られる最大の数字を返してください.
例1:
入力:num=9669出力:9969解釈:最初のビット数を変更すると6669になります.2番目の数字を変更すると9969が得られます.3番目の数字を変えると9699が得られます.4番目の数字を変更すると9666が得られます.このうち最大の数字は9969です.例2:
入力:num=9996出力:9999解釈:最後のビットを6から9に変更し、その結果9999が最大数になります.例3:
入力:num=9999出力:9999解釈:変更する必要がなく最大の数字です.
コード#コード#

class Solution {
     
    public int maximum69Number (int num) {
     
        String snum = String.valueOf(num);
        int slen = snum.length(), i = 0;
        for (i=0; i <slen; ++i) {
     
            if (snum.charAt(i) == '6') {
     
                return Integer.parseInt(snum.substring(0, i) + '9' + snum.substring(i+1));
            }
        }
        return num;
    }
};

5316.単語を垂直に印刷
文字列sをあげます.単語sの出現順にすべて垂直に返してください.単語は文字列リストとして返され、必要に応じてスペースで補完されますが、末尾のスペースを出力するには削除する必要があります(スペースは後続できません).各単語は1列にしか置けず、各列にも1つの単語しか置けません.
例1:
入力:s="HOW ARE YOU"出力:["HAY","ORO","WEU"]解釈:単語ごとに垂直に印刷する必要があります.「HAY」「ORO」「WEU」例2:
入力:s=“TO BE OR NOT TO BE”出力:[“TBONTB”,“OEROOE”,“T”]解釈:題目はスペースを使って位置を補うことを許可して、しかし出力の末尾にスペースが現れることを許可しません.「TBONTB」「OEROOE」「T」の例3:
入力:s="CONTEST IS COMING"出力:["CIC","OSO","N M","T I","E N","S G","T"]
ヒント:
1<=s.length<=200 sは大文字の英字のみを含む.タイトルデータは、2つの単語の間にスペースが1つしかないことを保証します.
コード#コード#

class Solution {
     
    public List<String> printVertically(String s) {
     
        s = s.trim();
        ArrayList<String> ans = new ArrayList<>();
        String[] words = s.split(" ");
        int n = words.length, i = 0, lmax = 0, j = 0;
        for (String word: words) {
     
            lmax = Math.max(lmax, word.length());
        }
        char[] chs = new char[n];
        for (j=0; j<lmax; ++j) {
     
            Arrays.fill(chs, '0');
            for (i=0; i<n; ++i) {
     
                if (j < words[i].length()) {
     
                    chs[i] = words[i].charAt(j);
                } else {
     
                    chs[i] = ' ';
                }
            }
            String tmp = new String(chs);
            tmp = 'a' + tmp;
            tmp = tmp.trim();
            tmp = tmp.substring(1);
            ans.add(tmp);
        }
        return ans;
    }
}

5317.指定した値のリーフノードを削除する
rootをルートとするツリーと整数targetを1本あげます.targetの値を持つすべてのリーフノードを削除してください.
注意:targetの値を持つリーフノードを削除すると、その親ノードがリーフノードになる可能性があります.新しいリーフノードの値がtargetである場合、このノードも削除されるべきです.
つまり、削除を続行できないまでこの手順を繰り返す必要があります.
例1:
入力:root=[1,2,3,2,null,2,4],target=2出力:[1,null,3,null,4]説明:上の左側の図では緑のノードがリーフノードであり、それらの値はtargetと同じ(同じ2)であり、それらは削除され、中間の図が得られる.新しいノードがリーフノードになり、targetと同じ値になったため、再び削除し、右端の図を得る.例2:
入力:root=[1,3,3,2,2]、target=3出力:[1,3,null,null,2]例3:
入力:root=[1,2,null,2,null,2],target=2出力:[1解釈:ステップごとに緑のリーフノードを削除します(値は2).例4:
入力:root=[1,1,1]、target=1出力:[]例5:
入力:root=[1,2,3]、target=1出力:[1,2,3]
ヒント:
1<=target<=1000ツリーあたり最大3000ノード.各ノード値の範囲は[1,1000]である.
構想
再帰.まず左右のサブツリーを処理し,左右のサブツリールートノードに戻り,更新した左右のサブノードから現在のルートノードを削除する必要があるか否かを判断する.
コード#コード#

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     
    public TreeNode removeLeafNodes(TreeNode root, int target) {
     
        if (root == null) {
     
            return null;
        }
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);
        if (root.left == null && root.right == null) {
     
            return root.val == target? null: root;
        }
        return root;
    }
}

5318.灌
x軸に1次元のガーデンがあります.ガーデンの長さはnで、点0から始まり、点nで終わります.
花園には全部でn+1個の蛇口があり、それぞれ[0,1,...,n]に位置している.
整数nと長さn+1の整数配列rangesを与え、ranges[i](以下0から始まる)は、点iの蛇口を開けると灌
庭全体を灌庭に灌
例1:
入力:n=5,ranges=[3,4,1,1,0]出力:1解釈:点0の蛇口が灌漑可能区間[-3,3]点1の蛇口が灌漑可能区間[-3,5]点2の蛇口が灌漑可能区間[1,3]点3の蛇口が灌漑可能区間[2,4]点4の蛇口が灌漑可能区間[4,4]点5の蛇口が灌漑可能区間[5,5]1箇所の蛇口を開けるだけでガーデン全体を灌漑できる[0,5].例2:
入力:n=3,ranges=[0,0,0]出力:-1説明:すべての蛇口を開けても、庭全体を灌例3:
入力:n=7,ranges=[1,2,1,0,2,1,0,1]出力:3例4:
入力:n=8,ranges=[4,0,0,0,0,0,0,0,4]出力:2例5:
入力:n=8,ranges=[4,0,0,0,4,0,0,0,4]出力:1
ヒント:
1 <= n <= 10^4 ranges.length == n + 1 0 <= ranges[i] <= 100
構想
区間オーバーライドの問題.2つの変数curLenおよびcurIdxは、それぞれ、現在選択されている選択区間の集合の最も右端が覆われている位置と、現在選択されている線分のIdを表す.curIdx区間において右端の最も右端の線分を探すIdは、新しいcurLenとして、この線分の右端の位置を新しいtmpIdxとする.このように区間が完全に覆うまで循環し、記録に用いた線分の個数が戻る.注意(curIdx, tmpIdx]の二分検索の書き方は、主にcurIdxサイクル条件curLenと戻り値rightmostNoLargerThanに注目する.
コード#コード#

class Solution {
     
    private class Line implements Comparable<Line> {
     
        public int left, right;
        
        public Line(int left, int right) {
     
            this.left = left;
            this.right = right;
        }
        
        @Override
        public int compareTo(Line other) {
     
            return left - other.left;
        }
    }
    
    private int rightmostNoLargerThan(Line[] lines, int beginIdx, int bound) {
     
        int n = lines.length, l = Math.max(beginIdx, 0), r = n-1, m = 0;
        while (l <= r) {
     
            m = (l + r) / 2;
            if (lines[m].left <= bound) {
     
                l = m + 1;
            } else {
     
                r = m - 1;
            }
        }
        return r;
    }
    
    public int minTaps(int n, int[] ranges) {
     
        Line[] lines = new Line[n+1];
        int i = 0;
        for (i=0; i<=n; ++i) {
     
            lines[i] = new Line(i - ranges[i], i + ranges[i]);
        }
        Arrays.sort(lines);
        int curLen = 0, curIdx = -1, cnt = 0, preLen = 0;
        while (curLen < n) {
     
            int tmpIdx = rightmostNoLargerThan(lines, curIdx, curLen);
            preLen = curLen;
            for (i=curIdx + 1; i<=tmpIdx; ++i) {
     
                if (lines[i].right > curLen) {
     
                    curLen = lines[i].right;
                    curIdx = tmpIdx;
                }
            }
            if (preLen == curLen) {
     
                return -1;
            }
            ++cnt;
        }
        return cnt;
    }
}