golang 解法, 执行用时: 124 ms, 内存消耗: 39.1 MB, 提交时间: 2023-07-04 09:47:03

func sandyLandManagement(n int) [][]int {
    ans := [][]int{}
    for i := 1; i < n; i++ {
        for j := 1; j <= i * 2 - 1; j += 4 {
            ans = append(ans, []int{i, j})
        }
    }
    ans = append(ans, []int{n, 1})
    
    if n > 1 {
        ans = append(ans, []int{n, n * 2 - 1})
    }
    
    for i := 4; i < n * 2 - 1; i += 8 {
        ans = append(ans, []int{n, i})
    }
    
    for i := 7; i < n * 2 - 1; i += 8 {
        ans = append(ans, []int{n, i})
    }
    
    for i := 9; i < n * 2 - 1; i += 8 {
        ans = append(ans, []int{n, i})
    }
    
    return ans
}

python3 解法, 执行用时: 132 ms, 内存消耗: 53.6 MB, 提交时间: 2023-07-04 09:41:39

# 按规律构造
def gen(tp: int, num: int):
    if num == 1:
        yield [1, 1]
    elif tp == 0:
        for j in range(1, num * 2, 2):
            yield [num, j]
    elif tp == 1:
        yield [num, 2]
    elif tp == 2:
        for j in range(3, num * 2, 2):
            yield [num, j]
    elif tp == 3:
        yield [num, 1]

class Solution:
    def sandyLandManagement(self, N: int) -> List[List[int]]:
        return list(chain.from_iterable(gen((N - num) & 3, num) for num in range(1, N + 1)))

python3 解法, 执行用时: 136 ms, 内存消耗: 56.9 MB, 提交时间: 2023-07-04 09:41:09

# 按规律构造
book = [[],
    [[1,1]],
    [[1,1],[2,1],[2,3]],
    [[1,1],[2,1],[3,1],[3,3],[3,5]],
    [[1,1],[2,3],[3,2],[4,1],[4,3],[4,5],[4,7]]
]

class Solution:
    def sandyLandManagement(self, size: int) -> List[List[int]]:
        if size <= 4: return deepcopy(book[size])
        res = self.sandyLandManagement(size - 4)
        for i in range(size): res.append([size, i * 2 + 1])
        res.append([size - 1, 2])
        for i in range(1, size - 2): res.append([size - 2, i * 2 + 1])
        res.append([size - 3, 1])
        return res

javascript 解法, 执行用时: 380 ms, 内存消耗: 89.8 MB, 提交时间: 2023-07-04 09:40:13

/**
 * @param {number} size
 * @return {number[][]}
 */
var sandyLandManagement = function(size) {
    if(size<4){  //size=1-3,直接返回
        return [[[1,1]],[[1,1],[2,1],[2,3]],[[1,1],[2,1],[2,3],[3,1],[3,5]]][size-1]
    }
    let res = [[1,1]]
    for(let i = 2;i<=size;i++){
        let y = (size-i)%4  //根据规律选择添加方式
        if(y===0){
            for(let j = 1;j<2*i;j+=2){
                res.push([i,j])
            }
        }else if(y===1){
            res.push([i,2])
        }else if(y===2){
            for(let j = 3;j<2*i;j+=2){
                res.push([i,j])
            }
        }else if(y===3){
            res.push([i,1])
        }
    }
    return res
};

python3 解法, 执行用时: 148 ms, 内存消耗: 52.6 MB, 提交时间: 2023-07-04 09:39:27

class Solution:
    def sandyLandManagement(self, size: int) -> List[List[int]]:
        ans = []
        for i in range(1, size):
            for j in range(1, i * 2, 4):
                ans.append([i, j])
            
        ans.append([size, 1])
        if size > 1:
            ans.append([size, size * 2 - 1]);
        for i in range(4, size * 2 - 1, 8):
            ans.append([size, i]);
        for i in range(7, size * 2 - 1, 8):
            ans.append([size, i])
        for i in range(9, size * 2 - 1, 8):
            ans.append([size, i])
        return ans

cpp 解法, 执行用时: 104 ms, 内存消耗: 52 MB, 提交时间: 2023-07-04 09:30:51

/**
 * 找规律，标记(n^2+3*n+2)/4个三角形
 **/
class Solution {
public:
    vector<vector<int>> sandyLandManagement(int n) {
        vector<vector<int>> ans;
        for (int i = 1; i < n; i++) for (int j = 1; j <= i * 2 - 1; j += 4) ans.push_back({i, j});
        ans.push_back({n, 1});
        if (n > 1) ans.push_back({n, n * 2 - 1});
        for (int i = 4; i < n * 2 - 1; i += 8) ans.push_back({n, i});
        for (int i = 7; i < n * 2 - 1; i += 8) ans.push_back({n, i});
        for (int i = 9; i < n * 2 - 1; i += 8) ans.push_back({n, i});
        return ans;
    }
};