27.移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

题目链接

思路

1. 双指针
   设置两个指针，左指针left，右指针right，左指针left指向待插入不等于val的值，right指针遍历寻找不等于val的值，如果找到，就将right指针指向的值复制到left指针指向的位置，
   然后left指针后移到下一个待插入位置，right指针继续后移寻找下一个不等于val的值，依次类推。

2. 双指针优化
   如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。
   当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。
   这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。

26.删除有序数组中的重复项

题目描述

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

题目链接

思路

1. 双指针
   （1）如果数组为空，返回0
   （2）如果数组只有一个元素，返回1
   （3）如果数组中有超过两个元素，第一个元素肯定不会被删除，所以从第二位位置开始删除重复元素，设置两个指针，一个快指针
   fast，一个慢指针slow，快指针fast用来遍历数组寻找下一个不重复元素，慢指针slow指向存放下一个不重复元素的位置；每当
   fast指针遍历到一个新的不重复元素（fast指向的元素不等于fast-1位置的元素），就将该元素复制到慢指针slow执行的位置，
   同时慢指针slow指向下一个位置，快指针fast继续寻找下一个不重复元素，依次类推。

121.买卖股票的最佳时机

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

题目链接

思路

1. 暴力法

2. 一次遍历
   遍历一遍数组，计算每次 到当天为止 的最小股票价格和最大利润。

3. 动态规划
动态规划一般分为一维、二维、多维（使用状态压缩），对应形式为 dp(i)、dp(i)(j)、二进制dp(i)(j)。
（1）动态规划做题步骤
明确 dp(i) 应该表示什么（二维情况：dp(i)(j)）；
根据 dp(i)和 dp(i−1) 的关系得出状态转移方程；
确定初始条件，如 dp(0)。
（2）本题思路
其实方法一的思路不是凭空想象的，而是由动态规划的思想演变而来。这里介绍一维动态规划思想。
dp[i] 表示前 i 天的最大利润，因为我们始终要使利润最大化，则：

dp[i]=max(dp[i−1],prices[i]−minprice)

136.只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

题目链接

思路

1. python版本
   遍历nums数组中的每一个数num，并使用list.count(num)统计num在nums中出现的次数，如果次数为1，返回num。
2. java版本
   遍历nums数组中的每一个数num，使用HashMap记录每个num出现的次数，然后返回出现次数为1的num。

283.移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

题目链接

思路

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：
（1）左指针左边均为非零数；
（2）右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

448.找到所有数组中消失的数字

题目描述

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

题目链接

思路

可以通过集合求差集的方式实现
set1 = {4,3,2,7,8,2,3,1}
set2 = {1,2,3,4,5,6}
set2 - set1即为题目所求

代码

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 超出时间限制
        # result = []
        # for i in range(1, len(nums)+1):
        #     if i not in nums:
        #         result.append(i)
        # return result

        # 超出时间限制
        # return [i for i in range(1, len(nums)+1) if i not in nums]

        # 集合求差集
        set1 = set(nums)
        set2 = set([i for i in range(1, len(nums) + 1)])
        return list(set2.difference(set1))


if __name__ == "__main__":
    slt = Solution()
    nums = [4, 3, 2, 7, 8, 2, 3, 1]
    result = slt.findDisappearedNumbers(nums)
    print(result)

338.比特位计数

题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 –> 0
1 –> 1
2 –> 10

题目链接

思路

我的题解

代码

class Solution(object):
    def countBits(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        # result = []
        # for i in range(0, n+1):
        #     result.append(bin(i).count('1'))
        # return result

        return [bin(i).count('1') for i in range(0, n+1)]

461.汉明距离

题目描述

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。

题目链接

思路

我的题解

代码

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x ^ y).count('1')


if __name__ == "__main__":
    # # 十进制转二进制：bin(10)
    # print(bin(10))
    # # 十进制转八进制：oct(10)
    # print(oct(10))
    # # 十进制转十六进制：hex(10)
    # print(hex(10))
    #
    # # 二进制转十进制：int("1010",2)
    # print(int("1010", 2))
    # # 八进制转十进制：int("0o12",8)
    # print(int("0o12", 8))
    # # 十六进制转十进制：int("0xa",16)
    # print(int("0xa", 16))
    
    # print(str(bin(1 ^ 4)).count('1'))
    # print(str(bin(3 ^ 1)).count('1'))
    
    slt = Solution()
    result = slt.hammingDistance(1, 4)
    print(result)

617.合并二叉树

题目描述

给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。

示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

题目链接

思路

1. 深度优先搜索
   使用深度优先搜索合并两个二叉树。从根节点开始遍历两个二叉树，并将对应的节点进行合并。

两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
（1）如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
（2）如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
（3）如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。
2. 广度优先搜索
使用广度优先搜索合并两个二叉树。首先判断两个二叉树是否为空，如果两个二叉树都为空，则合并后的二叉树也为空，如果只有一个二叉树为空，则合并后的二叉树为另一个非空的二叉树。

如果两个二叉树都不为空，则首先计算合并后的根节点的值，然后从合并后的二叉树与两个原始二叉树的根节点开始广度优先搜索，从根节点开始同时遍历每个二叉树，并将对应的节点进行合并。

使用三个队列分别存储合并后的二叉树的节点以及两个原始二叉树的节点。初始时将每个二叉树的根节点分别加入相应的队列。每次从每个队列中取出一个节点，判断两个原始二叉树的节点的左右子节点是否为空。如果两个原始二叉树的当前节点中至少有一个节点的左子节点不为空，则合并后的二叉树的对应节点的左子节点也不为空。对于右子节点同理。

如果合并后的二叉树的左子节点不为空，则需要根据两个原始二叉树的左子节点计算合并后的二叉树的左子节点以及整个左子树。考虑以下两种情况：
（1）如果两个原始二叉树的左子节点都不为空，则合并后的二叉树的左子节点的值为两个原始二叉树的左子节点的值之和，在创建合并后的二叉树的左子节点之后，将每个二叉树中的左子节点都加入相应的队列；
（2）如果两个原始二叉树的左子节点有一个为空，即有一个原始二叉树的左子树为空，则合并后的二叉树的左子树即为另一个原始二叉树的左子树，此时也不需要对非空左子树继续遍历，因此不需要将左子节点加入队列。
对于右子节点和右子树，处理方法与左子节点和左子树相同。

543.二叉树的直径

题目描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。

题目链接

思路

1. 深度优先搜索
   首先我们知道一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。
   而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 LLL （即以左儿子为根的子树的深度） 和其右儿子向下遍历经过最多的节点数 RRR （即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 L+R+1L+R+1L+R+1 。
我们记节点 node 为起点的路径经过节点数的最大值为 dnode​ ，那么二叉树的直径就是所有节点 dnode​的最大值减一。

算法流程为：我们定义一个递归函数 depth(node) 计算 dnode​，函数返回该节点为根的子树的深度。先递归调用左儿子和右儿子求得它们为根的子树的深度 L 和 R ，则该节点为根的子树的深度即为
max(L,R)+1，该节点的 dnode​值为 L+R+1，递归搜索每个节点并设一个全局变量 ans 记录 dnode​的最大值，最后返回 ans-1 即为树的直径。

代码

class TreeNode(object):  # Definition for a binary tree node.
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        这种解法路径必须经过根节点，由题目可知路径可能穿过
        也可能不穿过根节点，故此解法不符合题意
        :type root: TreeNode
        :rtype: int
        """
        left = self.get_depth(root.left)
        right = self.get_depth(root.right)
        return left + right
    
    def get_depth(self, root):
        if not root:
            return 0
        left_depth = self.get_depth(root.left)
        right_depth = self.get_depth(root.right)
        return max(left_depth, right_depth) + 1
    
    def diameterOfBinaryTree1(self, root):
        self.ans = 1
        def depth(node):
            if not node:
                return 0
            L = depth(node.left)
            R = depth(node.right)
            self.ans = max(self.ans, L + R + 1)
            return max(L, R) + 1
        depth(root)
        return self.ans - 1  # 一条路径的长度为该路径经过的节点数减一

if __name__ == "__main__":
    slt = Solution()
    root = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    root.left = node2
    root.right = node3
    node2.left = node4
    node2.right = node5
    # diameter = slt.diameterOfBinaryTree(root)
    diameter = slt.diameterOfBinaryTree1(root)
    print("diameter:", diameter)