leetcode第 132 场周赛

leetcdoe-weekly-contest-132

1 第一题目： 除数博弈【Easy】

Divisor Game

1.1分析

Divisor Game 输入6的的选择判断

1.2 code

时间复杂度：O(n^2) 有那个N个元素，每个元素计算N次。
空间复杂度：O(n)

/**
01
别人描述的题目是是否理解清楚，如果不知道清楚不是清楚，回答下面2个问题
1 要求获取什么样的结果 清楚吗？
    两个玩家都以最佳状态参与游戏,如果玩家无法执行这些操作，就会输掉游戏，问爱丽丝在游戏中取得胜利？
2 输入什么样的数据清楚吗？
    黑板上有一个数字 N
    0 < x < N
    N % x == 0 。
    N-x
    这是博弈论问题
3 如果还是不清楚，请举例说明，一定不要放过去。
  a 如何表示最佳状态
 一个数字N，能被整除的多个，选择其中一个回赢选择，另外一个会输，
   自然选择赢的那个数字，。只选择能赢的那个数字。

  b 对方赢，自己输 如何表示

**/
func divisorGame(N int) bool {

    dp := make([]bool, N+1)
    dp[0] = false //0 < x < N,不能为为零,无法选择
    dp[1] = false //爱丽丝:0<x<1 无法选择，输掉游戏
    isWin := false

    for i := 2; i <= N; i++ {

        isWin = false
        //爱丽丝 有哪些数字可以选择
        for j := 1; j < i; j++ {
            //爱丽丝 我选择j，
            if i%j == 0 {
                //对方赢，自己输
                isWin = (isWin || !dp[i-j]) //最佳状态
            }
        }
        dp[i] = isWin

    }
    return dp[N]
}

//o（1）
func divisorGame(N int) bool {
    return N%2==0
}

2 第二题： 节点与其祖先之间的最大差值【Medium】

1026. Maximum Difference Between Node and Ancestor

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.
题目大意：给你一棵二叉树，找出一个pair (n, a)，a必选是n的祖先，使得|n.val - a.val|的值最大化。

2.1 分析

8>3>1 调用只有一次，如何传递allparent节点？ 每个路径，遍历一次
max-min

2.2code1 暴力破解

暴力破解
1 遍历每个root节点 ------------一层循环
2.计算每个root节点和其他子节点的差异 ------------第二层循环

time：o(n^2)
space:o(n)
Runtime: 88 ms, faster than 5.17%

/**
01
别人描述的题目是是否理解清楚，如果不知道清楚不是清楚，回答下面2个问题
1 要求获取什么样的结果 清楚吗？
    求2个节点差值最大：
    Maximum Difference Between Node and Ancestor
    where V = |A.val - B.val| and A is an ancestor of B

2 输入什么样的数据清楚吗？
  理解1 从root节点到叶子节点 有n个路径，每个路径上m node，n×m个数字差值。


3 真的理解清楚了吗？
   理解纠正 理解1 root节点到child节点n个，每个n也是root节点
   n*m*m 累计差值比较
   The number of nodes in the tree is between 2 and 5000.
Runtime: 88 ms, faster than 5.17% of Go online submissions for Maximum Difference Between Node and Ancestor

time：o(n^2)
space:o(n)


**/
func maxAncestorDiff(root *TreeNode) int {
    result := 0
    max_diff(root, &result)
    return result
}

func max_diff(root *TreeNode, result *int) {
    if root == nil {
        return
    }
    max_root_diff(root, root.Val, result)

    max_diff(root.Left, result)
    max_diff(root.Right, result)
}

func max_root_diff(root *TreeNode, rootValue int, max *int) {

    if root == nil {
        return
    }
    if *max < root.Val-rootValue {
        *max = (root.Val - rootValue)
    } else if *max < rootValue-root.Val {
        *max = rootValue - root.Val
    }
    max_root_diff(root.Left, rootValue, max)
    max_root_diff(root.Right, rootValue, max)
}

2.2 code2

time:0(n)
space:o(n)
Runtime: 4 ms, faster than 96.55%

/**
time:0(n)
space:o(n)
通过参数从上到下传递数据 区分什么指针传递，什么使用值传递
这次不是1个参数，是2个参数
Runtime: 4 ms, faster than 96.55%
**/
func maxAncestorDiff(root *TreeNode) int {
    diff := 0
    dFsmaxAncestorDiff(root, root.Val, root.Val, &diff)
    return diff
}

func dFsmaxAncestorDiff(root *TreeNode, min int, max int, diff *int) {
    if root == nil {
        return
    }

    if max < root.Val {
        max = root.Val
    }
    if min > root.Val {
        min = root.Val
    }
    if max-min > *diff {
        *diff = max - min
    }
    dFsmaxAncestorDiff(root.Left, min, max, diff)
    //min, max 不能被先顺遍历节点修改 前面执行 diff 可以
    dFsmaxAncestorDiff(root.Right, min, max, diff)
}

第四题 最长等差数列 [Medium]

4.1 题目

longest-arithmetic-sequence

• 没看懂啥意思 直接看例子

输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：

输入：[20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]

等差数列 等差数列

不考虑任何技巧，
时间复杂度：O(n^2 * n) = O(n^3)
空间复杂度：O(1)

第一个数字 和第二个数字比较有个差额，寻找类似的差额 n
第一个数字 和第三个数字比较有个差额，寻找类似的差额 n
第i个数字 。。。。 n

/**
别人描述的题目是是否理解清楚，如果不知道清楚不是清楚，回答下面2个问题
1 要求获取什么样的结果 清楚吗？


2 输入什么样的数据清楚吗？



3 真的理解清楚了吗？
是多少的等差数列
不考虑任何技巧，
时间复杂度：O(n^2 * n) = O(n^3)
空间复杂度：O(1)

第一个数字 和第二个数字比较有个差额，寻找类似的差额 n
第一个数字 和第三个数字比较有个差额，寻找类似的差额 n
第i个数字 。。。。                             n
执行用时：1768 ms

**/
func longestArithSeqLength(A []int) int {
    n := len(A)
    maxLengh := 0
    curLength := 0

    //第一层 每个元素都是序列开始位置
    for i := 0; i < n-1; i++ {

        //第一个元素和j元素寻找差值
        for j := i + 1; j < n; j++ {
            d := A[j] - A[i]
            //寻找类似等差序列
            next := A[j] + d
            curLength = 2
            for k := j + 1; k < n; k++ {
                if A[k] == next {
                    curLength++
                    next = A[k] + d
                }
            } //3

            if curLength > maxLengh {
                maxLengh = curLength
            }
        } //2
    } //11
    return maxLengh
}

3.2 其他更好方式 ---我还没想出来，-其他人的也没看懂

第四题 1028. 从先序遍历还原二叉树[hard]

recover-a-tree-from-preorder-traversal

We run a preorder depth first search on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)

If a node has only one child, that child is guaranteed to be the left child.

Given the output S of this traversal, recover the tree and return its root.

4.1 题意理解

没有看懂题目 d+1 是什么？

先序遍历输出结果添加-

提示：
原始树中的节点数介于 1 和 1000 之间。
每个节点的值介于 1 和 10 ^ 9 之间。

• 这是时候不要急着做题，题目根本不明白，一做就是错

  
  题目依然没有明白

输入字符串的理解

• demo3

  
  demo3

输入字符串的理解

-- 非递归遍历

节点的深度大小决定入栈出栈的顺序

90元素的深度为3 此时栈内数据有三个元素
88元素 深度为2，必须出栈2个元素，剩余栈大小为2

节点深度和栈的大小关系

时间复杂度：O(n)
空间复杂度：O(n)
public TreeNode recoverFromPreorder(String S) {
        int level, val;
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 0; i < S.length();) {
            for (level = 0; S.charAt(i) == '-'; i++) {
                level++;
            }
            for (val = 0; i < S.length() && S.charAt(i) != '-'; i++) {
                val = val * 10 + (S.charAt(i) - '0');
            }
            while (stack.size() > level) {
                stack.pop();
            }
            TreeNode node = new TreeNode(val);
            if (!stack.isEmpty()) {
                if (stack.peek().left == null) {
                    stack.peek().left = node;
                } else {
                    stack.peek().right = node;
                }
            }
            stack.add(node);
        }
        while (stack.size() > 1) {
            stack.pop();
        }
        return stack.pop();
    }

-- 递归的遍历输出，递归遍历构造

递归的时候我们需要记录处理到第几个字符了i，以及当前的期待深度d（非常重要）。

另外我们需要两个辅助函数，这可以使得我们主递归函数非常
简洁清晰
getD()，获得当前深度（看看有几个"-"字符）
getV()，获得当前节点值
如果getD() != d，表示当前这个节点不合法，返回空指针
否则
创建根节点值为getV()
递归构建左子树(i, d + 1)
递归构建右子树(i, d + 1)
TreeNode* root = new TreeNode(val);
root->left = dfs(S, i, depth + 1);
root->right = dfs(S, i, depth + 1);
return root;
时间复杂度：O(n)
空间复杂度：O(n)

来源花花酱

func recover_from_string(input *string, index *int, depth int) *TreeNode {

    //当前元素的高度
    realDeth := get_node_depth(s,index)
    //判断当前元素是上个元素子元素
    if depth != realDeth {
         *index-=realDeth //index全局变量 要回退，不正确的位置
        retur nil
    }
    //字符串变整数
    nodeValue:=get_node_value(s,index)
    
    ptr:=new TreeNode(nodeValue,nil,nil);
    ptr.Left=recover_from_string(s,index,depth+1)
    ptr.Right=recover_from_string(s,index,depth+1)
    return ptr
}

func get_node_depth(s *string,index* int){
     d:=0
    for ;*index<len(s)&&s[*index]=='-';*index++{
        d++
    }
    return d
}
func get_node_value(s *string,index* int){
     val:=0
    for ;*index<len(s)&&s[*index]!='-';*index++{
        val=val*10+(s[*index]='0')
    }
    return val
}

学会提问1：为什么出现 i-d 回？
递归调用依靠的栈--栈控制顺序
什么时候从上到下传递是参数：应该层次
如果计算改节点错误 需要上层，继续计算
知道何时层次为止

image.png

学会提问2：
如果节点的深度为 D，则其直接子节点的深度为 D + 1。没理解明白？

获取一个元素，判断是不是上个元素节点子节点
get_node_depth=stack.length()-1+1= stack.length(）
stack.length()-1--上个元素的深度
如果节点的深度为 D，则其直接子节点的深度为 D + 1

类似问题：判断一个tree是否完全二叉树 ，

每个节点的编号
和实际长度的关系