数据结构与算法

 * author：conowen@大钟                                                                                                                          
 * E-mail：conowen@hotmail.com

常见时间复杂度

常数阶O(1)

没有循环等复杂结构，一次执行便可得到结果，如哈希表取值复杂度就都是O(1)。

线性阶O(n)

经历一次循环：

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

对数阶O(logN)

int i = 1;
while(i<n)
{
    i = i * 2;
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。当循环 log2^n 次以后，这个代码就结束了。简单来说就是每执行一次，后续需要执行的次数就少一半，因此这个代码的时间复杂度为：O(logn)，如二分查找法。

线性对数阶O(nlogN)

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

简单来说，就是上面时间复杂度为：O(logn)的算法，外面套一层循环。

平方阶O(n²)

把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

同理还有立方阶立方阶O(n³)、K次方阶O(n^k)

常用数据结构

数组

数组一般用来存储相同类型的数据，可通过数组名和下标进行数据的访问和更新。数组中元素的存储是连续，同时在内存中连续存放。

数组常见算法题

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
https://leetcode-cn.com/problems/two-sum/

时间复杂度O(N)，空间复杂度O(N)

public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashtable = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i],i);
        }
        return new int[2];
    }

链表

链表的节点除了数据域，还有指针域，用于指向下一节点地址。由于是通过指针进行下一个数据元素的查找和访问，使得链表的自由度更高。

image.png

数组与链表对比

操作 数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

链表常见算法题

翻转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
https://leetcode-cn.com/leetbook/read/tencent/x5xg2m/

   public  static ListNode reverseListNode(ListNode head)
    {
        if (head == null)
            return  head;
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

栈

先进后出 (LIFO: Last In First Out) 表

队列

先进先出 (FIFO: First In First Out) 表

堆

堆是一种非线性结构，可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组但堆并不一定是完全二叉树

  • 大顶堆：每个结点的值都大于或等于其左右孩子结点的值，根节点最大。

  • 小顶堆：每个结点的值都小于或等于其左右孩子结点的值，根节点最小。


    image.png
image.png

图上堆表示为数组为
大顶堆 arr : 50 45 40 20 25 35 30 10 15
小顶堆 arr : 10 20 15 25 50 30 40 35 45

散列表 （哈希表）

树

树可以理解为链表的高配版。树的实现就是对链表的指针域进行了扩充，增加了多个地址指向子结点。同时将“链表”竖起来，从而凸显了结点之间的层次关系，更便于分析和理解。


image.png

二叉树

每个节点最多只有两个分支，通常称二叉树节点的左右两个分支为左右子树。

满二叉树

在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

完全二叉树

从根往下数，除了最下层外都是全满（都有两个子节点），而最下层所有叶结点都向左边靠拢填满。
构造一颗完全二叉树就是【从上到下，从左往右】的放置节点。

image.png

左边是完全二叉树，右边是满二叉树，满二叉树是完全二叉树的一种特殊类型。

二叉查找树

简单来说就是二叉树上所有节点的，左子树上的节点都小于根节点，右子树上所有节点的值都大于根节点。

平衡二叉查找树

根节点看作是天平的中点，左子树的高度放在天平左边，右子树的高度放在天平右边，当左右子树的高度相差「不是特别多」，称为是平衡的二叉树。

二叉树常见算法题

最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null)
            return null;
        if(root.val == p.val || root.val == q.val)
            return root;
        TreeNode left =  lowestCommonAncestor(root.left,p,q);
        TreeNode right =  lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null)
            return root;
        else if(left == null)
            return right;
        else 
            return left;
    }
}

翻转一棵二叉树。

https://leetcode-cn.com/problems/invert-binary-tree/

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

常用算法

排序

排序的算法动画演示可以参考
选取两种常用的排序，冒泡和快排。

private static void quickSort(int[] array, int left, int right) {
        int pivot,temp,i,j;
        if(left >= right) {
            return;
        }
        //p就是基准数,这里就是每个数组的第一个
        pivot = array[left];
        i = left;
        j = right;
        while(left < right) {
            //右边当发现小于pivot的值时停止循环
            while(array[right] >= pivot && left < right) {
                right--;
            }
            //这里一定是右边开始，上下这两个循环不能调换（下面有解析，可以先想想）
            //左边当发现大于pivot的值时停止循环
            while(array[left] <= pivot && left < right) {
                left++;
            }
            System.out.println("res = "+ Arrays.toString(array));
            temp = array[right];
            array[right] = array[left];
            array[left] = temp;
        }
        array[i] = array[left];//pivot与left值互换
        array[left] = pivot;
        quickSort(array,i,left);  //对左边快排
        quickSort(array,left+1,j); //对右边快排
    }

参考
https://www.jianshu.com/p/b0b8eb1ef908

搜索

  • BFS：广度优先搜索

简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。

  • DFS：深度优先搜索

简单来说，从根节点出发，然后依次向下继续搜索，直到遇到叶子节点，此时就会向上回溯，继续向为访问过的点继续深度搜索。

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = maxDepth(root.left);
        int right= maxDepth(root.right);
        return Math.max(left,right) + 1;
    }
}

查找

二分查找

贪心算法

分治算法

动态规划

  • 定义
    要解决一个给定的问题，我们需要解决其不同部分（即解决子问题），再合并子问题的解以得出原问题的解。
    通常许多子问题非常相似，为此动态规划法试图只解决每个子问题一次，从而减少计算量。
    一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
    这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

简单来说，就是利用空间换取时间。

  • 三个核心元素：

1.最优子结构
2.边界
3.状态转移方程

  • 经典题目

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……,从第三个数开始，每个数等于前面两个数之和。
此数列的递归公式为f(n) = f(n-1) + f(n-2);

暴力解法，递归，时间复杂度为O(2^n)

  public static int fib(int n)
    {
        if (n < 2)
            return n;
        return fib(n - 1) + fib(n - 2);
    }

使用备忘录优化
因为上述f(n)在计算过程中，f(n)会重复计算多个子状态，用哈希表存储，然后就可以减少重复计算的次数。

class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();
    public int fib(int n) {
        if (n < 2)
            return n;
        if(map.containsKey(n))
            return map.get(n);
        int val =  fib(n-1)+fib(n-2);
        map.put(n,val);
        return val;
    }
}

时间复杂度O(n),空间复杂度O(n)，多了一个哈希表。

使用动态规划优化
我们发现每次迭代只需要前两次迭代的数据，不用哈希表保存所有子状态的数据。
利用滚动数组的原理。

class Solution {
public int fib(int n) {
        int a = 0,b = 1,ans = 0;
        for(int i = 0; i < n; i++) {
            ans = a + b;
            a = b;
            b = ans;
        }
        return a;
}

另外一个经典题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

我们用 f(x)f(x) 表示爬到第 xx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
(x) = f(x - 1) + f(x - 2)
与上述的斐波那契数列大同小异，边界不同而已。

class Solution {
    public int climbStairs(int n) {
       int a = 1,b = 1,ans = 0;
        for(int i = 0; i < n; i++) {
            ans = a + b;
            a = b;
            b = ans;
        }
        return a;
}

总结
动态规划的核心思想就是穷举求最值，因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。动态规划的穷举一般存在重叠子问题，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。只有列出正确的「状态转移方程」才能正确地穷举。

字符串

字符串翻转

image.png

双指针的解法：
将 left 指向字符数组首元素，right 指向字符数组尾元素。
当 left < right：
交换 s[left] 和 s[right]；
left 指针右移一位，即 left = left + 1；
right 指针左移一位，即 right = right - 1。
当 left >= right，反转结束，返回字符数组即可。

public void reverseString(char[] s) {
      int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
 }

数字

整型数翻转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
https://leetcode-cn.com/problems/reverse-integer/submissions/

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while(x != 0) {
            if (rev > Integer.MAX_VALUE/10 || rev < Integer.MIN_VALUE/10)
                return 0;
            int dig = x % 10;
            x = x / 10;
            rev = rev * 10 + dig;
        }
        return rev;
    }
}

反转URL

https://www.jianshu.com/p/73d56c3d228c

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • Spring Cloud
    Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具（例如配置管理，服务发现，断路器，智...
    卡卡罗2017阅读 134,886评论 18赞 139
  • 网络请求
    AFHTTPRequestOperationManager 网络传输协议UDP、TCP、Http、Socket、X...
    Carden阅读 4,383评论 0赞 12
  • iOS网络架构文档整理
    iOS网络架构讨论梳理整理中。。。 其实如果没有APIManager这一层是没法使用delegate的，毕竟多个单...
    yhtang阅读 5,251评论 1赞 23
  • Java初级面试题
    1. Java基础部分 基础部分的顺序：基本语法，类相关的语法，内部类的语法，继承相关的语法，异常的语法，线程的语...
    子非鱼_t_阅读 31,759评论 18赞 399
  • 面向对象的用电信息数据交换协议
    国家电网公司企业标准（Q/GDW）- 面向对象的用电信息数据交换协议 - 报批稿：20170802 前言： 排版 ...
    庭说阅读 11,133评论 6赞 13