剑指offer52-两个链表的第一个公共节点

题目描述：输入两个链表，找出它们的第一个公共节点。

解题的思路：

1. 采用双指针的解法，并且在遍历的过程中用到了三目运算符
2. 两个指针在走到它们各自链表的结尾的时候需要跳到另一个链表的头开始遍历
3. 最终它们要么在某一个节点相遇，要么在None相遇（也即没有相遇）

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 思考这是一道链表的题目，用什么方法比较好
        # 要找出公共节点，尝试使用双指针的思路来解题
        # 相交的位置的值是相同的

        # 进行边界的判断
        # 如果两个链表其中一个为空的话
        if not headA or not headB:
            return None
        # 同时从两个链表的头部开始遍历
        pA,pB=headA,headB
        # 指针pA和pB不断的向后遍历，直到找到相交点
        # 如果两个链表不相交，则None是它们的相交点，因此不会跳不出循环
        while pA!=pB:
            # 指针pA一开始在链表A上遍历，当走到链表A的尾部的时候（即指向None）,跳到链表B上面
            pA=pA.next if pA else headB
            # 指针pB一开始在链表B上遍历，当走到链表B的尾部的时候（即指向None）,跳到链表A上面
            pB=pB.next if pB else headA
        return pA

剑指offer54-二叉搜索树的第k大节点

题目描述：给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
基础知识：

1. 对于任意一个二叉搜索树
   解题思路：
2. 将二叉树按照中序遍历的方式输出
3. 将中序遍历倒序输出

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        # 解题思路：将二叉搜索树转换成为一个中序遍历的序列/链表
        # 然后将列表进行排序（倒序），输出相应的值
        # 实际上用一根线从右往左扫描就行了
        # 采用递归的写法（中序遍历）
        res=[]
        def dfs(root):
            if not root:
                return []
            else:
                # 遍历左子树
                dfs(root.left)
                # 加入根节点
                res.append(root.val)
                # 遍历右子树
                dfs(root.right)
        dfs(root)
        # print(res)
        return res[::-1][k-1]

剑指offer57I-和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

一开始自己做了一遍，用的元组的方法，不过最后只AC了70%的案例
这里附上相应的代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        nums=tuple(nums)
        # print(nums)
        res=[]
        for i in range(n):
            # 如果元素不在元组中，将该值加入元组中
            if target-nums[i] in nums:
                res.append(nums[i])
                res.append(target-nums[i])
                break
        return res

看了题解之后，想到有更加有效的方法，整理如下：
利用哈希表可以通过遍历组合找到数组组合。用字典存储已经遍历的结果，如果target-c也在字典中，则输出[c,target-c]即为题目中需要的结果，时间和空间的复杂度均为O(N)
在考试的时候写出这样的答案我觉得已经不错了，只要是能够AC的，相比纯暴力的解法要好多了，也对哈希字典有了更多的了解。

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap=dict()
        n=len(nums)
        # 特殊情况的判定：nums的长度为1
        if n==1:
            return []
            
        for c in nums:
            # 如果发现target-c也在哈希表中，直接输出[c,target-c]
            if target-c in hashmap:
                return [c,target-c]
            hashmap[c]=0
        return []

if __name__=="__main__":
    nums=[10,26,30,31,47,60]
    target=40
    res=Solution().twoSum(nums,target)
    print(res)

由于是排序的数组，可以使用双指针将空间复杂度降低为O(1)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        if n==1:
            return []
        # 设置两个指针分别指向数组的开头和末尾位置
        left,right=0,n-1
        while left <right:
            # 定义一个数组sum
            sum=nums[left]+nums[right]
            # 如果发现之和小于target
            if sum<target:
                # 说明需要将左指针右移
                left+=1
            elif sum==target:
                return [nums[left],nums[right]]
            # 如果发现之和大于target,说明需要将右指针左移
            else:
                right-=1
        # 循环结束仍没有返回
        return []

剑指offer57II-和为s的连续正数序列

自己采用的是暴力的解法，结果是超出了时间的限制

# 暴力解法
# 不能完全通过（AC大约70%）
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        n=target//2+1
        res=[]
        nums=[i for i in range(1,n+1)]
        # print(nums)
        for i in range(n+1):
            for j in range(i+1,n+1):
                temp=sum(nums[i:j])
                if temp==target:
                    res.append(nums[i:j])
        return res

看看题解有没有什么比较好的方法：（滑动窗口的思路）


自己写的时候一直调试失败，打败我的真的是一些细节的部分，实在是太细了
调试了好几遍，还是在仔细对比K神的基础上才发现问题所在，有一些细节：

1. 当sum<target的时候,此时需要先把右边窗口扩大后再加入到sum值中
2. 当sum>target的时候,需要sum中的值减小后，然后再将左侧的窗口向右滑动
3. 当sum=target的时候，这个时候的窗口仍然需要滑动，sum值仍然需要更新

# 根据K神的代码更改的版本
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # 采用滑动窗口的思路来解题
        # 滑动窗口用错方式了
        # n=target//2+1
        # nums=[i for i in range(1,n+1)]
        # 定义了三个值：分别是第一个，第二个以及两数之和
        i,j,s=1,2,3
        # 用于储存结果
        res=[]
        while i<j:
            # 此时的正是要求的区间值，加入结果数组中
            if s==target:
                # res.append(nums[i-1:j+1])
                res.append(list(range(i, j + 1)))

            # 如果发现之和小于目标值，将右边的值+1，同时将和更新
            if s<=target:
                j+=1
                s+=j
            # 如果发现之和大于目标值，将左边的值+1，同时将和更新
            elif s>target:
                s-=i
                i+=1      
        return res

后来仔细想了想，自己的代码就是在细节上没有处理好，当判定sum==target的时候，也需要移动数和改变sum的值，这里摘录后面自己修改后的版本

剑指offer58I-翻转单词顺序

还有一个案例没有通过，没通过的主要原因：”a good example” ,在good和example这两个单词中间有两个空格，但是在我的代码中并没有将这个考虑进去。
发现问题：原因是我在用split()函数的时候，没有区分split()和split(“ “)的区别

1. s.split() :在用空格分割字符串的时候可以将多个空格连在一起进行分割
2. s.split(‘ ‘) :在用空格分割的时候就会存在问题，因为有的单词之间存在多个空格的情况，比如说的这个例子
   
   这种方法实际上是借用语言的特性，简单的调用内置的API函数来完成的

# 进行发现问题后通过的版本
class Solution:
    def reverseWords(self, s: str) -> str:
        # 翻转句子中的单词顺序，单词内的顺序不变，标点符号和普通字母一样处理
        # 采用字符串的空格的切分方式
        # 先将字符串中的多个空格转化为只有一个空格，并转化为列表的形式
        a=s.split()
        # print(a)
        # 列表翻转
        b=a[::-1]
        # print(b)
        # 用join函数对字符串进行连接，同时去除头部和尾部的空格
        res=' '.join(b).lstrip().rstrip()
        # print(res)
        return res

这里再次参考别人一些比较 优秀的解法：用双指针
具体的算法解析：

1. 倒序遍历字符串，记录单词的左右索引边界i j
2. 每确定一个单词的边界，则将其添加到单词的列表中
3. 最终将单词的列表拼接为字符串，并返回

如果采用自己编写函数的方式去解决的话就稍微偏麻烦一点（python的语言字符串不可变）
需要将字符串转化为可变的数据结构，在转化的过程中去除空格
具体的代码后面有空再另行整理

# 其他解法待整理：K神和官方题解

剑指offer58II-左旋转字符串

自己写的稍微有点简单

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        # 左旋转本质就是字符串的切分
        a=s[:n]
        b=s[n:]
        return b+a

有空的话建议看看K神的其他做法
https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/solution/mian-shi-ti-58-ii-zuo-xuan-zhuan-zi-fu-chuan-qie-p/

剑指offer59I-滑动窗口的最大值（已经做过的）

自己独立做出来了，想想之前做的另外的一个版本的方法是怎么样的
在别处已经做完了，此处省略

剑指offer59II-队列的最大值

虽然是模仿的，但是也要追根溯源的把概念搞清楚
看到题解的时候发现这一部分写的十分的详细，而且内容也是特别的多，看来也是自己学习的一个地方呀，得好好整理一下，好好的补充一下知识点。我自己写的这种方式可能时间复杂度不同，需要满足O(1）的要求。所以还是得学习一下：
对于一个普通的队列，push_back 和 pop_front 的时间复杂度都是 O(1)，因此我们直接使用队列的相关操作就可以实现这两个函数。但是对于实现最大值有另外的理解
解决思路：
只需记住当前最大值出队后，队列里的下一个最大值即可（维护一个最大值的变量）。
具体方法是使用一个双端队列 deque，在每次入队时，如果 deque 队尾元素小于即将入队的元素 value，则将小于 value 的元素全部出队后，再将 value入队；否则直接入队。

https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/solution/jian-zhi-offer-59-ii-dui-lie-de-zui-da-z-0pap/
说实话这一块的理解有点复杂，暂时不准备去管了。

剑指offer61-扑克牌中的顺子

主要是要分析，当有两张大小王的时候，剩下的牌中，最大值与最小值的差值可以为多少的问题？
答案：除了大小王之后的其他的牌的最大值与最小值的差值不能超过4(下面是用的一张图来辅助理解的。有助于加深印象，也是本题的一个关键点)
用一个哈希表：看是否有重复的牌（有重复的肯定不能形成顺子）
根据题意，此 5张牌是顺子的 充分条件 如下：

* 除大小王外，所有牌 无重复 ；
* 设此 5 张牌中最大的牌为 maxcard ，最小的牌为 mincard （大小王除外），则需满足：pythonmax−min<5max - min < 5 max−min<5

要自己来写：

1. hashset+遍历
   1. 遍历5张牌，遇到大小王就直接跳过
   2. 判别重复：利用set实现判重
   3. 或者最大最小的牌（需要借助辅助变量遍历统计得到）
2. 排序之后再比较
   1. 先对数组进行排序
   2. 判别重复，通过遍历数组看nums[i]==nums[i+1]
   3. 获取最大与最小牌

以下分别结合K神的两种解法的代码：

# 采用set集合+遍历的方式
class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        # 看了K神的题解之后自己马上过来实际操作一下
        hashset=set()
        mincard,maxcard=14,0
        for c in nums:
            # 定义两个变量用来记录最大值与最小值，同时如果遇到0（表示是大小王，直接跳过）
            if c==0:
                continue
            # 不断地更新最大牌与最小牌的值
            mincard=min(mincard,c)
            maxcard=max(maxcard,c)

            # 当遍历到c的时候发现重复了，有对子存在，直接返回False
            if c in hashset:
                return False
            # 将元素加入到set集合中
            hashset.add(c)
        # 下面来判定最大值与最小值直接的差值是否小于5
        return maxcard-mincard < 5

# 采用排序+遍历的方式
class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        # 先对数组进行排序
        nums.sort()
        # 用一个数组记录0的个数
        count=0
        for i in range(5):
            if nums[i]==0:
                count+=1
                continue
            if i>0 and nums[i-1]==nums[i]:
                return False
        # 返回最终的结果
        # 因为已经经过了排序，所以最大值一定是最右边的数
        # 0的个数正好就是最小牌对应的下标（非王牌）
        return nums[4]-nums[count]<5

剑指offer62-圆圈中最后剩下的数字

这题没有思路，做不出来？？（主要是没有找到规律）
看题解的之后再好好的整理一下，其实我的写法已经有那么一点接近了
是著名的约瑟环问题，可以采用动态规划的思路来解题
输入n,m，计入问题为
从链表的角度来分析：
假设当前删除的位置的idx，那么下一个要删除的位置是idx+m,由于当前的位置删除了，会往后移动一位，所以实际的下一个位置是：idx+m-1,由于数到末尾会从头继续需要取模：(idx+m-1)%n

从数学的角度来看问题
0 1 2 3 4
第一轮：从0开始的第三个数(总共5个数)，删除2 （原余数的下标）
剩余3 4 0 1
第二轮：从3开始的第三个数(总共4个数)，删除0
剩余 1 3 4
第三轮：从1开始的第三个数(总共3个数)，删除4
剩余 1 3 1 3
第四轮：从1开始的第三个数(总共2个数)，删除1
剩余3

根据分析的结果来反推是如何得到这样的一个3的：虽然自己已经明白了这样的一个过程，但是要我写却依然是无法写出来的
由于最后一定是剩下一个数，所以索引为0，现在反推在上一轮中该数在哪个索引？
（0+3）% 2=1
在这个基础上继续的往上进行反推，当前索引为1的数，在本轮的上一轮中哪个索引？
（1+3）%3=1
在这个基础上继续的往上进行反推，当前索引为1的数，在本轮的上一轮中哪个索引？
（1+3）%4=0
在这个基础上继续的往上进行反推，当前索引为0的数，在本轮的上一轮中哪个索引？
（0+3）%5=2
由于已经到了上一轮剩余的数字的个数为5的情况（等于给定数组的长度），此时不再向上反推，因为此时索引2就为原数组中经过这种方式的删除后剩余的元素：3

这里我又参考了另外的一个人题解：只关心最终活着的那个人的序号变化（感这句话说的非常好，在反推的时候就是在确定这个数的索引变化）
约瑟夫问题：
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。

问题的转化：
https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/

还是用人来举例，给u每个人一个编号（索引值），每个人用字母代替

从8个人开始，每次杀掉一个人，去掉被杀掉的那个人，然后把杀掉的那个人之后的第一个人作为开头重新编号。

1. 第一次C被杀掉，人数变成7，D作为开头（最终活下来的G的编号从6–3）
2. 第二次F被杀掉，人数变成6，G作为开头（最终活下来的G的编号从3–0）
3. 第三次A被杀掉，人数变成5，B作为开头（最终活下来的G的编号从0–3）
4. 第四次E被杀掉，人数变成4，G作为开头（最终活下来的G的编号从3–0）
5. 第五次B被杀掉，人数变成3，D作为开头（最终活下来的G的编号从0–1）
6. 第六次H被杀掉，人数变成2，D作为开头（最终活下来的G的编号从1–1）
7. 第七次D被杀掉，人数变成1，G作为开头（最终活下来的G的编号从1–0）:最终编号肯定是为0，G活下来了。

最终活着的人的编号反推：
知道了G的索引号的变化过程来进行相应的反推过程
从N=7到N=8的过程
先把被杀掉的C补充回来，然后右移动m个人，把溢出的补充在最前面

这里给出一份递归的代码：

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        # 递归的出口
        if n==0:
            return 0
        else:
            return (self.lastRemaining(n-1,m)+m)%n

剑指offer63-股票的最大利润（已经做过的）

见动态规划部分的题解

剑指offer64-1+2 +3+…+n

要求：不能使用乘除法、for while if else switch case等关键字以及条件判断语句（A?B:C）
略