CS Manual

Appearance

构造 ​

构造 ​

118. 杨辉三角 easy ​

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

java
class Solution {
    public List<List<Integer>> generate(int n) {
        List<List<Integer>> res = new ArrayList<>(n);
        res.add(List.of(1));
        for (int i = 1; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            List<Integer> pre = res.get(i - 1);
            for (int j = 1; j < i; j++) {
                int a = pre.get(j - 1);
                int b = pre.get(j);
                list.add(a + b);
            }
            list.add(1);
            res.add(list);
        }
        return res;
    }
}
go
func generate(numRows int) [][]int {
    ans := make([][]int, numRows)
    for i := range ans {
        ans[i] = make([]int, i+1)
        ans[i][0] = 1
        ans[i][i] = 1
        for j := 1; j < i; j++ {
            ans[i][j] = ans[i-1][j] + ans[i-1][j-1]
        }
    }
    return ans
}

667. 优美的排列 II mid ​

给你两个整数 n 和 k，请你构造一个答案列表 answer，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：

  • 假设该列表是 answer=[a1,a2,a3,...,an] ，那么列表 [|a1−a2|,|a2−a3|,|a3−a4|,...,|an−1−an|] 中应该有且仅有 k 个不同整数。

返回列表 answer。如果存在多种答案，只需返回其中 任意一种。

k+1 个数产生 k 个间隔: 1, k+1, 2, k, ...
间隔: k->1
后面的序列保证间隔 1

java
class Solution {
    public int[] constructArray(int n, int k) {
        int[] res = new int[n];
        res[0] = 1;
        int interval = k;
        for (int i = 1; i <= k; i++) {
            res[i] = (i & 1) == 1
                    ? res[i - 1] + interval
                    : res[i - 1] - interval;
            interval--;
        }
        // 1->k+1 占用 [0]->[k]
        for (int i = k + 1; i < n; i++) {
            res[i] = i + 1;
        }
        return res;
    }
}