LeetCode-6

忙啊，最近真忙啊，算法难度也进入到基础了，基本上全都是中等了，越来越难了。

495 提莫攻击

刷题时间：2021-11-10

借用网友的话。祖玛我唯唯诺诺，提莫我重拳出击。

class Solution {
   public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int sum = 0;
        for (int i = 1; i < timeSeries.size(); i++) {
            if (timeSeries[i] - timeSeries[i - 1] < duration) {
                sum += timeSeries[i] - timeSeries[i - 1];
            } else {
                sum += duration;
            }
        }
        return sum + duration;
    }
};

82 删除排序链表中的重复元素 II

刷题时间：2021-11-10

class Solution {
   public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* prev = new ListNode(-1, head);
        ListNode* node = prev;

        while (head) {
            if (head->next && head->next->val == head->val) {
                while (head->next && head->next->val == head->val) {
                    head = head->next;
                }
                head = head->next;
                node->next = head;
                continue;
            }
            node = head;
            head = head->next;
        }
        return prev->next;
    }
};

15 三数之和

刷题时间：2021-11-10

时隔多年，这道题还是不会，把我搞抽象了，只能说非常的难，中间的条件比两数之和还难一点，因为有重复的

class Solution {
   public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> v;
        int n = nums.size();
        if (n < 3 || nums.back() < 0 || nums.front() > 0) return {};

        // k为target的负数
        for (int k = 0; k < n - 2; k++) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = n - 1;
            int target = -nums[k];
            while (i < j) {
                if (nums[j] < 0) break;

                if (nums[i] + nums[j] == target) {
                    v.push_back({nums[k], nums[i], nums[j]});
                    while (i < j && nums[i] == nums[i + 1]) ++i;
                    while (i < j && nums[j] == nums[j - 1]) --j;
                    ++i;
                    --j;
                } else if (nums[i] + nums[j] < target)
                    ++i;
                else
                    --j;
            }
        }
        return v;
    }
};

844 比较含退格的字符串

刷题时间：2021-11-11

非常的难受啊，双指针没写出来，实属丢了芝麻赔了西瓜，先来个正常思维的版本。

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }

    string build(string str) {
        string ret;
        for (char ch : str) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
};

我的双指针思路很像官解，但是思路不清晰，有点乱，各种条件还缺一点，导致乱了阵法，没做出来，唉。

class Solution {
   public:
    bool backspaceCompare(string s, string t) {
        int ps = s.size() - 1;
        int pt = t.size() - 1;
        int cs = 0, ct = 0;
        while (ps >= 0 || pt >= 0) {
            while (ps >= 0) {
                if (s[ps] == '#') {
                    cs++;
                    ps--;
                } else if (cs > 0) {
                    cs--;
                    ps--;
                } else {
                    break;
                }
            }
            while (pt >= 0) {
                if (t[pt] == '#') {
                    ct++;
                    pt--;
                } else if (ct > 0) {
                    ct--;
                    pt--;
                } else {
                    break;
                }
            }

            if (ps >= 0 && pt >= 0) {
                if (s[ps] != t[pt]) {
                    return false;
                }
            } else if (ps >= 0 || pt >= 0) {
                return false;
            }
            ps--;
            pt--;
        }
        return true;
    }
};

986 区间列表的交集

表现还不错，击败七八十的用户。

class Solution {
   public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                             vector<vector<int>>& secondList) {
        int m = firstList.size(), n = secondList.size();

        vector<vector<int>> res;
        int num = 0;
        for (int i = 0; i < m; i++) {
            for (int j = num; j < n; j++) {
                // cout<<i<<" "<<j<<" "<<num<<endl;
                if (secondList[j][0] > firstList[i][1]) {
                    num = j - 1 > 0 ? j - 1 : 0;
                    break;
                }
                if (firstList[i][0] > secondList[j][1]) {
                    num = j + 1;
                    continue;
                }
                res.push_back({max(firstList[i][0], secondList[j][0]),
                               min(firstList[i][1], secondList[j][1])});
            }
        }
        return res;
    }
};

官解更简单，还是官解香啊。

class Solution {
   public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                             vector<vector<int>>& secondList) {
        int m = firstList.size(), n = secondList.size();

        vector<vector<int>> res;
        int i = 0, j = 0;
        while (i < m && j < n) {
            int lo = max(firstList[i][0], secondList[j][0]);
            int hi = min(firstList[i][1], secondList[j][1]);
            if (lo <= hi) {
                res.push_back({lo, hi});
            }
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return res;
    }
};

11 盛最多水的容器

双指针法，感觉也有点一般般吧

class Solution {
   public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int res = 0;
        int sum = 0;
        while (i < j) {
            sum = (j - i) * min(height[i], height[j]);
            if (sum > res) res = sum;
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return res;
    }
};

374 猜数字大小

刷题时间：2021-11-12

哥哥题目做不出来，做弟弟题目，就二分查找

class Solution {
   public:
    int guessNumber(int n) {
        int l = 1, r = n;
        while (l < r) {
            int m = l+(r-l) / 2;
            if (guess(m) == 0) {
                return m;
            }
            if (guess(m) < 0) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};

375 猜数字大小 II

刷题时间：2021-11-12

干，这题太难了，二维的动态规划，太难了。

class Solution {
   public:
    int getMoneyAmount(int n) {
        vector<vector<int>> f(n + 1, vector<int>(n + 1));
        for (int i = n - 1; i >= 1; i--) {
            for (int j = i + 1; j <= n; j++) {
                int minCost = INT_MAX;
                for (int k = i; k < j; k++) {
                    int cost = k + max(f[i][k - 1], f[k + 1][j]);
                    minCost = min(minCost, cost);
                }
                f[i][j] = minCost;
            }
        }
        return f[1][n];
    }
};

438 找到字符串中所有字母异位词

滑动窗口，只不过不能用数组，需要用vector才能判断两个是否相同。

class Solution {
   public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.length(), n = p.length();
        vector<int> res;
        if (m < n) return res;
        vector<int> a(26, 0);
        for (char ch : p) {
            a[ch - 'a']++;
        }
        vector<int> b(26, 0);
        for (int i = 0; i < n - 1; i++) {
            b[s[i] - 'a']++;
        }
        for (int i = 0; i < m - n + 1; i++) {
            b[s[i + n - 1] - 'a']++;
            if (b == a) {
                res.push_back(i);
            }
            b[s[i] - 'a']--;
        }
        return res;
    }
};

js版本，注意数组不能直接判断，得变成toString()

var findAnagrams = function (s, p) {
    const m = s.length,
        n = p.length;
    const res = [];
    if (m < n) {
        return res;
    }
    const arrp = new Array(26).fill(0);
    for (let ch of p) {
        arrp[ch.charCodeAt() - 'a'.charCodeAt()]++;
    }

    const arrs = new Array(26).fill(0);
    for (let i = 0; i < n - 1; i++) {
        arrs[s[i].charCodeAt() - 'a'.charCodeAt()]++;
    }
    for (let i = n - 1; i < m; i++) {
        arrs[s[i].charCodeAt() - 'a'.charCodeAt()]++;
        if (arrs.toString() == arrp.toString()) res.push(i - n + 1);
        arrs[s[i - n + 1].charCodeAt() - 'a'.charCodeAt()]--;
    }
    return res;
};

713 乘积小于K的子数组

刷题时间：2021-11-12

滑动窗口，没写出来，尿了。过于难了这道题，cnt = i -l +1这什么天才想法。

class Solution {
   public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int l = 0, n = nums.size();
        int sum = 1;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            sum *= nums[i];
            while (sum >= k) {
                sum /= nums[l];
                l++;
            }
            cnt += i - l + 1;
        }
        return cnt;
    }
};

209 长度最小的子数组

滑动窗口，反正就这个意思吧。

class Solution {
   public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l = 0, n = nums.size();
        int sum = 0;
        int cnt = INT_MAX;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            while (sum >= target) {
                if (cnt > i - l + 1) {
                    cnt = i - l + 1;
                }
                sum -= nums[l];
                l++;
            }
        }
        if (cnt == INT_MAX) return 0;
        return cnt;
    }
};

js版本

var minSubArrayLen = function (target, nums) {
    let l = 0,
        n = nums.length;
    let sum = 0;
    let cnt = Infinity;
    for (let i = 0; i < n; i++) {
        sum += nums[i];
        while (sum >= target) {
            if (cnt > i - l + 1) {
                cnt = i - l + 1;
            }
            sum -= nums[l];
            l++;
        }
    }
    if (cnt == Infinity) return 0;
    return cnt;
};

520 检测大写字母

刷题时间：2021-11-13

准备回归go和js，不用C++了，js作为主力吧。

var detectCapitalUse = function(word) {
    // 若第 1 个字母为小写，则需额外判断第 2 个字母是否为小写
    if (word.length >= 2 && word[0] === word[0].toLowerCase() && word[1] === word[1].toUpperCase()) {
        return false;
    }
    
    // 无论第 1 个字母是否大写，其他字母必须与第 2 个字母的大小写相同
    for (let i = 2; i < word.length; ++i) {
        if (word[i] === word[i].toLowerCase() ^ word[1] === word[1].toLowerCase()) {
            return false;
        }
    }
    return true;
};

200 岛屿数量

刷题时间：2021-11-13

和岛屿最大的面积那题差不多，就是小改一下，下面这个是深度优先的算法

const a = [1, 0, -1, 0];
const b = [0, 1, 0, -1];
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let cnt = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                cnt++;
                dfs(grid, i, j);
            }
        }
    }
    return cnt;
};
function dfs(grid, i, j) {
    grid[i][j] = '0';
    for (let m = 0; m < 4; m++) {
        const mx = i + a[m],
            my = j + b[m];
        while (mx >= 0 && mx < grid.length && my >= 0 && my < grid[0].length && grid[mx][my] == '1') {
            dfs(grid, mx, my);
        }
    }
}

网上扒拉了一个用go写的dfs，真尼玛简单

func numIslands(grid [][]byte) int {
	var num int
	var dfs func(int, int)
	dfs = func(i, j int) {
		if i >= len(grid) || i < 0 {
			return
		}
		if j >= len(grid[0]) || j < 0 {
			return
		}
		if grid[i][j] == '1' {
			grid[i][j] = '0'
			dfs(i+1, j)
			dfs(i, j+1)
			dfs(i-1, j)
			dfs(i, j-1)
		}
	}

	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				dfs(i, j)
				num++
			}
		}
	}
	return num
}

自己用go写了广度优先的，go没有原生的队列，用切片就行了

func numIslands(grid [][]byte) int {
	a := []int{1, 0, -1, 0}
	b := []int{0, 1, 0, -1}
	que := make([]int, 0)
	cnt := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				cnt++
				que = append(que, i, j)
				grid[i][j] = '0'
				for len(que) != 0 {
					tmp_i, tmp_j := que[0], que[1]
					que = que[2:]
					for m := 0; m < 4; m++ {
						mx := tmp_i + a[m]
						my := tmp_j + b[m]
						if mx >= 0 && mx < len(grid) && my >= 0 && my < len(grid[0]) && grid[mx][my] == '1' {
							grid[mx][my] = '0'
							que = append(que, mx, my)
						}
					}
				}
			}
		}
	}
	return cnt
}

还有个并查集的方法，之后再看

547 省份数量

用go写的dfs，也算是抄的吧，一开始觉得邻接矩阵有个公式，没想到还是要dfs

func findCircleNum(isConnected [][]int) int {
	vis := make([]bool, len(isConnected))
	var dfs func(i int)
	dfs = func(i int) {
		vis[i] = true
		for to, conn := range isConnected[i] {
			if conn == 1 && !vis[to] {
				dfs(to)
			}
		}
	}
	cnt := 0
	for i, v := range vis {
		if !v {
			cnt++
			dfs(i)
		}
	}
	return cnt
}

js写的bfs

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
    const visited = new Set();
    const queue = new Array();
    const len = isConnected.length;
    let cnt = 0;
    for (let i = 0; i < len; i++) {
        if (!visited.has(i)) {
            queue.push(i);
            cnt++;
            while (queue.length) {
                const j = queue.shift();
                visited.add(j);
                for (let k = 0; k < len; k++) {
                    if (isConnected[j][k] === 1 && !visited.has(k)) {
                        queue.push(k);
                    }
                }
            }
        }
    }
    return cnt;
};

贴个并查集的go，只使用了路径压缩，没有用到按秩合并

什么是并查集呢？https://zhuanlan.zhihu.com/p/93647900/

func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	// 查找，找到根节点
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	// 合并，找到两个的根节点，然后把其中一个设为另一个的父节点
	union := func(from, to int) {
		parent[find(from)] = find(to)
	}

	for i, row := range isConnected {
		for j := i + 1; j < n; j++ {
			if row[j] == 1 {
				union(i, j)
			}
		}
	}
	for i, p := range parent {
		if i == p {
			ans++
		}
	}
	return
}

677 键值映射

不会写这种类的，直接cv js版本的暴力法

/*
 * @Author: szx
 * @Date: 2021-11-14 12:37:55
 * @LastEditTime: 2021-11-14 12:40:46
 * @Description:
 * @FilePath: \leetcode\600-699\677\677.js
 */
var MapSum = function () {
    this.map = new Map();
};

/**
 * @param {string} key
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function (key, val) {
    this.map.set(key, val);
};

/**
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function (prefix) {
    let res = 0;
    for (const s of this.map.keys()) {
        if (s.startsWith(prefix)) {
            res += this.map.get(s);
        }
    }
    return res;
};

/**
 * Your MapSum object will be instantiated and called as such:
 * var obj = new MapSum()
 * obj.insert(key,val)
 * var param_2 = obj.sum(prefix)
 */

法二是再用一个哈希表来存所有的前缀，算是我能想到的极限了

var MapSum = function() {
    this.map = new Map();
    this.prefixmap = new Map();

};

MapSum.prototype.insert = function(key, val) {
    const delta = val - (this.map.get(key) || 0);
    this.map.set(key, val);
    for (let i = 1; i <= key.length; ++i) {
        const currprefix = key.substring(0, i);
        this.prefixmap.set(currprefix, (this.prefixmap.get(currprefix) || 0) + delta);
    }
};

MapSum.prototype.sum = function(prefix) {
    return this.prefixmap.get(prefix) || 0;
};

看一下go的版本，给我肯定写不出来

type MapSum struct {
    m, pre map[string]int
}

func Constructor() MapSum {
    return MapSum{map[string]int{}, map[string]int{}}
}

func (m *MapSum) Insert(key string, val int) {
    delta := val
    if m.m[key] > 0 {
        delta -= m.m[key]
    }
    m.m[key] = val
    for i := range key {
        m.pre[key[:i+1]] += delta
    }
}

func (m *MapSum) Sum(prefix string) int {
    return m.pre[prefix]
}

字典树的js做法，charCodeAt返回Unicode编码

class TrieNode {
    constructor() {
        this.val = 0;
        this.next = new Array(26).fill(0);
    }
}

var MapSum = function() {
    this.root = new TrieNode();
    this.map = new Map();

};

MapSum.prototype.insert = function(key, val) {
    const delta = val - (this.map.get(key) || 0);
    this.map.set(key, val);
    let node = this.root;
    for (const c of key) {
        if (node.next[c.charCodeAt() - 'a'.charCodeAt()] === 0) {
            node.next[c.charCodeAt() - 'a'.charCodeAt()] = new TrieNode();
        }
        node = node.next[c.charCodeAt() - 'a'.charCodeAt()];
        node.val += delta;
    }
};

MapSum.prototype.sum = function(prefix) {
    let node = this.root;
    for (const c of prefix) {
        if (node.next[c.charCodeAt() - 'a'.charCodeAt()] === 0) {
            return 0;
        }
        node = node.next[c.charCodeAt() - 'a'.charCodeAt()];
    }
    return node.val;
};

117 填充每个节点的下一个右侧节点指针 II

迭代法，应该是只有这个想法能够想到

var connect = function(root) {
    if (root === null) {
        return null;
    }
    const queue = [root];
    while (queue.length) {
        const n = queue.length;
        let last = null;
        for (let i = 1; i <= n; ++i) {
            let f = queue.shift();
            if (f.left !== null) {
                queue.push(f.left);
            }
            if (f.right !== null) {
                queue.push(f.right);
            }
            if (i !== 1) {
                last.next = f;
            }
            last = f;
        }
    }
    return root;
};

golang版本的，这里用了两个数组，因为切片只能用下标来访问，这样子删除下标就会有问题。

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    q := []*Node{root}
    for len(q) > 0 {
        tmp := q
        q = nil
        for i, node := range tmp {
            if i+1 < len(tmp) {
                node.Next = tmp[i+1]
            }
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
    }
    return root
}

常数空间

一旦在某层的节点之间建立了next指针，那这层节点实际上形成了一个链表。因此，如果先去建立某一层的next指针，再去遍历这一层，就无需再使用队列了。

let last = null, nextStart = null;
const handle = (p) => {
    if (last !== null) {
        last.next = p;
    } 
    if (nextStart === null) {
        nextStart = p;
    }
    last = p;
}
var connect = function(root) {
    if (root === null) {
        return null;
    }
    let start = root;
    while (start != null) {
        last = null;
        nextStart = null;
        for (let p = start; p !== null; p = p.next) {
            if (p.left !== null) {
                handle(p.left);
            }
            if (p.right !== null) {
                handle(p.right);
            }
        }
        start = nextStart;
    }
    return root;
};

572 另一棵树的子树

就按照题意来，虽然我也没写出来就是了，最近没写出来的题目真多，过于依赖题解了

var isSubtree = function (root, subRoot) {
    if (root == null) {
        return false;
    }
    return check(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

var check = function (root, subRoot) {
    if (!root && !subRoot) {
        return true;
    }
    if ((root && !subRoot) || (!root && subRoot) || root.val != subRoot.val) {
        return false;
    }
    return check(root.left, subRoot.left) && check(root.right, subRoot.right);
};

还有两个神仙题解，过于牛逼了，这居然是简单题

319 灯泡开关

刷题时间：2021-11-15

这道题目离谱了，居然这么找规律，算了。暴力法我也写不出来。

var bulbSwitch = function(n) {
    return Math.floor(Math.sqrt(n + 0.5));
};

797 所有可能的路径

经典回溯题目，可惜我做不出来，还需要加强回溯的思想啊

var allPathsSourceTarget = function (graph) {
    const res = [];
    const stack = [];
    const n = graph.length - 1;
    const dfs = (graph, x) => {
        if (x === n) {
            res.push(stack.slice());
            return;
        }
        for (const y of graph[x]) {
            stack.push(y);
            dfs(graph, y);
            stack.pop();
        }
    };
    stack.push(0);
    dfs(graph, 0);
    return res;
};

130 被围绕的区域

刷题时间：2021-11-15

直接dfs

var solve = function (board) {
    const m = board.length;
    const n = board[0].length;
    const dfs = function (board, x, y) {
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    };

    for (let i = 0; i < m; i++) {
        dfs(board, i, 0);
        dfs(board, i, n - 1);
    }

    for (let i = 0; i < n; i++) {
        dfs(board, 0, i);
        dfs(board, m - 1, i);
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] == 'A') board[i][j] = 'O';
            else if (board[i][j] == 'O') board[i][j] = 'X';
        }
    }
};

78 子集

刷题时间：2021-11-16

这道题还是比较简单的，但我还是做不出来，反正就是基本的回溯

var subsets = function (nums) {
    const res = [];
    const len = nums.length;
    const backtrack = (path, index) => {
        if (path.length > len) return;
        res.push(Array.from(path));
        for (let i = index; i < len; i++) {
            path.push(nums[i]);
            backtrack(path, i+1);
            path.pop();
        }
    };
    backtrack([], 0);
    return res;
};

再来个枚举所有的方法，这个快一点

var subsets = function(nums) {
    const ans = [];
    const n = nums.length;
    for (let mask = 0; mask < (1 << n); ++mask) {
        const t = [];
        for (let i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                t.push(nums[i]);
            }
        }
        ans.push(t);
    }
    return ans;
};

再来个go的写法

func subsets(nums []int) [][]int {
	n := len(nums)
	res := [][]int{}
	for i := 0; i < (1 << n); i++ {
		t := []int{}
		for j := 0; j < len(nums); j++ {
			if i&(1<<j) > 0 {
				t = append(t, nums[j])
			}
		}
		res = append(res, t)
	}
	return res
}

90 子集 II

有点绕，果然有个去重的题目，唉，又是排序然后检查有没有和前面相同。

var subsetsWithDup = function (nums) {
    nums.sort((a, b) => a - b);
    const len = nums.length;

    const vis = new Array(len).fill(false);
    const res = [];

    const backtrack = (path, index) => {
        if (path.length > len) return;
        res.push(Array.from(path));
        for (let i = index; i < len; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && vis[i - 1] == false) continue;
            path.push(nums[i]);
            vis[i] = true;
            backtrack(path, i + 1);
            path.pop();
            vis[i] = false;
        }
    };
    backtrack([], 0);
    return res;
};

那个迭代枚举的直接抄官解的go版本了。

func subsetsWithDup(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
outer:
    for mask := 0; mask < 1<<n; mask++ {
        t := []int{}
        for i, v := range nums {
            if mask>>i&1 > 0 {
                // 并且上一个没有选中
                if i > 0 && mask>>(i-1)&1 == 0 && v == nums[i-1] {
                    continue outer
                }
                t = append(t, v)
            }
        }
        ans = append(ans, append([]int(nil), t...))
    }
    return
}