LEETCODE 第169场周赛

前三题比较容易，第四题有点点难。

Contents

1 第一题：和为零的N个唯一整数
2 第二题：两棵二叉搜索树中的所有元素
3 第三题：跳跃游戏 III
4 第四题：口算难题

第一题：和为零的N个唯一整数

　　给你一个整数 n，请你返回任意一个由 n 个各不相同的整数组成的数组，并且这 n 个数相加和为 0 。
　　　
　　示例 1：
　　
　　输入：n = 5
　　输出：[-7,-1,1,3,4]
　　解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。
　　示例 2：
　　
　　输入：n = 3
　　输出：[-1,0,1]
　　示例 3：
　　
　　输入：n = 1
　　输出：[0]

思路：如果n为偶数，取相反数即可，如果n为奇数，取0和相反数即可。

class Solution:
    def sumZero(self, n: int) -> List[int]:
        if n % 2 ==1:
            ans = [0]
        else:
            ans = []

        for i in range(n//2):
            ans.append(i+1)
            ans.append(-i-1)

        return ans

class Solution:

def sumZero(self, n: int) -> List[int]:

if n % 2 ==1:

ans = [0]

else:

ans = []

for i in range(n//2):

ans.append(i+1)

ans.append(-i-1)

return ans

第二题：两棵二叉搜索树中的所有元素

　　给你 root1 和 root2 这两棵二叉搜索树。
　　
　　请你返回一个列表，其中包含两棵树中的所有整数并按升序排序。.
　　
　　示例 1：
　　输入：root1 = [2,1,4], root2 = [1,0,3]
　　输出：[0,1,1,2,3,4]
　　
　　示例 2：
　　输入：root1 = [0,-10,10], root2 = [5,1,7,0,2]
　　输出：[-10,0,0,1,2,5,7,10]
　　
　　示例 3：
　　输入：root1 = [], root2 = [5,1,7,0,2]
　　输出：[0,1,2,5,7]
　　
　　示例 4：
　　输入：root1 = [0,-10,10], root2 = []
　　输出：[-10,0,10]
　　
　　示例 5：
　　输入：root1 = [1,null,8], root2 = [8,1]
　　输出：[1,1,8,8]

思路：先分别先序遍历一遍，然后再合并

class Solution {
public:
    vector<int> t1;
    vector<int> t2;

    void dfs(TreeNode* root, int t){
        if(!root) return;
        if (root->left) {
            dfs(root->left ,t);
        }
        if(t==1)t1.push_back(root->val);
        else t2.push_back(root->val);
        if(root->right){
            dfs(root->right ,t);
        }

    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> ans;
        dfs(root1, 1);
        dfs(root2 ,2);
        int i =0;
        int j =0;
        while(i<t1.size() && j<t2.size()){
            if(t1[i]>t2[j]){
                ans.push_back(t2[j]);
                j++;
            }
            else{
                ans.push_back(t1[i]);
                i++;
            }
        }
        while(i<t1.size()){
            ans.push_back(t1[i]);
            i++;
        }
        while(j<t2.size()){
            ans.push_back(t2[j]);
            j++;

        }

        return ans;
    }
};

class Solution {

public:

vector<int> t1;

vector<int> t2;

void dfs(TreeNode* root, int t){

if(!root) return;

if (root->left) {

dfs(root->left ,t);

}

if(t==1)t1.push_back(root->val);

else t2.push_back(root->val);

if(root->right){

dfs(root->right ,t);

}

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

vector<int> ans;

dfs(root1, 1);

dfs(root2 ,2);

int i =0;

int j =0;

while(i<t1.size() && j<t2.size()){

if(t1[i]>t2[j]){

ans.push_back(t2[j]);

j++;

}

else{

ans.push_back(t1[i]);

i++;

}

while(i<t1.size()){

ans.push_back(t1[i]);

i++;

}

while(j<t2.size()){

ans.push_back(t2[j]);

j++;

}

return ans;

}

};

第三题：跳跃游戏 III

　　这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i – arr[i]。
　　
　　请你判断自己是否能够跳到对应元素值为 0 的任意下标处。
　　
　　注意，不管是什么情况下，你都无法跳到数组之外。
　　
　　示例 1：
　　
　　输入：arr = [4,2,3,0,3,1,2], start = 5
　　输出：true
　　解释：
　　到达值为 0 的下标 3 有以下可能方案：
　　下标 5 -> 下标 4 -> 下标 1 -> 下标 3
　　下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
　　示例 2：
　　
　　输入：arr = [4,2,3,0,3,1,2], start = 0
　　输出：true
　　解释：
　　到达值为 0 的下标 3 有以下可能方案：
　　下标 0 -> 下标 4 -> 下标 1 -> 下标 3
　　示例 3：
　　
　　输入：arr = [3,0,2,1,2], start = 2
　　输出：false
　　解释：无法到达值为 0 的下标 1 处。

思路：DFS，把所有能到达的位置标为-1

class Solution:

    def dfs(self, arr, i):
        if i < 0 or i > len(arr) - 1 or arr[i] == -1:  # 下标越界或者已经走过了就不走了
            return

        k = arr[i]
        arr[i] = -1  # 能到达，置为-1
        self.dfs(arr, i - k)  # 向前走
        self.dfs(arr, i + k)  # 向后走

    def canReach(self, arr: List[int], start: int) -> bool:
        a = arr.copy()
        self.dfs(a, start)
        for i in range(len(arr)):
            if arr[i] == 0 and a[i] == -1:
                return True

        return False

class Solution:

def dfs(self, arr, i):

if i < 0 or i > len(arr) - 1 or arr[i] == -1: # 下标越界或者已经走过了就不走了

return

k = arr[i]

arr[i] = -1 # 能到达，置为-1

self.dfs(arr, i - k) # 向前走

self.dfs(arr, i + k) # 向后走

def canReach(self, arr: List[int], start: int) -> bool:

a = arr.copy()

self.dfs(a, start)

for i in range(len(arr)):

if arr[i] == 0 and a[i] == -1:

return True

return False

第四题：口算难题

　　你需要根据以下规则检查方程是否可解：
　　
　　每个字符都会被解码成一位数字（0 – 9）。
　　每对不同的字符必须映射到不同的数字。
　　每个 words[i] 和 result 都会被解码成一个没有前导零的数字。
　　左侧数字之和（words）等于右侧数字（result）。
　　如果方程可解，返回 True，否则返回 False。
　　　
　　示例 1：
　　
　　输入：words = [“SEND”,”MORE”], result = “MONEY”
　　输出：true
　　解释：映射 ‘S’-> 9, ‘E’->5, ‘N’->6, ‘D’->7, ‘M’->1, ‘O’->0, ‘R’->8, ‘Y’->’2′
　　所以 “SEND” + “MORE” = “MONEY” , 9567 + 1085 = 10652
　　示例 2：
　　
　　输入：words = [“SIX”,”SEVEN”,”SEVEN”], result = “TWENTY”
　　输出：true
　　解释：映射 ‘S’-> 6, ‘I’->5, ‘X’->0, ‘E’->8, ‘V’->7, ‘N’->2, ‘T’->1, ‘W’->’3′, ‘Y’->4
　　所以 “SIX” + “SEVEN” + “SEVEN” = “TWENTY” , 650 + 68782 + 68782 = 138214
　　示例 3：
　　
　　输入：words = [“THIS”,”IS”,”TOO”], result = “FUNNY”
　　输出：true
　　示例 4：
　　
　　输入：words = [“LEET”,”CODE”], result = “POINT”
　　输出：false
　　
　　提示：
　　
　　2 <= words.length <= 5
　　1 <= words[i].length, results.length <= 7
　　words[i], result 只含有大写英文字母
　　表达式中使用的不同字符数最大为 10

思路：将words倒序以后遍历，不遍历result，根据words求和得到result的结果，然后再判断符不符合规则。如果result中的结果已经有映射了但是结果不正确则return False。如果result中的结果没有映射，则将映射置为算出的结果。将result加在了words的最后方便遍历，x表示第几位，y表示第几个单词，sum保存的是进位。

class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        m = [-1] * 26  # 保存映射
        used = [False] * 10
        for i in range(len(words)):
            words[i] = words[i][::-1]  # 反序

        words.append(result[::-1])
        print(words)
        l = len(words)
        mlen = max([len(w) for w in words])
        # 0 0   0 1   0 2
        # 1 0   1 1   1 2
        def dfs(x, y, sum):  # x表示第几位, y表示第几个

            if x > mlen-1:
                # print_map(m)
                return True

            if y == l - 1:  # result不进行搜索 而是用words计算
                c = ord(words[-1][x]) - ord('A')  # result对应位置的字符转成数字

                if m[c] >= 0:  # 字符已经有映射了
                    if m[c] != sum % 10:  # 计算结果不对直接结束
                        return False
                else:  # 字符还没有映射
                    i = sum % 10
                    if not used[i]:
                        used[i] = True
                        m[c] = i
                        sum = sum // 10

                        if dfs(x+1, 0, sum):
                            return True

                        used[i] = False
                        m[c] = -1
                        return False
                    else:
                        return False  # result的数字已经被其他的字符用过了

                sum = sum // 10  # 将sum置为进位的数

                return dfs(x+1, 0, sum)

            if x > len(words[y]) - 1:  # 不够了
                if dfs(x, y+1, sum):
                    return True
            else:
                islast = x >= len(words[y]) - 1
                c = ord(words[y][x]) - ord('A')
                if m[c] >= 0:  # 字母已经用过了
                    if islast and m[c] == 0:  # 不能有前置0
                        return False
                    if dfs(x, y+1, sum + m[c]):
                        return True
                else:
                    for i in range(10):
                        if islast and i == 0:
                            continue
                        if not used[i]:
                            used[i] = True
                            m[c] = i
                            if dfs(x, y+1, sum+i):
                                return True
                            used[i] = False
                            m[c] = -1
            return False

        return dfs(0, 0, 0)

class Solution:

def isSolvable(self, words: List[str], result: str) -> bool:

m = [-1] * 26 # 保存映射

used = [False] * 10

for i in range(len(words)):

words[i] = words[i][::-1] # 反序

words.append(result[::-1])

print(words)

l = len(words)

mlen = max([len(w) for w in words])

# 0 0 0 1 0 2

# 1 0 1 1 1 2

def dfs(x, y, sum): # x表示第几位, y表示第几个

if x > mlen-1:

# print_map(m)

return True

if y == l - 1: # result不进行搜索而是用words计算

c = ord(words[-1][x]) - ord('A') # result对应位置的字符转成数字

if m[c] >= 0: # 字符已经有映射了

if m[c] != sum % 10: # 计算结果不对直接结束

return False

else: # 字符还没有映射

i = sum % 10

if not used[i]:

used[i] = True

m[c] = i

sum = sum // 10

if dfs(x+1, 0, sum):

return True

used[i] = False

m[c] = -1

return False

else:

return False # result的数字已经被其他的字符用过了

sum = sum // 10 # 将sum置为进位的数

return dfs(x+1, 0, sum)

if x > len(words[y]) - 1: # 不够了

if dfs(x, y+1, sum):

return True

else:

islast = x >= len(words[y]) - 1

c = ord(words[y][x]) - ord('A')

if m[c] >= 0: # 字母已经用过了

if islast and m[c] == 0: # 不能有前置0

return False

if dfs(x, y+1, sum + m[c]):

return True

else:

for i in range(10):

if islast and i == 0:

continue

if not used[i]:

used[i] = True

m[c] = i

if dfs(x, y+1, sum+i):

return True

used[i] = False

m[c] = -1

return False

return dfs(0, 0, 0)