LeetCode-5

Keep going, up up.

268 丢失的数字

刷题时间：2021-11-06

只想到排序法

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for(int i =0;i<nums.size();i++){
            if(nums[i]!=i){
                return i;
            }
        }
        return nums.size();
    }
};

还有个哈希，没写了，直接粘贴了

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> set;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            set.insert(nums[i]);
        }
        int missing = -1;
        for (int i = 0; i <= n; i++) {
            if (!set.count(i)) {
                missing = i;
                break;
            }
        }
        return missing;
    }
};

还有个位运算，因为相同的数字异或是0，最后留下来的只能是缺少的那个。很妙的方法。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            res ^= nums[i];
        }
        for (int i = 0; i <= n; i++) {
            res ^= i;
        }
        return res;
    }
};

数学这个我怎么没想到呢，求和。然后再算一下应该有的求和公式，两个相减就是差值，唉，这我没想到。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }
};

102 二叉树的层序遍历

简单，但我还是贴官方的，比我空间少一点。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }

        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;
    }
};

js版本

var levelOrder = function (root) {
    const res = [];
    if (!root) return res;
    const que = [];
    que.push(root);
    while (que.length) {
        const length = que.length;
        const arr = [];
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            arr.push(tmp.val);
            if (tmp.left) que.push(tmp.left);
            if (tmp.right) que.push(tmp.right);
        }
        res.push(arr);
    }
    return res;
};

104 二叉树的最大深度

我记得这个方法最简单了，果然直接写出来了，不过只打败了30%的人。

class Solution {
   public:
    int maxDepth(TreeNode *root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

层序遍历法，确实快一点。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = 0;
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz > 0) {
                TreeNode* node = Q.front();Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        } 
        return ans;
    }
};

js版本

var maxDepth = function (root) {
    if (!root) return 0;
    const que = [];
    que.push(root);
    let deep = 0;
    while (que.length) {
        const length = que.length;
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            if (tmp.left) que.push(tmp.left);
            if (tmp.right) que.push(tmp.right);
        }
        deep++;
    }
    return deep;
};

101 对称二叉树

没写出来，简单题还是，直接抄了

class Solution {
   public:
    bool isSymmetric(TreeNode *root) { return check(root, root); }
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) &&
               check(p->right, q->left);
    }
};

js版本

var isSymmetric = function (root) {
    const check = (left, right) => {
        if (left == null && right == null) return true;
        else if ((left == null && right != null) || (left != null && right == null)) return false;
        else if (left.val != right.val) return false;
        return check(left.left, right.right) && check(left.right, right.left);
    };
    return check(root.left, root.right);
};

迭代法

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

70 爬楼梯

最简单的动态规划，但是我用了O(n)的空间

class Solution {
   public:
    int climbStairs(int n) {
        int* dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
};

尿了，官方只用常数的空间

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

198 打家劫舍

又是O(N)的空间，我再优化优化

class Solution {
   public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return max(dp[n], dp[n - 1]);
    }
};

好了，这样子就行了

class Solution {
   public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int q = 0, p = 0, r = nums[0];

        for (int i = 2; i <= n; i++) {
            q = p;
            p = r;
            r = max(p, q + nums[i-1]);
        }
        return max(r, p);
    }
};

120 三角形最小路径和

动态规划，空间拉了一点

class Solution {
   public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp{triangle[0]};

        for (int i = 1; i < triangle.size(); i++) {
            int n = triangle[i].size();
            vector<int> tmp(n);
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    tmp[j] = dp[j] + triangle[i][j];
                } else if (j == n - 1) {
                    tmp[j] = dp[j - 1] + triangle[i][j];
                } else {
                    tmp[j] =
                        min(dp[j - 1] + triangle[i][j], dp[j] + triangle[i][j]);
                }
            }
            dp = tmp;
        }
        int res = INT_MAX;
        for (int i : dp) {
            if (i < res) {
                res = i;
            }
        }
        return res;
    }
};

稍微修改一下，直接dp直接取最后一行的数组大小，然后遍历的时候倒着遍历，这样子到最后一个的时候才会覆盖上一个j

class Solution {
   public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle[triangle.size() - 1].size());
        dp[0] = triangle[0][0];

        for (int i = 1; i < triangle.size(); i++) {
            int n = triangle[i].size();
            for (int j = n - 1; j >= 0; j--) {
                if (j == 0) {
                    dp[j] = dp[j] + triangle[i][j];
                } else if (j == n - 1) {
                    dp[j] = dp[j - 1] + triangle[i][j];
                } else {
                    dp[j] = triangle[i][j] + min(dp[j - 1], dp[j]);
                }
            }
        }
        int res = INT_MAX;
        for (int i : dp) {
            if (i < res) {
                res = i;
            }
        }
        return res;
    }
};

还以为自己很厉害了，没想到还有一个反向日神仙的做法

从底部向上，真的牛啊，这才是真大神。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.back());
        for(int i = triangle.size() - 2; i >= 0; i --)
            for(int j = 0; j <= i; j ++)
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
        return dp[0];
    }
};

598 范围求和 II

刷题时间：2021-11-07

简单的很

class Solution {
   public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        int a = m, b = n;
        for (auto &row : ops) {
            a = min(row[0], a);
            b = min(row[1], b);
        }
        return a * b;
    }
};

226 翻转二叉树

简简单单dfs

class Solution {
   public:
    TreeNode *invertTree(TreeNode *root) {
        if (!root) return root;
        TreeNode *tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

js版本

var invertTree = function (root) {
    if (!root) return root;
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

112 路径总和

日日日日，这个简单题的递归没有想出来，尿了尿了，直接看反而很简单呢。干

class Solution {
   public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }
        return hasPathSum(root->left, sum - root->val) ||
               hasPathSum(root->right, sum - root->val);
    }
};

队列的什么的就不写了，毕竟递归都想不出来。

191 位1的个数

题目输入的还是十进制，不过给的是测试用例是二进制罢了，循环检查就行了

class Solution {
   public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if (n & (1 << i)) {
                ret++;
            }
        }
        return ret;
    }
};

优化法，这个还变慢了，实属不行。

n &= n – 1;其运算结果恰为把 n的二进制位中的最低位的 1 变为 0 之后的结果。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

299 猜数字游戏

刷题日期：2021-11-08

简单，一次就过，时间直接拉满，空间率还拉了点。

class Solution {
   public:
    string getHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        unordered_map<int, int> m;
        int n = secret.length();
        for (int i = 0; i < n; i++) {
            if (secret[i] == guess[i]) {
                bulls++;
                guess[i] = 'a';
            } else {
                m[secret[i]]++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (guess[i] != 'a' && m[guess[i]] > 0) {
                cows++;
                m[guess[i]]--;
            }
        }
        return to_string(bulls) + 'A' + to_string(cows) + 'B';
    }
};

干，官方的更聪明，分别统计各个字符的出现次数，然后取最小值就行了，尿了。

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0;
        vector<int> cntS(10), cntG(10);
        for (int i = 0; i < secret.length(); ++i) {
            if (secret[i] == guess[i]) {
                ++bulls;
            } else {
                ++cntS[secret[i] - '0'];
                ++cntG[guess[i] - '0'];
            }
        }
        int cows = 0;
        for (int i = 0; i < 10; ++i) {
            cows += min(cntS[i], cntG[i]);
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

190 颠倒二进制位

位运算的简单题，但由于我不会位运算，所以有点蛋疼，这里的n>0有更好，没有也没什么大影响。

class Solution {
   public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t rev = 0;
        for (int i = 0; i < 32 && n > 0; i++) {
            rev |= (n & 1) << (31 - i);
            n >>= 1;
        }
        return rev;
    }
};

这个分治很有东西，对调奇偶位，无限循环下去，可惜我弄不成功。

class Solution {
private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111

public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};

700 二叉搜索树中的搜索

递归， 简单

class Solution {
   public:
    TreeNode *searchBST(TreeNode *root, int val) {
        if (root) {
            if (root->val == val)
                return root;
            else if (root->val > val)
                return searchBST(root->left,val);
            else
                return searchBST(root->right,val);
        }
        return nullptr;
    }
};

迭代这个也简单

class Solution {
   public:
    TreeNode *searchBST(TreeNode *root, int val) {
        while (root && root->val != val) {
            root = val < root->val ? root->left : root->right;
        }
        return root;
    }
};

js版本

var searchBST = function(root, val) {
    while (root && root.val != val) {
        root = val < root.val ? root.left : root.right;
    }
    return root;
};

701 二叉搜索树中的插入操作

非常一般的操作，应该还能优化优化，但官方也只有一个解法，算了就。

class Solution {
   public:
    TreeNode *insertIntoBST(TreeNode *root, int val) {
        TreeNode *node = root;
        TreeNode *prev = node;
        while (node) {
            prev = node;
            node = val < node->val ? node->left : node->right;
        }
        node = new TreeNode(val);
        if (prev) {
            if (val < prev->val) {
                prev->left = node;
            } else {
                prev->right = node;
            }
        } else {
            return node;
        }
        return root;
    }
};

js版本

var insertIntoBST = function (root, val) {
    let node = root;
    let prev = node;
    while (node) {
        prev = node;
        node = val < node.val ? node.left : node.right;
    }
    node = new TreeNode(val);
    if (prev) {
        if (val < prev.val) {
            prev.left = node;
        } else {
            prev.right = node;
        }
    } else {
        return node;
    }
    return root;
};

34 在排序数组中查找元素的第一个和最后一个位置

无脑O(n)先写一遍

class Solution {
   public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = -1, end = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                if (start == -1) {
                    start = i;
                }
                end = i;
            }
        }
        return {start, end};
    }
};

然后自己写了一个二分搜索。

class Solution {
   public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = -1, end = -1;
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (r == 0) {
            return {-1, -1};
        }
        for (int i = l - 1; i >= 0; i--) {
            if (nums[i] == target) {
                if (end == -1) {
                    end = i;
                }
                start = i;
            } else {
                break;
            }
        }
        return {start, end};
    }
};

33 搜索旋转排序数组

比较的麻烦，需要注意各种不等号吧，尿了

class Solution {
   public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) {
                if (nums[mid] < nums[l] && target >= nums[l]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] >= nums[l] && target < nums[l]) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
        }
        if (r == 0 || nums[l - 1] != target) return -1;
        return l - 1;
    }
};

74 搜索二维矩阵

写错了一下，看了解析才知道有个字母写错了，应该是matrix[mid / n][mid % n]而不是matrix[mid / m][mid % n]

此方法是一次二分查找，如果数组长度不一致的话，这种方法会失效。

class Solution {
   public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int all = m * n;
        int l = 0, r = all;
        while (l < r) {
            int mid = (l + r) / 2;
            if (matrix[mid / n][mid % n] == target) {
                return true;
            }
            if (matrix[mid / n][mid % n] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }
};

再来一个二次二分查找的，C++版本的就不写了，来个go语言的，妙哇哇

func searchMatrix(matrix [][]int, target int) bool {
    row := sort.Search(len(matrix), func(i int) bool { return matrix[i][0] > target }) - 1
    if row < 0 {
        return false
    }
    col := sort.SearchInts(matrix[row], target)
    return col < len(matrix[row]) && matrix[row][col] == target
}

98 验证二叉搜索树

刷题时间：2021-11-09

直接尿了，不能直接比较根元素和左右节点的大小，而是比较最大值或者最小者和左右节点的关系，因为是搜索树是整个子树的关系。反正我写的是错误的，来个官方的递归、

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

还有个是中序遍历，二叉搜索树的中序遍历是肯定递增的，所以只用判断是不是比之前的那个数小就行了。

class Solution {
   public:
    long long pre = LLONG_MIN;

    bool isValidBST(TreeNode *root) {
        if (!root) return true;

        if (!isValidBST(root->left)) return false;

        if (root->val <= pre) return false;
        pre = root->val;

        if (!isValidBST(root->right)) return false;

        return true;
    }
};

js遍历

var isValidBST = function (root) {
    const dfs = (root, min, max) => {
        if (!root) return true;
        if (root.val <= min || root.val >= max) return false;
        return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
    };
    return dfs(root, -Infinity, Infinity);
};

中序遍历，必须要把变量放到函数里面，不然通不过leetcode提交

var isValidBST = function (root) {
    let pre = -Infinity;
    const dfs = (root) => {
        if (!root) return true;
        if (!dfs(root.left)) return false;
        if (pre >= root.val) return false;
        pre = root.val;
        if (!dfs(root.right)) return false;
        return true;
    };
    return dfs(root);
};

653 两数之和 IV-输入 BST

就利用BST的性质，利用中序遍历把他变成vec，然后就是两数之和了。

class Solution {
   public:
    bool findTarget(TreeNode *root, int k) {
        vector<int> vec;
        zhongxu(root, vec);
        for (int i : vec) {
            cout << i << " ";
        }
        cout << endl;
        int l = 0, r = vec.size()-1;
        int sum = 0;
        while (l < r) {
            sum = vec[l] + vec[r];
            if (sum == k) {
                return true;
            }
            if (sum > k)
                r--;
            else
                l++;
        }
        return false;
    }
    void zhongxu(TreeNode *root, vector<int>& vec) {
        if (!root) return;
        zhongxu(root->left, vec);
        vec.push_back(root->val);
        zhongxu(root->right, vec);
    }
};

235 二叉搜索树的最近公共祖先

就是这样子的，喵。

不过这题是简单题是不是有点过分了啊。

class Solution {
   public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        if (root->val >= p->val && root->val <= q->val || root->val <= p->val && root->val >= q->val) {
            return root;

        } else if (root->val >= p->val && root->val >= q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (root->val <= p->val && root->val <= q->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        return nullptr;
    }
};

再来个迭代的，迭代的更简单，尿了。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ancestor = root;
        while (true) {
            if (p->val < ancestor->val && q->val < ancestor->val) {
                ancestor = ancestor->left;
            }
            else if (p->val > ancestor->val && q->val > ancestor->val) {
                ancestor = ancestor->right;
            }
            else {
                break;
            }
        }
        return ancestor;
    }
};

js版本的递归

var lowestCommonAncestor = function (root, p, q) {
    if (!root) return null;
    if ((root.val <= p.val && root.val >= q.val) || (root.val >= p.val && root.val <= q.val)) return root;
    if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
};

迭代法

var lowestCommonAncestor = function(root, p, q) {
    // 使用迭代的方法
    while(root) {
        if(root.val>p.val&&root.val>q.val) {
            root = root.left;
        }else if(root.val<p.val&&root.val<q.val) {
            root = root.right;
        }else {
            return root;
        }
        
    }
    return null;
};

153 寻找旋转排序数组中的最小值

垃圾O(n)

class Solution {
public:
    int findMin(vector<int>& nums) {
        int minNum = INT_MAX;
        for(int &i :nums){
            minNum=min(i,minNum);
        }
        return minNum;
    }
};

二分法，但用时和空间和O(1)一毛一样

class Solution {
   public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n;
        while (l < r) {
            int mid = (r + l) / 2;
            // cout<<l<<" " <<r<<" "<<mid<<endl;
            if (mid < n - 1 && nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (nums[mid] < nums[l]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[0];
    }
};

因为我写的太垃圾了，所以用这个。

class Solution {
   public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (r + l) / 2;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
};

js版本

var findMin = function (nums) {
    const n = nums.length;
    let l = 0,
        r = n - 1;
    while (l < r) {
        const mid = Math.floor((l + r) / 2);
        if (nums[mid] < nums[r]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return nums[l];
};

162 寻找峰值

朴素O(n)

class Solution {
   public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return 0;
        }
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        if (nums[0] > nums[1]) {
            return 0;
        }
        if (nums[n - 2] < nums[n - 1]) {
            return n - 1;
        }
        return 0;
    }
};

或者直接找最大值，这也太赖了吧

return max_element(nums.begin(), nums.end()) - nums.begin();

二分法，有点尿感觉，我看了好久的r 的取值和最后返回的l。

class Solution {
   public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
};

go语句一秒的事情

func findPeakElement(nums []int) int {
	return sort.Search(len(nums)-1, func(k int) bool { return nums[k] > nums[k+1] })
}