发表于 | 分类于

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?

解法1：

吃透了bst的性质就好做了：
第一个数字是root，之后找出所有比他大的和所有比他小的范围。
对large 和small分别做递归。
要注意如果left > right return true
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return true;
        }   
        return helper(preorder, 0, preorder.length - 1);
    }
    private boolean helper(int[] preorder, int left, int right) {
        if (left > right) {
            return true;
        }
        if (left == right) {
            return true;
        }
        // root is the first one
        int root = preorder[left];
        // check [left, right] find first index that is larger than root
        int i = left + 1;
        for (;i <= right; i++) {
            if (preorder[i] > root) {
                break;
            }
        }
        if (i > right) {
            return helper(preorder, left + 1, right);
        }
        if (i == right) {
            return helper(preorder, left + 1, right - 1);   
        }
        // check if [i, right] has one element that is smaller than root
        for (int j = i; j <= right; j++) {
            if (preorder[j] < root) {
                return false;
            }
        }
        return helper(preorder, left + 1, i - 1) && helper(preorder, i, right);
    }
}

解法2： Stack O(N) Time + O(N) Space

基本的思想是，用一个stack来维护当前的树，如果一个数字比栈顶的数字小，那么就认为是当前数的左子树，而如果比栈顶的大，那么说明是其中一个node的右字树，那么就需要把栈顶弹出，同时需要更新当前的low，之后所有的点都必须要比这个low大，如果不符合这一点就不是BST。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int lower = Integer.MIN_VALUE;
        for (int i = 0; i < preorder.length; i++) {
            int p = preorder[i];
            if (p < lower) {
                return false;
            }
            while (!stack.isEmpty() && p > stack.peek()) {
                lower = stack.pop();
            }
            stack.push(p);
        }
        return true;
    }
}

解法3： Follow Up Stack O(N) Time + O(1) Space

为了节省空间，就直接用preorder这个数组来当成stack就可以了。

lang: java
1
2
3
4
5
6
7
8
9
10
11
public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE, i = -1;
    for (int p : preorder) {
        if (p < low)
            return false;
        while (i >= 0 && p > preorder[i])
            low = preorder[i--];
        preorder[++i] = p;
    }
    return true;
}

发表于 | 分类于

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

1
2
3
4
5
6
7
1
 \
  3
 / \
2   4
     \
      5

Longest consecutive sequence path is 3-4-5, so return 3.

1
2
3
4
5
6
7
  2
   \
    3
   /
  2    
 /
1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

解法1：

用一个全局变量来存储答案，然后递归遍历数就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        helper(root, 1);
        return max;        
    }
    private void helper(TreeNode root, int count) {
        if (root == null) {
            max = Math.max(max, count);
            return;
        }
        max = Math.max(max, count);
        if (root.left != null) {
            if (root.left.val == root.val + 1) {
                helper(root.left, count + 1);
            } else {
                helper(root.left, 1);
            }
        }
        if (root.right != null) {
            if (root.right.val == root.val + 1) {
                helper(root.right, count + 1);
            } else {
                helper(root.right, 1);
            }
        }
    }
}

发表于 | 分类于

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

1
2
3
4
5
    5
   / \
  1   5
 / \   \
5   5   5

return 4.

解法1：

用Divide & Conquer
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int res = 0;
    public int countUnivalSubtrees(TreeNode root) {
        helper(root);
        return res;
    }
    private boolean helper(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean left = helper(root.left);
        boolean right = helper(root.right);
        if (left && right) {
            if (root.left != null && root.left.val != root.val) {
                return false;
            }
            if (root.right != null && root.right.val != root.val) {
                return false;
            }
            ++res;
            return true;            
        } else {
            return false;
        }
    }
}

发表于 | 分类于

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

解法1： O(N) Space

最直观的方法，就是先做一遍in order, 存起来，然后找出来目标node前一个node即可。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        if (root == null || p == null) {
            return null;
        }
        helper(root, list);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == p) {
                if (i == list.size() - 1) {
                    return null;
                } else {
                    return list.get(i + 1);
                }
            }
        }
        return null;
    }
    private void helper(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        helper(root.left, list);
        list.add(root);
        helper(root.right, list);
    }
}

解法2： O(1) Space

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode prev = null;
    TreeNode res = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        helper(root, p);
        return res;
    }
    private void helper(TreeNode root, TreeNode p) {
        if (root == null) {
            return;
        }
        helper(root.left, p);
        if (prev == p) {
            res = root;
            prev = root;
            return;
        }
        prev = root;
        helper(root.right, p);
    }
}

解法3: Iterative

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (prev == p) return root;            
                prev = root;
                root = root.right;
            }
        }
        return null;
    }
}

发表于 | 分类于

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

1
2
 nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

解法1：

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[][] dp = new int[n][n]; // record the largest coin for a burst between [i, j]
        for (int len = 1; len <= n; len++) {
            for (int start = 0; start <= n - len; start++) {
                int end = start + len - 1;
                // dp[start][end]
                int max = Integer.MIN_VALUE;
                for (int i = start; i <= end; i++) {
                    int coins = 0;
                    coins = nums[i] * (start == 0 ? 1 : nums[start - 1]) * (end == n - 1 ? 1 : nums[end + 1]);
                    // burst nums[i]
                    if (i != start) {
                        coins += dp[start][i - 1];
                    }
                    if (i != end) {
                        coins += dp[i + 1][end];
                    }
                    max = Math.max(max, coins);
                }
                dp[start][end] = max;
            }
        }
        return dp[0][n - 1];
    }
}

发表于 | 分类于

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

1
2
3
4
5
6
7
8
9
10
Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2

解法1：两次dp

两次dp的思想很巧妙，用up和down两个数组记录到当前位置，最后相邻的两个是up的最长wiggle sequence或者是最后相邻两个是down的最长wiggle sequence。
那么只要交替更新一下每一个dp array就可以了。
似乎这和minmax类的题目很类似， 比如Predict the winner，也是用两个相互影响的dp数组来完成。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null) {
            return 0;
        }
        if (nums.length <= 1) {
            return nums.length;
        }
        int n = nums.length;
        int[] up = new int[n];
        int[] down = new int[n];
        up[0] = 1; down[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up[i] = down[i - 1] + 1;
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                down[i] = up[i - 1] + 1;
                up[i] = up[i - 1];
            } else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }
        return Math.max(up[n - 1], down[n - 1]);
    }
}

发表于 | 分类于

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:

The given numbers of 0s and 1s will both not exceed 100
The size of given string array won't exceed 600.

Example 1:

1
2
3
4
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Example 2:

1
2
3
4
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

解法1：

这个的解释还算可以,来自于leetcode discuss:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
The idea is to build up the solution for 0..m zeros and 0..n ones, from only knowing 1 string, 2 strings, ..., up to n strings.
For example, for array = {"10", "0", "1"}, m = 1, n = 1.
    for first string "10":
        zero = 0, one = 0
        zero = 1, one = 0
        zero = 0, one = 1
        zero = 1, one = 1, can form "10" [+1]
    continue on the second string "0", with previous knowledge of string "10":
        zero = 0, one = 0
        zero = 1, one = 0, can form "0" [+1]
        zero = 0, one = 1
        zero = 1, one = 1, can form "0" [+1] or 1 string ("10"), known from previous string
    continue on the last string "1", with previous knowledge of strings "10" and "0":
        zero = 0, one = 0
        zero = 1, one = 0, can't form "1", but we know it can form 1 string ("0") from previous set of strings
        zero = 0, one = 1, can form "1" (+1)
        zero = 1, one = 1, (can form "1" and 1 more string ("0") with zero = 1, one = 0, known from previous set of strings) or (1 string ("10"), known from previous set of strings)
Hence, at the end, we know that with zero = 1, one = 1, with string "10", "0", and "1", the maximum number of strings we can form is 2.

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int[] count = count(str);
            for (int i = m; i >= count[0]; i--) {
                for (int j = n; j >= count[1]; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
    private static int[] count(String s) {
	int[] result = new int[2];
	char[] array = s.toCharArray();
	for (int i : array) {
	    result[i - '0']++;
	}
	return result;
    }
}

解法2： 背包解法

此题实际上是一个背包问题，背包问题的本质是：
求一个最大或者最小，给定一定的限定条件。这里的限定条件是有限的0和1。
背包就构建一个n维数组，dp[i][j][k]表示前i个数，用jk两个限定条件所能达到的最大结果。

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) {
            return 0;
        }
        int strn = strs.length;
        int[][][] dp = new int[strn + 1][m + 1][n + 1];
        // dp[l][i][j] means up to first l strings, with m zeros and n ones, the max number of strings it can form
        // do[l][i][j] = Math.max(dp[l - 1][i - zero[l]][j - zero[l][i - ones]] + 1, dp[l - 1][i][j]）；
        for (int l = 1; l <= strn; l++) {
            int[] current = count(strs[l - 1]);   // count current number of zeros and ones
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (i >= current[0] && j >= current[1]) {
                        dp[l][i][j] = Math.max(dp[l][i][j], dp[l - 1][i - current[0]][j - current[1]] + 1);
                    }
                    dp[l][i][j] = Math.max(dp[l][i][j], dp[l - 1][i][j]);
                }
            }
        }
        return dp[strn][m][n];
    }
    private int[] count(String str) {
        // count number of ones and zeros in the string
        int[] res = new int[2];
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                res[0]++;
            } else {
                res[1]++;
            }
        }
        return res;
    }
}

发表于 | 分类于

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
maxChoosableInteger = 10
desiredTotal = 11
Output:
false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

解法1：

当dp不太好想的时候考虑用一下memorization来减少复杂度。
这题粗暴思路就是一个dfs，来判断对于一组数是否能win。
那么我们可以把当前数字使用情况转变成一个key来存储起来。
转成key的思路是把每一位数字如果没被用过变为0，用过了变为1.
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {
    private HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int sum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
        if (sum < desiredTotal) {
            return false;
        }
        if (maxChoosableInteger >= desiredTotal) {
            return true;
        }
        boolean[] used = new boolean[maxChoosableInteger + 1];
        return helper(used, desiredTotal, maxChoosableInteger);
    }
    private boolean helper(boolean[] used, int desiredTotal, int max) {
        if (desiredTotal <= 0) {
            return false;
        }
        int key = transform(used);
        if (map.containsKey(key)) {
            return map.get(key);
        }
        for (int i = 1; i <= max; i++) {
            if (!used[i]) {
                used[i] = true;
                boolean sub = helper(used, desiredTotal - i, max);
                used[i] = false;
                if (!sub) {
                    map.put(key, true);
                    return true;
                }
            }
        }
        map.put(key, false);
        return false;
    }
    private int transform(boolean[] used) {
        int num = 0;
        for (boolean i : used) {
            num <<= 1;
            if (i) {
                num |= 1;
            }
        }
        return num;
    }
}

发表于 | 分类于

Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

1
2
3
4
Input: "a"
Output: 1
Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

1
2
3
Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

1
2
3
Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

解法1:

又是维护一个running local optimal，然后再更新最终答案的题目。
这里是把p中以每一个字符结尾的最长子串加入到hashmap中。
之后再得出一个加和就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int findSubstringInWraproundString(String p) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int maxLen = 0;
        for (int i = 0; i < p.length(); i++) {
            if (i > 0 && (p.charAt(i) - p.charAt(i -1) == 1 || p.charAt(i) - p.charAt(i - 1) == -25)) {
                maxLen++;
            } else {
                maxLen = 1;
            }
            map.put(p.charAt(i), Math.max(map.getOrDefault(p.charAt(i), 0), maxLen));
        }
        int sum = 0;
        for (char key : map.keySet()) {
            sum += map.get(key);
        }
        return sum;        
    }
}

发表于 | 分类于

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

解法1：BFS

BFS 然后reverse间隔行就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();
                temp.add(current.val);
                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
            if (level % 2 == 0) {
                // reverse the temp
                for (int i = 0, j = temp.size() - 1; i < j; i++, j--) {
                    int buffer = temp.get(i);
                    temp.set(i, temp.get(j));
                    temp.set(j, buffer);
                }
            }
            res.add(temp);
            level++;
        }
        return res;
    }
}