精华内容
下载资源
问答
  • leetcode刷题app 算法冲冲冲!!!!!!!适合后台人员的算法学习!! 1. 后台学习方法 看刘宇波波的三个视频,看你想看的知识点就行,边看边做对应的题目 视频:三个视频的内容在下面的卡片里面!!链接: 提取码...
  • 程序员刷题app排行榜目的 这可以作为结构化指南,指导您如何构建全栈应用程序,以防您迷路或不知道如何开始。 现在,这将在一个非常高级的概述中编写。 这应该是语言不可知的,没有深入研究框架或哪种语言可以优化您...
  • leetcode刷题app 面试 Google 招聘的网上算法试场,一般一场打进前40可能会收到Google的面试邀约 一些常见的工程师面试问题 一个难度比leetcode难的网站,网站不仅仅有算法,还有数学和其他编程语言的锻炼项目。 ...
  • 程序员刷题app有哪些 Android_QA 2020 年 10 月 27 重磅更新: 最真实的 Android 面经,最详细的面试回答,我都给你准备好啦! 几大公司面试问题: 里面都备注了回答要点! 最重要的,遇到这些面试题该如何回答我都...
  • 数据结构与算法刷题汇总

    千次阅读 2019-10-24 08:40:43
    记录自己在leetcode的刷题总结,由于个人水平的限制,错误在所难免,希望有大佬指正。 方法论:分类400+随机高频250 分类400题 数组

    方法:leetcode打基础+剑指Offer针对性训练

    【数据结构】

    数组和字符串是两种最基本的数据结构,它们用连续内存分别存储数字和字符。链表和树是面试中出现频率最高的数据结构。栈是一个与递归紧密相关的数据结构,同样队列也与广度优先遍历算法紧密相关。

    数组✌

    大小固定、内存连续、简单哈希表、动态数组

    【面试题3】(不修改)找出数组中的重复数字

    【面试题4】二维数组中的查找

    字符串✌

    字符组成、常量字符串、数组字符串

    【面试题5】替换空格

    基础

    1. 【13.罗马数字转整数】简单
    2. 【12.整数转罗马数字】中等
    3. 【273.整数转换英文表示】困难

    提高

    1. 【68. 文本左右对齐】困难
    2. 【65.有效数字】困难

    子串

    1. 【76. 最小覆盖子串】困难
    2. 【30. 串联所有单词的子串】困难
    3. 【3. 无重复字符的最长子串】中等
    4. 【395.至少有K个重复字符的最长子串】中等

    回文串

    1. 【125. 验证回文串】
    2. 【5. 最长回文子串】
    3. 【214.最短回文串】
    4. 【336.回文对】
    5. 【131.分割回文串&132.分割回文串Ⅱ】

    括号

    1. 【20.有效的括号】
    2. 【22.括号生成】
    3. 【32.最长有效括号】
    4. 【241.为运算表达式设计优先级】
    5. 【301.删除无效的括号】

    子序列

    1. 【115.不同的子序列】

    链表✌

    面试最频繁、代码量适中、空间效率高、环形链表、双向链表、复杂链表

    1. 【206.反转链表】
    2. 【141.环形链表】
    3. 【24.两两交换链表中的节点】
    4. 【328.奇偶链表】
    5. 【92.反转链表Ⅱ】
    6. 【237.删除链表中的节点】
    7. 【19.删除链表的倒数第N个节点】
    8. 【301.删除无效的括号】
    9. 【203.移除链表元素】
    10. 【83.删除排序链表中的重复元素】
    11. 【82. 删除排序链表中的重复元素 II】
    12. 【160.相交链表】
    13. 【21.合并两个有序链表】
    14. 【143.重排链表】
    15. 【142.环形链表Ⅱ】
    16. 【148.排序链表】
    17. 【25.K个一组翻转链表】
    18. 【61.旋转链表】
    19. 【86.分隔链表】
    20. 【23.合并K个排序链表】
    21. 【147.对链表进行插入排序】

    树✌

    二叉树:前序、中序、后序遍历的递归和迭代写法、层次遍历(宽度优先遍历)、二叉搜索树、堆和红黑树

    【面试题7】重建二叉树】

    【面试题8】二叉树的下一个节点

    遍历基础(递归+迭代)

    1. 【144.二叉树的前序遍历】中等
    2. 【94.二叉树的中序遍历】中等
    3. 【145.二叉树的后序遍历】中等
    4. 【102.二叉树的层次遍历】中等

    遍历的应用

    1. 【100.相同的树】简单
    2. 【101.对称二叉树】简单
    3. 【226.翻转二叉树】
    4. 【257.二叉树的所有路径】
    5. 【112.路径总和】
    6. 【113.路径总和Ⅱ】
    7. 【124.二叉树中的最大路径和】
    8. 【129.求根到叶子节点数字之和】
    9. 【111.二叉树的最小深度】
    10. 【104.二叉树的最大深度】
    11. 【110.平衡二叉树】
    12. 【337.打家劫舍Ⅲ】
    13. 【107.二叉树的层次遍历Ⅱ】
    14. 【103.二叉树的锯齿形层次遍历】
    15. 【199.二叉树的右视图】

    二叉搜索树

    1. 【98.验证二叉搜索树】
    2. 【235.二叉搜索树的最近公共祖先】
    3. 【236.二叉树的最近公共祖先】
    4. 【108.将有序数组转换为二叉搜索树】
    5. 【109.有序链表转换二叉搜索树】
    6. 【173.二叉搜索树迭代器】
    7. 【230.二叉搜索树中第K小的元素】
    8. 【297.二叉树的序列化和反序列化】
    9. 【99.恢复二叉搜索树】
    10. 【116.填充每个节点的下一个右侧节点指针】
    11. 【117.填充每个节点的下一个右侧节点指针Ⅱ】
    12. 【96.不同的二叉搜索树】

    栈&优先队列✌

    栈:后进先出,无序
    队列:先进先出

    【面试题9】用两个栈实现队列

    1. 【155.最小栈】
    2. 【232.用栈实现队列】
    3. 【225.用队列实现栈】
    4. 【150.逆波兰表达式求值】
    5. 【71.简化路径】
    6. 【388.文件的最长绝对路径】
    7. 【394.字符串解码】
    8. 【224.基本计算器】
    9. 【227.基本计算器Ⅱ】
    10. 【385.迷你语法分析器】
    11. 【84.柱状图中最大的矩形】
    12. 【215. 数组中的第K个最大元素】
    13. 【347.前K个高频元素】
    14. 【218.天际线问题】
    15. 【332.重新安排行程】
    16. 【341.扁平化嵌套列表迭代器】

    并查集

    字典树

    矩阵

    【算法】

    一般算法具有递归和循环两种实现方式,递归简洁但性能不佳;排序和查找是重点,需重点掌握二分查找、归并排序和快速排序;二维数组搜索路径,使用回溯法,适合递归实现;求某个问题最优解,该问题可分为多个子问题,使用动态规划,为避免重复计算,使用自下而上的循环代码实现;分解子问题时存在某个特殊选择,且能得到最优解,适用贪婪算法,并证明贪婪算法能够得到最优解;位运算,包括与、或、异或、左移和右移。

    递归和循环

    适用于重复计算多次相同的问题,如无特别要求,优先使用递归写法。
    递归的本质是将一个问题分解为两个或多个小问题,但是其中很多计算可能都是重复的,对性能带来很大影响。

    动态规划解决问题是一般用递归思路分析问题,由于递归分解的子问题中存在大量重复,因此我们用自下而上的循环来实现代码。

    递归可能导致调用栈溢出。

    【面试题10】斐波那契数列

    查找和排序

    查找:顺序查找、二分查找、哈希表查找和二叉排序树查找。

    排序:插入排序、冒泡排序、归并排序、快速排序的特点,从额外空间消耗、平均时间复杂度和最差时间复杂度等方面比较优缺点。

    【面试题11】旋转数组的最小数字

    回溯法

    =蛮力法“升级版”,适合解决多步骤问题,每个步骤有多个选项,适合递归实现。

    将回溯法解决问题的选项用树结构表示,步骤看做为一个节点,选型对应着节点连接线。叶节点不满足约束条件则往上回溯尝试。

    【面试题12】矩阵中的路径

    【面试题13】机器人的运动范围

    动态规划和贪婪算法

    动态规划:求一个问题最优解(通常是最大最小值),该问题能够分解成若干个子问题,且子问题之间还有重叠的更小的子问题。 应用动态规划求解问题的特点:
    一,求一个问题的最优解;
    二,整体问题的最优解依赖各个子问题的最优解;
    三,大问题分解成若干小问题,小问题之间有互相重叠的更小的子问题;
    四,从上往下分析问题,从下往上求解问题。
    贪婪算法:每一步做出一个贪婪的选择,基于这个选择,可以确定能够得到最优解。

    【面试题14】剪绳子

    位运算

    位运算:把数字用二进制表示之后,对每一位上0或1的运算。包括与、或、异或、左移和右移五种运算。
    左移运算符m<<n表示把m左移n位,左边n位丢弃。 右移运算符m>>n表示把m右移n位,右边n位丢弃。
    右移无符号数值,用0填充左边n位;右移有符号数,正数用0填充,负数用1填充左边n位。

    【面试题15】二进制中1的个数

    DFS&BFS

    随机

    数学

    设计

    高质量的代码

    代码的规范性:清晰的书写、清晰的布局和合理的命名。

    代码的完整性:功能测试、边界测试和负面测试。

    优点缺点
    返回值和系统API一致不能方便的使用计算结果
    全局变量能够方便的使用计算结果用户可能会忘记检查全局变量
    异常可以为不同的出错原因定义不同的异常类型有些语言不支持异常,抛出异常时对性能有负面影响

    【面试题17】打印从1到最大的n位数

    【面试题18】删除链表的节点

    【面试题19】正则表达式匹配

    【面试题20】表示数值的字符串

    【面试题21】调整数组顺序是奇数位于偶数前面

    代码的鲁棒性

    鲁棒性指程序能判断输入是否合乎规范要求,并对不符合要求的输入予以合理的处理。
    容错性、防御性编程、

    【面试题22】链表中倒数第k个节点

    【面试题23】链表中环的入口节点

    【面试题24】反转链表

    【面试题25】合并两个排序的链表

    【面试题26】树的子结构

    大多数面试都要求应聘者在白纸或者白板上写代码。应聘者应该在编码的时候注意规范性,尽量清晰的书写每个字母,通过缩进和对其括号让代码布局合理,同时合理命名代码中的变量和函数。
    最好在编码之前全面考虑所有可能的输入,确保写出的代码在完成了基本功能之外,还考虑了边界条件,并做好了错误处理。只有全面考虑到这3个方面的代码才是完整的代码。
    另外,要确保自己写出的程序不会轻易崩溃。平时在写代码的时候,最好养成防御性编程的习惯,在函数入口判断输入是否有效,并对各种无效输入做好相应的处理。

    解决面试题的思路

    画图

    举例

    分解

    展开全文
  • 算法刷题-数据结构

    2020-07-26 17:07:16
    TreeNode) -> TreeNode: if root is None: return root else: self.mirrorTree(root.left) self.mirrorTree(root.right) temp=root.left root.left=root.right root.right=temp return root 1.1.9 是否是子结构 ...

    1.树

    1.1 二叉树

    1.1.1 二叉树的深度

     # Definition for a binary tree node.
     class TreeNode:
         def __init__(self, x):
             self.val = x
             self.left = None
             self.right = None
    
    class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            if not root:
                return 0
            ldepth = Solution.maxDepth(self, root.left)
            rdepth = Solution.maxDepth(self, root.right)
            return max(ldepth, rdepth) + 1
    

    1.1.2 二叉搜索树的第k大节点

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def kthLargest(self, root: TreeNode, k: int) -> int:
            def func(root):
                return func(root.left) +[root.val]+func(root.right) if root else []
    
            return func(root)[-k]
    
    

    1.1.3 二叉树的遍历

    先序遍历
    #递归
    def pre_order(root):
        if not root:
            return []
        return [root.val]+pre_order(root.left)+pre_order(root.right)
    #非递归
    def pre_order(root):
        if not root:
            return 
        stack=[]
        stack.append(root)
        ret=[]
        while stack:
            x=stack.pop()
            ret.append(x.val)
            if x.right:
                stack.append(x.right)
            if x.left:
                stack.append(x.left)
    
    中序遍历
    #递归
    def mid_order(root):
        if not root:
            return []
        return mid_order(root.left)+[root.val]+mid_order(root.right)
    #非递归
    def mid_order(root):
        if not root:
            return 
        stack=[]
        stack.append(root)
        ret=[]
        while stack:
            x=stack.pop()
            if x.right:
                stack.append(x.right)
            ret.append(x.val)
            if x.left:
                stack.append(x.left)
    
    后序遍历
    # 递归
    def post_order(root):
        if not root:
            return []
        return post_order(root.left)+post_order(root.right)+[root.val]
    # 非递归
    def post_order(root):
        if not root:
            return 
        stack=[]
        stack.append(root)
        ret=[]
        while stack:
            x=stack.pop()
            if x.right:
                stack.append(x.right)
            if x.left:
                stack.append(x.left)
            ret.append(x.val)
    
    层次遍历

    不保留空值

    def layer_order(root):
        if not root:
            return 
        stack=[]
        stack.append(root)
        ret=[]
        while stack:
            x=stack.pop()
            if x.right:
                stack.append(x.right)
            if x.left:
                stack.append(x.left)
            ret.append(x.val)
    

    保留空值

    def layer_order(root):
        if not root:
            return 
        stack=[]
        stack.append(root)
        ret=[]
        while any(stack):
            x=stack.pop()
            if x:
                stack.append(x.right)
                stack.append(x.left)
            ret.append(x.val)
    

    1.1.4 二叉树的构建

    按层次遍历构建

    采用层次遍历的结果构建二叉树,结果可能不对着,需要修改

    class TreeNode:
        def __init__(self, x, left, right):
            self.val = x
            self.left = left
            self.right = right
    def reconstruct(data):
        """
        依据层次遍历结果重构二叉树
        :return: 
        """
        if not data:
            return None
        # data = eval(data)
        n = len(data)
        vals, i = data, 1
        root = TreeNode(data[0])
        queue = [root]
        while queue:
            node = queue.pop(0)
            if i >= n: break
            if vals[i] != None:
                node.left = TreeNode(vals[i])
                queue.append(node.left)
            i += 1
            if i >= n: break
            if vals[i] != None:
                node.right = TreeNode(vals[i])
                queue.append(node.right)
            i += 1
        return root
    layer_node = [1, 2, 3, None, 4, 4, 5, None, None, 6, 7, 8]
    ret = reconstruct(layer_node)
    mid = mid_order(ret)
    print(ret)
    
    按先序和中序
    class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
            if not preorder:
                return None
            if preorder:
                root=preorder.pop(0)
                root_idx=inorder.index(root)
                in_left=inorder[:root_idx]
                in_right=inorder[root_idx+1:]
                pre_left=preorder[:len(in_left)]
                pre_right=preorder[len(in_left):]
                return TreeNode(root,self.buildTree(pre_left,in_left),self.buildTree(pre_right,in_right))
    

    1.1.5 二叉树路径求和

    class Solution:
        def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
            def func(root,has,target):
                if not root:return 
                tmp=has+[root.val]#采用临时变量的原因是之后不用再pop一下
                if not root.left and not root.right:
                    # 求和 
                    has_sum=0
                    for i in tmp:
                        has_sum+=i
                    # 判断目标和
                    if has_sum==target:
                        ret.append(tmp)
                        return
                func(root.left,tmp,target)
                func(root.right,tmp,target)
            ret=[]
            func(root,[],sum)
            return ret
    

    1.1.6 判断是否是平衡二叉树

    class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            def depth(root):
                if not root:
                    return 0
                return 1+max(depth(root.left),depth(root.right))
            if not root:
                return True
            if self.isBalanced(root.left) and self.isBalanced(root.right) and abs(depth(root.left)-depth(root.right))<=1: 
                return True
            else:
                return False
    

    1.1.7 对称二叉树

    class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            def depth(root):
                if not root:
                    return 0
                return 1+max(depth(root.left),depth(root.right))
            if not root:
                return True
            if self.isBalanced(root.left) and self.isBalanced(root.right) and abs(depth(root.left)-depth(root.right))<=1: 
                return True
            else:
                return False
    

    1.1.8 二叉树的镜像

    class Solution:
        def mirrorTree(self, root: TreeNode) -> TreeNode:
            if root is None:
                return root
            else:
                self.mirrorTree(root.left)
                self.mirrorTree(root.right)
                temp=root.left
                root.left=root.right
                root.right=temp
                return root
    

    1.1.9 是否是子结构

    class Solution:
        def HasSubtree(self, pRoot1, pRoot2):
            # write code here
            def is_subtree(pRoot1,pRoot2):
                if not pRoot1 and not pRoot2:
                    return True
                if not pRoot1:
                    return False
                if not pRoot2:
                    return True
                if pRoot1.val !=pRoot2.val:
                    return False
                else:
                    return is_subtree(pRoot1.left, pRoot2.left) and is_subtree(pRoot1.right, pRoot2.right)
            if not pRoot1:
                return False
            if not pRoot2:
                return False
            if is_subtree(pRoot1, pRoot2):
                return True
            else:return self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
    

    1.1.10 二叉树的最小深度

    class Solution:
        def minDepth(self, root: TreeNode) -> int:
            if not root:
                return 0
            if not root.left or not root.right:
                return 1+max(self.minDepth(root.left),self.minDepth(root.right))
            else:
                return 1+min(self.minDepth(root.left),self.minDepth(root.right))
    

    1.2 二叉搜索树

    查找

            if not root:return None
            if root.val >val:
                return self.searchBST(root.left,val) 
            elif root.val<val:
                return self.searchBST(root.right,val) 
            else:return root
    

    验证二叉搜索树

    class Solution:
        def isValidBST(self, root: TreeNode) -> bool:
            if not root:
                return True
            # 递归 #需要同时比较左子树和右子树
            def func(root,low=-float("inf"),high=float("inf")):
                if not root:
                    return True
                if low>= root.val or high<=root.val:
                    return False
                else:
                    return func(root.left,low,root.val) and func(root.right,root.val,high)
            return func(root)
    

    2.链表

    2.1 单链表

    2.1.1 删除单链表的某个节点:

    删除中间节点

    class Solution:
        def deleteNode(self,node):
    		"输入仅删除的节点"
            node.val=node.next.val
            node.next=node.next.next
            
    
    class Solution:
        def deleteNode(self, head: ListNode, val: int) -> ListNode:
            if head.val==val:
                return head.next
            p=head
            q=head.next
            while q:
                if q.val != val:
                    p=q
                    q=q.next
                else:
                    p.next=q.next
                    break
            return head
    

    2.1.2 单链表的倒数第k个节点

    双指针

    class Solution:
        def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
            q=p=head
            while k:# q先走k步
                q=q.next
                k-=1
            while q:#p、q一起走,q到终点的时候,p在倒数dik个位置
                p=p.next
                q=q.next
            return p
    

    2.1.3 单链表的插入

    头插法

    class Solution:
        def insert(self, head: ListNode,node: ListNode):
        node.next=head.next
        head.next=node    
    

    尾插法

    class Solution:
        def insert(self, head: ListNode,node: ListNode):
        p=head
        q=head.next
        while q:
        	p=q
        	q=q.next
        q.next=node
        return head
    

    2.1.4 单链表的逆序

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            ret=None
            while head:
                p=head.next# head的下一个节点
                #头插
                head.next=ret
                ret=head
                #head 指向原来head的下一个
                head=p
            return ret
    

    2.1.5 删除单链表中重复元素

    class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            if not head:
                return None
            p=head
            while p:
                if p.next and p.val==p.next.val:
                    p.next=p.next.next
                else: p=p.next
            return head
    

    3.图

    3.1 有向图

    3.1.1 拓扑排序

    leetcode 中的例题:210. 课程表 II

    
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            """
            :type numCourses: int 课程门数
            :type prerequisites: List[List[int]] 课程之间的次序关系
            """
            # 入度表
            rudus = {num: [] for num in range(numCourses)}
            for cur, pre in prerequisites:
                rudus[cur].append(pre)
            chudus = {num: [] for num in range(numCourses)}
            for cur, pre in prerequisites:
                chudus[pre].append(cur)
    
            # 先判断是否有环 判断拓扑排序是否有环
            def dfs(course):
                states[course] = 1
                for next_course in chudus[course]:
                    if states[next_course] == 1:  # 找见了环
                        return False
                    elif states[next_course] == 0:# 继续
                        if not dfs(next_course): return False
                states[course] = 2
                return True
    
            for course in range(numCourses):
                states = [0 for _ in range(numCourses)]
                if not dfs(course):
                    return []
            visited = [True for _ in range(numCourses)]
            ret = []
            while any(visited):
                for cur_course in rudus.keys():
                    if not rudus[cur_course] and visited[cur_course]:  # 当该节点没有前置的时候
                        visited[cur_course] = False
                        ret.append(cur_course)
                        for pre_course in rudus.keys():  # 在其余的节点里删除前置
                            if pre_course == cur_course:
                                continue
                            if cur_course in rudus[pre_course]:
                                rudus[pre_course].remove(cur_course)
            return ret
    
    展开全文
  • 链表专栏1. 递归反转链表1.1 题目描述1.2 解题思路1. 递归反转整个链表2. 递归反转链表前n个节点3....首先熟悉一些链表结构: // 单链表节点的结构 public class ListNode { int val; ListNode next; List

    原文地址:https://labuladong.github.io/algo/2/18/17/

    1. 递归反转链表

    本部分从部分反转链表这一题目入手,可能这一问题迭代实现很简单但是递归实现你是否会呢?首先熟悉一些链表结构:

    // 单链表节点的结构
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    
    

    1.1 题目描述

    给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

    输入
    head = [1,2,3,4,5], left = 2, right = 4

    输出
    [1,4,3,2,5]

    示例
    在这里插入图片描述

    1.2 解题思路

    1. 递归反转整个链表

    代码框架

    ListNode reverse(ListNode head) {
        if (head.next == null) return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
    
    

    递归算法最重要的是明确递归含义。
    定义reverse:输入一个节点 head,将以 head 为起点的链表反转,并返回反转之后的头结点。如下图所示:

    ListNode last = reverse(head.next);
    

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    现在再来看下面的代码:

    head.next.next = head;
    

    在这里插入图片描述
    接下来:

    head.next = null;
    return last;
    

    在这里插入图片描述

    base case

    if (head.next == null) return head;
    

    意思是如果链表只有一个节点的时候反转也是它自己,直接返回即可。

    注意!
    别忘了末尾指向null

    2. 递归反转链表前n个节点

    只需要把之前框架改一遍
    代码框架

    ListNode successor = null; // 后驱节点
    
    // 反转以 head 为起点的 n 个节点,返回新的头结点
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) { 
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点,需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);
    
        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }    12
    

    base case:n==1的时候就是只反转头结点,那么返回的就是它本身,与此同时记录后驱节点。
    successor:反转整个链表head就是最后一个节点,这边反转前n个,head就该指向第n+1个节点

    3. 递归反转链表的一部分

    代码框架

    ListNode reverseBetween(ListNode head, int m, int n) {
        // base case
        if (m == 1) {
            return reverseN(head, n);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }
    
    

    base case:m==1就相当于反转两边前n个节点。
    递归思想:如果我们把 head的索引视为 1,那么是从第 m 个元素开始反转;如果把 head.next 的索引视为 1 呢?那么相对于 head.next,反转的区间应该是从第 m - 1 个元素开始的;
    千万不要跳进递归!关注递归结果。

    2. K个一组翻转链表

    使用迭代的方式反转链表

    2.1 题目描述

    给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

    k 是一个正整数,它的值小于或等于链表的长度。

    如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

    进阶:

    • 你可以设计一个只使用常数额外空间的算法来解决此问题吗?
    • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

    输入
    head = [1,2,3,4,5], k = 2

    输出
    [2,1,4,3,5]

    示例
    在这里插入图片描述

    2.2 解决思路

    链表是兼具递归和迭代性质的数据结构,该问题具有递归性质。

    假如对这个链表调用 reverseKGroup(head, 2),即以 2 个节点为一组反转链表,结果如下图所示:
    在这里插入图片描述
    对于后面节点的处理:后面的节点也是链表,但是长度比原链表小,这就是子问题,这就有了如下算法流程。

    1.算法流程

    • 先反转以 head 开头的 k 个元素。
    • 将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。
    • 将上述两个过程的结果连接起来。
    • base case:如果最后的元素不足 k 个,就保持不变。

    2. 代码实现

    • 先用迭代的思想实现以a为头节点到节点b之间的链表的反转。
    • 然后按之前的逻辑递归调用reverseKGroup 函数即可
    public class reverseKlink {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(head==null)
                return null;
            //先找到区间a,b
            ListNode b = head;
            for(int i=0;i<k;i++){
                //base case,不足 k 个,不需要反转
                if(b==null){
                    return head;
                }
                b = b.next;
            }
            ListNode a = head;
            //反转区间链表
            ListNode nexthead = reverseN(a,b);
            // 递归反转后续链表并连接起来
            a.next = reverseKGroup(b,k);
            return nexthead;
    
        }
        //反转区间a,b元素
        public ListNode reverseN(ListNode a,ListNode b){
            ListNode pre = null,cur = a,nxt = null;
            while(cur!=b){
                nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            return pre;
        }
    }
    

    下图解释了for循环之后的几句代码:
    在这里插入图片描述

    3. 判断回文链表

    3.1 题目描述

    输入
    1->2

    输出
    false

    3.2 解题思路

    1. 判断回文单链表

    判断回文字符串的思想很简单,只需要「双指针技巧」,从两端向中间逼近即可:

    bool isPalindrome(string s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            if (s[left] != s[right])
                return false;
            left++; right--;
        }
        return true;
    }
    

    下面考虑,输入一个单链表的头结点,判断这个链表中的数字是不是回文。因为单链表是不可以反向遍历的所以不能用双指针。但其实可以用二叉树后序遍历的思想来完成链表的反序遍历。因为链表是具有递归性质的数据结构,二叉树是递归的衍生。

    /* 倒序打印单链表中的元素值 */
    void traverse(ListNode head) {
        if (head == null) return;
        traverse(head.next);
        // 后序遍历代码
        print(head.val);
    }
    
    

    所以可以使用后序遍历模仿实现回文判断的功能:

    // 左侧指针
    ListNode left;
    
    boolean isPalindrome(ListNode head) {
        left = head;
        return traverse(head);
    }
    
    boolean traverse(ListNode right) {
        if (right == null) return true;
        boolean res = traverse(right.next);
        // 后序遍历代码
        res = res && (right.val == left.val);
        left = left.next;
        return res;
    }
    
    

    实际上就是把链表节点放入一个栈,然后再拿出来,这时候元素顺序就是反的,只不过我们利用的是递归函数的堆栈而已。

    2. 优化空间复杂度

    上面算法思想空间复杂度是O(n)。思路:

    1. 通过「双指针技巧」中的快慢指针来找到链表的中点:
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // slow 指针现在指向链表中点
    //如果fast指针没有指向null,说明链表长度为奇数,slow还要再前进一步
    if (fast != null)
        slow = slow.next;
    
    1. slow开始反转后面的链表,就可以开始比较回文串了。
      在这里插入图片描述

    2. 如果想恢复链表的链式结构,可以在比较完了之后,return之前加一行:

    left.next = reverse(right);
    

    3. 代码实现

    public class ispalindrome {
        ListNode left;
        public boolean isPalindrome(ListNode head) {
            //后续遍历
    //        left = head;
    //        return traverse(head);
    
            //优化空间复杂度
            left = head;
            ListNode slow = head,fast = head;
            //使用快慢指针找中点,slow走一步时fast走两步
            while (fast!=null&&fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
            }
            //slow指向链表中点
            if(fast!=null)
                slow = slow.next;
            ListNode right = reverse(slow);
            while (right!=null){
                if(left.val!=right.val)
                    return false;
                left = left.next;
                right = right.next;
            }
            return true;
    
        }
        public boolean traverse(ListNode right){
            if(right==null) return true;
            boolean res = traverse(right.next);
            res = res && (left.val==right.val);
            left = left.next;
            return res;
        }
        //优化空间复杂度
        public ListNode reverse(ListNode head){
            ListNode cur,pre,nxt;
            cur = head;
            pre = null;
            while (cur!=null){
                nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            return pre;
        }
    }
    
    展开全文
  • 数组刷题 485. 最大连续1的个数 算法思想:1.从头开始遍历,设置table = 0表示连续个数为0,max为最大连续个数为0 2.当遇到1时table++,当遇到非1元素时比较table与max的值,将max更新并将table置零 3.最长的连续个...

    数组的遍历

    485. 最大连续1的个数
    在这里插入图片描述

    算法思想:
    1.从头开始遍历,设置table = 0表示连续个数为0,max为最大连续个数为0
    2.当遇到1时table++,当遇到非1元素时比较table与max的值,将max更新并将table置零
    3.最长的连续个数有可能在最后一段,则需要对结尾处进行特殊判断

    int findMaxConsecutiveOnes(int* nums, int numsSize){
    
        int table = 0, max = 0;
        for(int i = 0; i < numsSize; i++)
        {
            if(nums[i] == 1) //当遇到1时table++,当遇到非1元素时比较table与max的值,将max更新并将table置零
                table++;
            else
            {
                if(table > max)
                    max = table;
                    table = 0;   
            }
        }
        if(table > max)
            max = table;
        return max;
    }
    

    495. 提莫攻击
    在这里插入图片描述

    算法思想:
    1.初始判断空集,然后将从数组第一个元素开始遍历,sum初始化为duration的值
    2.动态转移方程为 sum += min(nums[i] - nums[i - 1], duration)
    3.返回sum即可

    int findPoisonedDuration(int* nums, int numSizes, int duration){
    
        if(numSizes == 0)
            return 0;
        int sum = duration;
        for(int i = 1; i < numSizes; i++)
        {
            if(nums[i] - nums[i - 1] < duration) //合并区间,选择更小的进行合并
                sum += nums[i] - nums[i - 1];
            else
                sum += duration;
        }
        return sum;
    }
    

    414. 第三大的数

    给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

    算法思想:
    1.设置数组max[3]用于保存前三大的值,初始化为LONG_MIN意为最小值
    2.遍历数组对前三大的值进行更新
    3.判断max[2]是否存在,若不存在直接返回max[0]

    int thirdMax(int* nums, int numsSize){
        long max[3] = {LONG_MIN,LONG_MIN,LONG_MIN}; //max数组保存前三大的数字,依次递减
        for(int i = 0; i < numsSize; i++)
        {
            if(nums[i] > max[0]) //比最大值还大
            {
                max[2] = max[1];
                max[1] = max[0];
                max[0] = nums[i];
            }
            else if(nums[i] < max[0] && nums[i] > max[1])   //比第二大的值大
            {
                max[2] = max[1];
                max[1] = nums[i];
            }
            else  if(nums[i] < max[1] && nums[i] > max[2])  //比第三大的值大
            {
                max[2] = nums[i];
            }
        }
        if(max[2] != LONG_MIN)  //若存在第三大的数
            return max[2];
        return max[0];
    }
    

    628. 三个数的最大乘积
    在这里插入图片描述

    算法思想:1.初始化设置数组max,min用于标记三个最大值和两个最小值
    2.遍历整个数组,更新max和min
    3.最大值直接为max三个数相乘或者min两个数乘max最大的数中产生
    原因在于若数组中存在三个及以上正数,那么三个最大值就是max数组三个数相乘,若正数个数小于三,那么max中至少有一个小于0,最大值就变成了max中最大的与min中两个最小的相乘

    int maximumProduct(int* nums, int numsSize){
        int max[3]={INT_MIN,INT_MIN,INT_MIN};
    	int min[2]= {INT_MAX,INT_MAX};
    	for (int i = 0; i < numsSize; i++)
    	{
    		if (nums[i] > max[0]) {
    			max[2] = max[1];
    			max[1] = max[0];
    			max[0] = nums[i];
    		}
    		else if (nums[i] > max[1]) {
    			max[2] = max[1];
    			max[1] = nums[i];
    		}
    		else if (nums[i] > max[2]) {
    			max[2] = nums[i];
    		}
    
    		if (nums[i] < min[0]) {
    			min[1] = min[0];
    			min[0] = nums[i];
    		}
    		else if (nums[i] < min[1]) {
    			min[1] = nums[i];
    		}
    	}
    	int result_1 = max[0] * max[1] * max[2];
    	int result_2 = max[0] * min[0] * min[1];
    	return result_1 > result_2 ? result_1 : result_2;
    
    }
    

    统计数组中的元素

    645. 错误的集合

    在这里插入图片描述

    算法思想:
    1.创建bool类型的hashtable用于判断数组中元素是否重复出现,初始化为false
    2.遍历数组,寻找重复的元素,若该元素没被标记过,则将其设置为true表示已经标记,若该元素已经被标记过,说明已经找到重复元素
    3.遍历hashtable,寻找未被标记的元素

    int* findErrorNums(int* nums, int numsSize, int* returnSize){
        bool hashtable[numsSize+1];
        for(int i = 1; i < numsSize+1; i++)
            hashtable[i] =false;
        int* target = (int*)malloc(sizeof(int)*2);  //返回数组
        for(int i = 0; i < numsSize; i++)
        {
            if(hashtable[nums[i]] == false)     //遍历整个数组,若该元素没被标记过,则将其设置为true表示已经标记
                hashtable[nums[i]] = true;
            else
                target[0] = nums[i];            //若已经被访问,则已经找到重复元素
        }
        for(int i = 1; i <= numsSize; i++)      //遍历数组寻找缺少的元素
            if(hashtable[i] == false)
                target[1] = i;
        *returnSize = 2;             
        return target;
    }
    

    697. 数组的度
    在这里插入图片描述

    算法思想:
    1.创建三个哈希表count,left,right分别用于记录元素出现的个数,该元素第一次出现的位置,最后一次出现的位置,degree设置为0
    2.遍历数组,当前元素为x,count[x]计数器加一,若该元素未出现过,则left[x]置为该元素下标(只执行一次),right[x]置为该元素下标
    (无限次执行覆盖),同时更新degree
    3.初始化最短连续长度length为numSizes,在count中寻找出现次数等于degree的元素,length = min(length,right[x]-left[x]+1)

    int min(int a, int b)
    {
        return a < b ? a:b;
    }
    int findShortestSubArray(int* nums, int numsSize){
        int count[50000] = {0},left[50000]={-1},right[50000]={0};
        int degree = 0, length = numsSize;
        for(int i = 0; i < numsSize; i++)
        {
            count[nums[i]]++;
            if(count[nums[i]] > degree)		//更新最大的入度
                degree = count[nums[i]];
            if(count[nums[i]] == 1)			//若是第一次出现
            {
                left[nums[i]] = i;
            }
            right[nums[i]] = i;
        }
        for(int i = 0; i < 50000; i++)
        {
            if(count[i] == degree)			//寻找出现次数等于度的元素
                length = min(length,right[i]-left[i]+1);
        }
        return length;
    }
    

    448. 找到所有数组中消失的数字
    在这里插入图片描述

    算法思想:
    > 一:使用额外辅助空间哈希表
    1.设置bool型hashtable用于统计当前元素是否出现过
    2.遍历数组更新hashtable,遍历结束后hashtable为false的元素即为未出现的元素
    > 二:不使用额外辅助空间
    1.遍历数组,若下标为abs([nums[i])-1的元素为正数,那么将其置为负数
    2.扫描数组中不为负数的值,下标+1即为未出现的元素

    方法一:哈希表法
    int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
        int* result = (int*)malloc(sizeof(int)*numsSize);
        int num = 0;//返回数组元素的个数
        bool hashtable[numsSize+1];	//创建哈希表
        for(int i = 1; i < numsSize + 1; i++)
            hashtable[i] = false;	//初始化全置为false
        for(int i = 0; i < numsSize; i++)	//遍历哈希表,将访问过的元素置为true
            hashtable[nums[i]] = true;
        for(int i = 1; i < numsSize + 1; i++)
            if(hashtable[i] == false)	//将未访问过的元素加入数组
                result[num++] = i;
        *returnSize = num;
        return result;
    }
    方法二:
    int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
        int* result = (int*)malloc(sizeof(int)*numsSize);
        int num = 0;
        for(int i = 0; i < numsSize; i++)
        {
            int temp = abs(nums[i]) - 1;
            if(nums[temp] > 0)
            {
                nums[temp] *= -1;
            }
        }
        for(int i = 0; i < numsSize; i++)
        {
            if(nums[i] > 0)
                result[num++] = i+1;
        }
        *returnSize = num;
        return result;
    }
    

    相同方法题目
    442. 数组中重复的数据 41.缺失的第一个正数
    个人理解:这种思想应该叫做原地哈希,一般来说,元素的值顺序是从1-n,可以通过将该元素值对应下标变更为负值/交换数据将其放置对应位置的两种方法对其标记,再次遍历数组,出现正值的元素即为第一个元素的下标。

    41题交换版本算法
    void swap(int* a,int* b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    int firstMissingPositive(int* nums, int numsSize){
    
        for(int i = 0; i < numsSize; i++)
        {
            while(nums[i] < numsSize && nums[i] > 0 && nums[i] != nums[nums[i] - 1])
            {
                swap(&nums[i],&nums[nums[i]-1]);
            }
        }
        for(int i = 0; i < numsSize; i++)
        {
            if(nums[i] != i+1)
                return i+1;
        }
        return numsSize+1;
    }
    

    数组的改变、移动

    453. 最小移动次数使数组元素相等
    在这里插入图片描述

    算法思想:
    设n个元素的数组中的最小值为min,最终结果为x,元素总和为sum
    那么一共需要加x-min次,最小值可以变成k
    执行的x-min次中,每次共计n-1个元素需要增加1,因此得出方程式
    x-min次中所有元素增加的值 = 最终的和 - 初始和
    (x-min) * (n-1) = x * n - sum
    解得 x = sum - (n-1)*min
    返回x-min即为执行次数

    int minMoves(int* nums, int n){
        if(n == 0)
            return 0;
        double min= nums[0];
        double sum = 0;
        for(int i = 0; i < n; i++)
        {
            if(nums[i] < min)
            {
                min = nums[i];   //更新最小值
            }
            sum = sum + nums[i];
        }
        double k = sum - (n-1) * min;
        return (int)k - min;
    }
    

    665. 非递减数列
    在这里插入图片描述

    算法思想:
    1.设置标志flag = 0表示未出现反序数字
    2.从第1个元素开始遍历到第n-1个元素,若当前元素大于下一个元素,则将flag置为1,若flag已经为1,则返回false
    3.需要判定特殊情况,以3423为例,4 > 2,两种选择,增大2或者减小4,还需要保证2之后的元素大于4或4之前的元素小于2,但若修改元素2使其>4,但3<2,不满足非递减要求,修改元素4使其<2,但3>2则不满足非递减要求

    bool checkPossibility(int* nums, int n){
        if(n <= 2)
            return true;
        int flag = 0;
        for(int i = 0; i < n - 1; i++)
        {
            if(nums[i] > nums[i+1]) //若出现反序数字
            {
                if(i + 2 < n && i - 1 >= 0) //边界
                {
                    if(nums[i+2] < nums[i] && nums[i-1] > nums[i+1])	//若出现了特殊情况
                        return false;
                }
                if(flag == 0)
                    flag = 1;
                else
                    return false;
            }
        }
        return true;
    }
    

    **

    二维数组及滚动数组

    118. 杨辉三角(经典算法建议百度)

    算法思想:1.创建二维数组result保存结果,返回的数组个数为returnSize=numRows,returnColumnSizes[i]为i+1
    2.共计创建numRows行,每行第一个和最后一个置为为1,从第二行开始有
    等式result[i][j] = result[i - 1][j] + result[i-1][j-1];

    int** generate(int numRows, int* returnSize, int** returnColumnSizes){
        int** result = (int**)malloc(sizeof(int*)*numRows);
        *returnSize = numRows;//返回的行数
    	*returnColumnSizes = (int *)malloc(sizeof(int)*numRows);//用来储存每一行的大小
        for(int i = 0; i < numRows; i++)
        {
            (*returnColumnSizes)[i] = i+1;      //注意此处一定要写成带括号的
            result[i] = (int*)malloc(sizeof(int)*(i+1));
            result[i][0] = 1;	//第一个元素置为1
            for(int j = i-1; j > 0; j--)	//前两行不执行,从后向前赋值,也可从前向后
            {
                result[i][j] = result[i - 1][j] + result[i-1][j-1];
            }
            result[i][i] = 1;				//最后一个元素置为1
        }
        return result;
    }
    

    119. 杨辉三角 II
    给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

    算法思想:
    1.由于算法只要求第k行,因此只需创建一个大小为k+1的数组(参考用例中给的k为3,返回的实际上是第4行)
    2.由等式result[j] = result[j] + result[j-1]

    int* getRow(int n, int* returnSize){
        int* result = (int*)malloc(sizeof(int)*(n+1));
        *returnSize = n+1;
        for(int i = 0; i <= n; i++)
        {
            for(int j = i - 1; j > 0; j--)
            {
                result[j] = result[j] + result[j-1];
            }
            result[i] = 1;
        }
        return result;
    }
    

    661. 图片平滑器
    在这里插入图片描述

    算法思想:暴力求解,从第一个结点开始,统计附近八个元素的值,只要位置合法即统计
    int average (int** M, int MSize, int *MColSize, int x, int y) //用于计算附近八个元素的值,MSize为数组的行数,*MColSize为数组的列数
    {
        int sum = 0,count = 0;
        for(int i = x-1; i <= x+1; i++)
        {
            for(int j = y-1; j <= y+1; j++)
                if(i >= 0 && i < MSize && j >= 0 && j < *MColSize)
                {
                    sum += M[i][j];
                    count++;
                }
        }
        return sum/count;
    }
    int** imageSmoother(int** M, int MSize, int* MColSize, int* returnSize, int** returnColumnSizes){
        *returnSize = MSize;
        *returnColumnSizes = (int*)malloc(sizeof(int) * MSize);
        int** result = (int**)malloc(sizeof(int*) * MSize);
        for(int i = 0; i < MSize; i++)
        {
            result[i] = (int*)malloc(*MColSize * sizeof(int));
            (*returnColumnSizes)[i] = *MColSize;
        }
        for(int i = 0; i < MSize; i++)
            for(int j = 0; j < *MColSize; j++)
            {
                result[i][j] = average(M,MSize,MColSize,i,j);
            }
        return result;
    }
    

    类似题型289.生命游戏

    189. 旋转数组
    在这里插入图片描述

    算法思想:
    1.元素向右移动k个位置,相当于前n-k个元素与后k个元素交换位置,因此相当于将一个长度为n的数组,前k个元素与前n-k个元素交换
    2.先对整个数组逆置,再对前k个元素逆置,再对后n-k个元素逆置,即可获得正确结果

    void reverse(int* nums, int left, int right)
    {
        for(int i = left; i < (left+right) / 2; i++)
        {
            int temp = nums[i];
            nums[i] = nums[right - (i - left) - 1];
            nums[right - (i - left) - 1] = temp;
        }
    }
    void rotate(int* nums, int numsSize, int k){
        if (numsSize == k || numsSize == 1 || k == 0) return;
        if (numsSize < k) k %= numsSize;
        reverse(nums,0,numsSize);
        reverse(nums,0,k);
        reverse(nums,k,numsSize);
    }
    

    396. 旋转函数
    在这里插入图片描述
    在这里插入图片描述

    int maxRotateFunction(int* nums, int n){
        double f0 = 0, sum = 0,max,temp;
        for(int i = 0; i < n; i++)
        {
            f0 += i * nums[i];
            sum += nums[i];
        }
        max = f0;
        double f1 = f0;
        for(int i = 1; i <= n; i++)
        {   
            temp = f1 - n * (double)nums[n - i] + sum;
            f1 =temp;
            if(temp > max)
                max = temp;
        }
        return (int)max;
    }
    

    238. 除自身以外数组的乘积
    在这里插入图片描述

    算法思想:
    1.除当前元素外所有元素的乘积等于左边所有元素的乘积 * 右边所有元素的乘积
    2.第一趟从左到右遍历,k初始化为1,每次更新都乘以nums[i] 表示包括该元素的乘积,从左到右求出每个元素左边的积,第二趟从右到左遍历,k初始化为1,每次更新都乘以nums[i],表示包括该元素的乘积,从右到左将每个左积再向右乘一次

    int* productExceptSelf(int* nums, int numsSize, int* returnSize){
        if(numsSize == 0)	
        {
            *returnSize = 0;
            return nums;
        }
        int* result = (int*)malloc(sizeof(int) * numsSize);
        *returnSize = numsSize;
        int k = 1;
        for(int i = 0; i < numsSize; i++)	//求出不包含该元素在内的左侧所有元素的乘积
        {
            result[i] = k;
            k *= nums[i]; 
        }
        k = 1;
        for(int i = numsSize - 1; i >= 0; i--)	//求出不包含该元素在内所有右侧元素的乘积 同时与左侧相乘
        {
            result[i] *= k;
            k *= nums[i];
        }
        return result;
    }
    

    240. 螺旋矩阵
    55.

    算法思想与螺旋矩阵赋值相同,但不需要对矩阵进行修改,设置level表示当前遍历的第几层,修改层数即可实现

    int* spiralOrder(int** a, int matrixSize, int* matrixColSize, int* returnSize){
        if (matrixSize == 0) {
            *returnSize = 0; return 0;
        }
        int i = 0, j = 0;
    	int count = 0, level = 0;
        *returnSize = matrixSize * (* matrixColSize);
        int* result = (int*)malloc(sizeof(int) * (*returnSize));
        
        while(count < (*returnSize))
        {
            while(j <= (*matrixColSize) - level - 1)   //向右走
                result[count++] = a[i][j++];
            i++; j--;   //向左下移动
            while(i <= matrixSize - level - 1)       //向下走
                result[count++] = a[i++][j];
            i--;j--;    //向左上移动
            if (count == *returnSize) break;    //需要额外判断是否为非矩形
            while(j >= level)                    //向左走
                result[count++] = a[i][j--];
            level++;                            //此时层数需要更新
            i--;j++;    // 向右上移动               
            while(i >= level)                    //向上走
                result[count++] = a[i--][j];
            i++;j++;    //向右下移动
        }
            return result;
    }
    

    同类型题59. 螺旋矩阵 II

    498. 对角线遍历
    在这里插入图片描述

    算法思想:设元素下标为x,y,共计k趟 (k = m+n-1)
    1.观察题目可知,对角线中元素特点 第一趟 x+y=0 第二趟 x+y=1 第n趟 x+y=n-1 因此根据横坐标x可以得出纵坐标y坐标
    2.前m趟中 x的坐标为执行的趟数
    3.奇数趟中 每次执行过程为:趟数小于m时 x等于趟数 趟数大于m时 x等于m-1 向上移动过程为x-- y++
    判断条件为 x>=0 且 y < n
    偶数趟中 每次执行过程为:趟数小于n时 y等于趟数 趟数大于n时 y等于n-1 向上移动过程为x++ y–
    判断条件为 x<m 且 y >= 0
    每次执行完成后都需要对趟数进行加一 在奇数行时需要提前判断是否已经到了num趟,以免越界

    int* findDiagonalOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
        if(matrixSize == 0 || *matrixColSize == 0)
        {
            *returnSize = 0;
            return 0;
        }
    
        *returnSize = matrixSize* (*matrixColSize);
        int* result = (int*)malloc(sizeof(int) * (*returnSize));
        int k = 0, x, y, num = 0;
        int m = matrixSize, n = *matrixColSize;
        while(k < m+n)
        {
            x = k < m ? k : m-1; //趟数小于m时 x等于趟数  趟数大于m时 x等于m-1
            y = k - x;
            while(x >= 0 && y < n)
            {
                result[num++] = matrix[x][y];
                x--;
                y++;
            }
            k++;
            if(k == m+n) break;
            y = k < n ? k : n-1; //趟数小于n时 y等于趟数  趟数大于n时 y等于n-1
            x = k - y;
            while(x < m && y >= 0)
            {
                result[num++] = matrix[x][y];
                x++;
                y--;
            }
            k++;
        }
        return result;
    }
    

    二维矩阵变换

    566. 重塑矩阵
    在这里插入图片描述
    在这里插入图片描述

    算法思想:
    1.阅读理解题,首先判断是否满足新矩阵的行列积是否等于原矩阵的行列积,若不是则返回原矩阵
    2.创建新的矩阵 遍历整个原数组,设置 k表示 新矩阵的行下标 l表示新矩阵的列下标 先将遍历到的元素复制给新数组 同时将新数组的下标更新(更新方式为l++,当l等于新数组的列c时,将l置为0,k++)

    int** matrixReshape(int** nums, int numsSize, int* numsColSize, int r, int c, int* returnSize, int** returnColumnSizes){
        if(r * c != numsSize * (*numsColSize)  )
        {
            *returnSize = numsSize;
            *returnColumnSizes = (int*)malloc(sizeof(int) * numsSize);
            for(int i = 0; i < numsSize; i++)
                (*returnColumnSizes)[i] = *numsColSize;
            return nums;
        }
        int** result = (int**)malloc(sizeof(int*) * r);
        *returnColumnSizes = (int*)malloc(sizeof(int) * r);
        *returnSize = r;
        for(int i = 0; i < r; i++)
        {
            (*returnColumnSizes)[i] = c;
            result[i] = (int*)malloc(sizeof(int) * c);
        }
        int k = 0, l = 0; //k和l用于表示结果数组的行列数
        for(int i = 0; i < numsSize; i++)
            for(int j = 0; j < *numsColSize; j++)
            {
                result[k][l] = nums[i][j];
                l++;
                if(l == c)
                {
                    k++;
                    l = 0;
                }
            }
        return result;
    }
    

    48. 旋转图像
    在这里插入图片描述
    在这里插入图片描述

    算法思想:
    1.可以将矩阵旋转视作是四个小方块交换元素,设置(pos1,pos1)为当前旋转矩阵的左上角的坐标,(pos1,pos2)为右上角的坐标,(pos2,pos1)为左下角坐标,(pos2,pos2)为右下角坐标,add为坐标偏移量
    2.当pos1等于pos2时,说明当前只有一个元素则无需旋转,否则将对四个小方块进行交换元素,add初始化为0,每执行一次,add++,共偏移pos2-pos1-1步
    3.每执行完一次,将矩阵缩小一格(pos1++,po2–)

     void rotate(int** a, int matrixSize, int* matrixColSize){
        if(matrixSize == 0)
            return;
        int pos1 = 0,pos2 = matrixSize - 1;
        int add,temp;
        while(pos1 < pos2)
        {
            add = 0;//初始化偏移量为0
            while(add < pos2 - pos1)
            {
                temp = a[pos1][pos1 + add];             //画图理解
                a[pos1][pos1 + add] = a[pos2-add][pos1];
                a[pos2-add][pos1] = a[pos2][pos2-add];
                a[pos2][pos2-add] = a[pos1+add][pos2];
                a[pos1+add][pos2] = temp;
                add++;
            } 
            pos1++;
            pos2--;
        }
    }
    

    73. 矩阵置零
    在这里插入图片描述

    算法思想:
    1.由于题目要求O(1)时间复杂度,因此我们可以通过遍历二维数组,每当遇到0元素时,就立即把该行第一个元素和该列第一个元素置为0,同时设置bool型变量row0和col0表示第一行和第一列是否有0
    2.遍历除第一行外的整个二维数组,对遍历到的每个元素进行判断,若对应的第一行或第一列为0则将其置为0,同时判断第一行第一列是否为0
    题外话:吉大答案版本为开额外空间的flag_r[m],flag_c[n]的算法,当遇到0时,将flag_r[num[i]]和flag_c[num[i]]置为true,最后将遍历flag置零

    void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
        bool row0 = false, col0 = false;
        for(int i = 0; i < matrixSize; i++)
            for(int j = 0; j < *matrixColSize; j++)
            {
                if(matrix[i][j] == 0)
                {
                    if(i == 0)	//判断第一行是否有0元素
                        row0 = true;
                    if(j == 0)	//判断第一列是否有0元素
                        col0 = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        for(int i = 1; i < matrixSize; i++) //遍历二维数组
            for(int j = 1; j < *matrixColSize; j++) //
            {
                if(matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        if(col0)
            for(int i = 0; i < matrixSize; i++)
                matrix[i][0] = 0;
        if(row0)
            for(int i = 0; i < *matrixColSize; i++)
                matrix[0][i] = 0;
    }
    

    双指针(滑动窗口)

    345. 反转字符串中的元音字母
    在这里插入图片描述

    算法思想:双指针思想,设置指向表头的指针i和指向表尾的指针j,当表头表尾指针未相遇时执行
    1.i向右寻找第一个元音字母
    2.j向左寻找第一个原因字母
    3.若i与j未相遇则交换二者数据

    bool isvovel(char word)
    {
        if(word == 'A' || word == 'E' || word == 'I' || word == 'O' || word == 'U')
            return true;
        if(word == 'a' || word == 'e' || word == 'i' || word == 'o' || word == 'u')
            return true;
        return false;
    }  
    char * reverseVowels(char * s){
        int len = strlen(s);
        if(len <= 1)
            return s;
        int i = 0, j = len - 1;
        while(i < j)
        {
            while(i < j && (!isvovel(s[i])))  i++;
            while(i < j && (!isvovel(s[j])))  j--;
            if(i < j)
            {
                char temp = s[i];
                s[i] = s[j];
                s[j] = temp;
                i++;
                j--;
            }
        }
        return s;
    }
    

    11. 盛最多水的容器
    在这里插入图片描述

    算法思想:双指针
    1.设置双指针i,j分别指向表头和表尾,初始化面积为表头和表尾,初始化最大面积为0
    2.计算此时的面积area,然后将area与maxarea比较,若大于area则更新,同时比较两个指针的值,移动较小的,缩小容器底部的长度
    3.重复过程2,直至二者相遇

    int min(int a, int b)
    {
        return a < b ? a : b;
    }
    int maxArea(int* height, int heightSize){
        int i = 0, j = heightSize - 1, maxArea = 0;
        while(i < j)
        {
            int area = (j - i) * min(height[i], height[j]);
            if(area > maxArea)
                maxArea = area;
            if(height[i] < height[j])
                i++;
            else
                j--;
        }
        return maxArea;
    }
    

    27. 移除元素
    在这里插入图片描述

    算法思想:双指针
    1.设置指针i为工作指针,用于遍历数组,指针k为不为val元素的个数
    2.若nums[i] != val时,说明该元素无需,则将nums[k] = nums[i];

    int removeElement(int* nums, int numsSize, int val){
    if(numsSize == 0)
        return 0;
        int k = 0;
        for(int i = 0; i < numsSize; i++)
        {
            if(nums[i] != val)
                nums[k++] = nums[i];
        }
        return k;
    }
    

    611. 有效三角形的个数
    在这里插入图片描述

    算法思想:优化的暴力法
    1.先进行冒泡排序,方便进行判断是否为三角形
    2.枚举所有三角形,优化的部分为当ums[i] + nums [j] <= nums[k]时,说明两边之和已经小于第三边了,后面的就不需要再判断了

    void bubblesort(int* nums, int numsSize)  //进行冒泡排序
    {
        for(int i = numsSize - 1; i > 0; i--)
            for(int j = 0; j < i; j++)
            {
                if(nums[j] > nums[j + 1])
                {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
    }
    int triangleNumber(int* nums, int numsSize){
        if(numsSize < 3)
            return 0;
        bubblesort(nums,numsSize);
        int count = 0;
        for(int i = 0; i < numsSize - 2; i++)
        {
            if(nums[i] == 0)    //若遇到0元素继续向后找,直到找到非0元素
                continue;
            for(int j = i + 1; j < numsSize - 1; j++)
                for(int k = j + 1; k < numsSize ; k++)
                {
                    if(nums[i] + nums [j] <= nums[k])   //若当前两边已经小于第三边,则不再判断更大的第三条边
                        break;
                    count++;
                }
        }    
        return count;
    }
    

    209. 长度最小的子数组
    在这里插入图片描述

    动态规划
    1.设置双指针i和j同时指向表头,sum统计当前的和,初始化长度为numSize + 1
    2.i向后遍历,sum为遍历到的元素值的和,直至sum >= s,更新此时的长度
    此时sum减去j下标元素的值,j向后移动一个单位
    3.重复执行过程2,判断此时的长度是否大于numsSize,若大于则返回最小的长度,否则返回0

    int minSubArrayLen(int s, int* nums, int numsSize){
        int minlen = numsSize + 1, sum = 0;
        for(int i = 0, j = 0; i < numsSize; i++)
        {
            sum += nums[i];
            while(sum >= s) //需注意此时应该为while,意为不停地去缩短左侧范围
            {
                int len = i - j + 1;
                if(len < minlen)
                    minlen = len;
                sum -= nums[j++];
            }
        }
        if(minlen > numsSize)
            return 0;
        return minlen;
    }
    

    3. 无重复字符的最长子串
    在这里插入图片描述

    算法思想:采用哈希表 + 滑动窗口的思想
    1.设置双指针i和j,用hashtable表示集合中元素是否出现
    2.从第一个元素开始向后遍历,分为两种情况
    若当前元素不在集合中,则将其加入集合,更新长度,同时将i向后移动一个单位
    若当前元素在集合中,将集合中的该元素删除,并将j向后移动
    3.结尾返回最大长度即可

    int lengthOfLongestSubstring(char * s){
        int len = strlen(s);
        if(len <= 1)
            return len;
        int maxlen = 1, i = 0, j = 0;
        bool hashtable[128] = {false};
        while(i < len && j < len)
        {
            if(hashtable[s[i]] == false)    //若未出现过
            {
                hashtable[s[i]] = true; //加入集合
                int currentlen = i - j + 1;
                if(currentlen > maxlen)
                    maxlen = currentlen;
                i++;
            }
            else    //当出现过,则将其去除,并让后指针移动
            {
                hashtable[s[j]] = false;
                j++;
            }
        }
        return maxlen;
    }
    

    88. 合并两个有序数组
    在这里插入图片描述

    算法思想:双指针
    1.设置双指针p,q,同时指向两个数组的末尾,设置k用于表示新数组当前需要赋值元素的下标
    2.同时遍历两个数组时,比较p和q所指元素的值,较大的赋值给nums1[k],然后较大值的指针向左移动一个单位
    若有一个指针下标小于0时,则不再比较,直接将另一个指针下标所指的元素依次赋值

    void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
        if(n == 0)
            return nums1;
        int p = m - 1, q = n - 1, k = m + n -1;
        while(k >= 0)   //当所有元素赋值完毕
        {
            if(p >= 0 && q >= 0)    //两个链表均未遍历完成
            {
                if(nums1[p] >= nums2[q])
                    nums1[k--] = nums1[p--];
                else
                    nums1[k--] = nums2[q--];
            }
            else if(p < 0)  //nums1遍历完成
            {
                    nums1[k--] = nums2[q--];
            }
            else    //nums2遍历完成
                break;
        }
    }
    
    展开全文
  • 高级数据结构 基础知识 trie树 又叫字典树、前缀树 (图中的红圈表示字符串结尾) 最为高效的字符串查找算法。 // 26 个字母 #define TRIE_MAX_CHAR_NUM 26 struct TrieNode { TrieNode *child[TRIE_MAX_CHAR_NUM...
  • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vnm5YSxi-1605532451835)(C:\Users\ASUS\AppData\Roaming\Typora\typora-user-images\1605529086917.png)] 示例: 输入:"23" 输出:["ad",...
  • 横空出世,席卷互联网 ---评微软数据结构+算法面试100题作者:July。时间:2010年10月-11月。版权所有,侵权必究。出处:http://blog.csdn.net/v_JULY_v。说明:本文原题为:“横空出世,席卷Csdn [评微软等公司...
  • LeetCode刷题

    2015-07-13 01:24:13
    暑假LeetCode刷题
  • 使用这个学习软件自行学习能快速掌握数据结构内容 我们老师给我的 还不错哦。适合初学数据结构的同学,提供种数据结构,代码,参数及数据结构的逻辑图
  • CTF刷题

    2021-08-05 19:37:44
    刷题网站:bugku;BUUCTF 本文记录了在刷题过程中所学到的知识点 坚持每天刷5道题,持续更新 坚持就是胜利鸭 CTF 1、bugku–Simple_SSLI_1 根据题目SSLI即服务端模板注入攻击,服务段接收用户输入,将其作为web应用...
  • 算法刷题 45 天总结

    2020-12-25 11:40:00
    算法和数据结构的学习从来不是一蹴而就,中间要有很多思考,很多练习,很多积累,才能真正掌握。我在3个月前,与600位星友一起开启刷题练习、分析思考和总结,现在已经来到Day55.关注下方《...
  • leetcode刷题

    2021-10-22 23:35:02
    leetcode刷题日记 <day 2021/10/20> 453. 最小操作次数使数组元素相等 简单 给你一个长度为 n 的整数数组,每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。 示例 1: 输入:nums...
  • PM刷题小记

    2021-05-23 10:19:16
    iQiyi PM刷题 对1-31PM题总结 1.移动端APP开发成本最高的是?(Native App) WebApp:针对iOS/Android优化后的web站点,用户不需要下载安装即可访问。 Native App(原生App):基于智能手机操作系统用原生程序编写...
  • 1、关于数据结构与算法? 数据结构就是为算法服务的,算法要作用在特定的数据结构之上.数据结构和算法相辅相成. 广义上讲就是 "操作一组数据的方法",像是你有很多个视频,我们怎么才能更快的查询到他们呢?可以先根据...
  • 软考刷题

    2019-11-08 22:10:47
    1:数据字典:不包括外部实体,包括基本加工 2:条件取值,有多少取多少 3:用户进程,与设备无关系统软件,设备驱动,中断处理,硬件 4:流水线的吞吐率是最长流水段操作时间的倒数 5:工作估算模型COCOMO II不...
  • 刷题第六天

    2021-01-13 11:26:39
    示例 3: 输入:words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" 输出:false 解释:当前三个字符 "app" 匹配时,第二个字符串相对短一些,然后根据词典编纂规则 "apple" > "app",因为 'l' > '∅'...
  • Android 源码,Android 第三方框架,Android 性能优化,数据结构与算法,再加上一些网络知识等等,这里我就不再重复赘述了。 另外我在补充两个点,我们在复习具体的题目或知识点时,还可以着重去百度查找具体公司的...
  • 当然,最后不要落下数据结构与算法、计算机原理等基础知识,这些才是程序员后期的竞争力,如果想要把握更多的当然你也可以学习后端开发相关的知识。 怎么学习 其实我更希望做无论是哪端的开发,都可以让自己的成长...
  • 这篇博客儿主要用来汇总LeetCode面试高频题目,为大家提供一种刷题思路
  • LeetCode刷题打卡(Java)

    2021-01-23 22:22:54
    最近想系统的刷LeetCode,看了很多LeetCode刷题攻略后决定从LeetCode热题100开始,按照顺序每天两题。困难的先跳过(能力不足),其余的题目会把解题思路和代码都放在这篇文章里,当作每天打卡,也欢迎同样想刷...
  • 算法笔记刷题(100000578-100000580) ...数组13 为了取数据更方便 #include<cstdio> #include <algorithm> using namespace std; bool isLeap(int year) { return (year % 4 == 0 && year % 100 !=
  • 69 ssm消防车辆检查与维修app 70 jsp学生就业创业管理系统 71 ssm随心淘网管理系统 72 ssm高校学生党建管理系统 73 springbootLIS检验系统 74 java超市进销存管理系统 75 ssm儿童思德教育网 76 ssm员工工资管理系统 ...
  • Leetcode-How-What 力扣Leetcode刷题指南

    千次阅读 2020-03-05 10:39:53
    Leetcode-How-What 力扣Leetcode刷题指南 About the way how to use Leetcode wisely for preparing the interview and the solutions to some Leetcode problems’. 怎样为准备面试机智聪明的刷题(高效刷题)以及...
  • 经过了数个月的学习,我们了解了包括链表、队列、栈、二叉树、堆(优先队列)、并查集、哈希表、单调队列、单调栈等数据结构,知道了他们的概念、性质、基本代码实现和应用场景,还学习了常见的排序算法如:快速排序...
  • 考研刷题小程序

    千次阅读 2020-12-29 09:06:20
    这个刷题小程序从2020年年初开发到6月份正式上线运营,半年的数据如下所示,陆续续每天人就那么一二千人,最高峰从没有超过5000,不过有你们在使用,就是我持续迭代的动力源泉,非常感谢这半年使用小程序的用户,...
  • 如何将刷题的效率提升10倍

    千次阅读 2018-08-17 12:38:00
    刷题一直找不到好方法,很苦恼? 这里分享一下真正能提高刷题效率的方法 1.刷题误区: 1.看到题就去搜答案 ...中期:熟悉各种类别的题目解题思路(线性结构,数据结构,图形结构,动态规划)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,818
精华内容 1,127
关键字:

数据结构刷题app

数据结构 订阅