什么是数据结构？

数据结构是核算机存储、组织数据的办法

一、线性结构, 线性表

线性表是具有n个相同类型元素的有限序列（n >= 0）
常见的线性表有: 数组、链表、栈、队伍、哈希表(散列表)

根本概念

时间复杂度

大O标明法中, 时间复杂度的公式是: T(n) = O(f(n)), 其间f(n)标明每个代码实行次数之和, 而O标明正比例联系, 这个公式的全称是:算法的渐进时间复杂度.
常见的时间复杂度量级从上至下越来越大:
- 常数阶O(1)
- 对数阶O(logN)
- 线性对数阶O(nlogN)
- 平方阶O(n)
- 立方阶O(n)
- K次方阶O(n^k)
- 指数阶O(2^n)

空间复杂度

空间复杂度是对一个算法在运行过程中暂时占用存储空间大小的一个测量, 相同反映的是一个趋势, 我们用S(n)来定义.
空间复杂度比较常用的有: O(1)、O(n)、O(n).
假设算法实行所需求的暂时空间不跟着某个变量n的大小而改动, 即此算法空间复杂度为一个常量, 可标明为O(1)

// 代码中的i、j、m所分配的空间都不跟着处理数据量改动, 因此它的空间复杂度S(n) = O(1)
int j = 1;
int j = 2;
++i;
j++;
int m = i + j;

空间复杂度O(n)

int[] m = new int[n];
for (i = 1; i <= n; ++i) 
{
    j = i;
    j++
}

这段代码中, 第一行new了一个数组出来, 这个数据占用的大小为n, 这段代码的2-6航, 虽然有循环, 但没有再分配新的空间, 因此, 这段代码的空间复杂度主要看第一行即可, 即S(n) = O(n);

1. 数组（Array）

数组是一种次第存储的线性表，全部元素的内存地址是连续的

很多编程语言中，数组都有个缺点，无法动态批改容量
实践开发中，我们更期望数组的容量是可以动态改动的

动态数组的接口规划

动态数组的规划

添加元素 add(E element)

打印数组

删去元素

new恳求的是连续的内存空间，不能中心挖掉

刺进添加元素 add(int index, E element)

把合规判别抽取出来

2. 链表(LinkedList)

动态数组有个显着的缺点
- 或许会构成内存空间的很多浪费
链表到多少内存就恳求多少内存
链表是一种链式存储的线性表, 全部元素的内存地址不一定是连续的

反转链表

输入: 1->2->3->4->5->NULL
输出: NULL->5->4->3->2->1

递归法翻转链表

ListNode newHead = reverseList(head.next)做的事

// 递归的办法反转链表
Java:
public ListNode reverseList(ListNode head) {
    // 1. 传入的参数合法性 || 递归的终止条件
    if (head == null || head.next == null) return head;
    // 2. 递归, 一贯递归到链表的终究一个结点, 该结点就是反转后的头结点
    ListNode newHead = reverseList(head.next);
    // 3. 每次函数在回来过程中, 将其时结点的后一个结点的指针指向其时结点, 并断开后一个结点指向后方的指针
    head.next.next = head;
    // 4. 断开其时结点指向后一个结点的指针, 并指向nil, 然后完毕链表尾部初步的部分反转
    head.next = null;
    // 5. 回来反转后的链表, 当递归函数全部出栈后, 链表反转完毕.
    return newHead;
}
Swift:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        // 选用递归的办法翻转链表
        // 1. 传入的参数合法性 || 递归的终止条件
        if head == nil || head?.next == nil {
            return head
        }
        // 2. 递归, 一贯递归到链表的终究一个结点, 该结点就是反转后的头结点
        var newHead = reverseList(head?.next)
        // 3. 每次函数在回来过程中, 将其时结点的后一个结点的指针指向其时结点, 并断开后一个结点指向后方的指针
        head?.next?.next = head
        // 4. 断开其时结点指向后一个结点的指针, 并指向nil, 然后完毕链表尾部初步的部分反转
        head?.next = nil
        // 5. 回来反转后的链表, 当递归函数全部出栈后, 链表反转完毕.
        return newHead
    }
}

反转链表力扣链接

双向循环链表

双向循环链表添加 – add(int index, E element)

双向循环链表删去 – remove(int index, E element)

public E remove(int index) {
    rangeCheck(index);
    Node<E> node = first;
    if (size == 1) {
        first = null;
        last = null;
    } else {
        node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = nodex.next;
        prev.next = next;
        next.prev = prev;
        if (node == first) {// index == 0
            first = next;
        }
    }
    size--;
    return node.element;
}

约瑟夫问题(Jesephus Problem)

数到三开枪
可以考虑增设1个成员变量、3个办法
- current: 用于指向某个节点
- void reset(): 让current指向头结点first
- E next(): 让current往后走一步, 也就是current = current.next
- E remove(): 删去current指向的节点, 删去成功后让current指向下一个节点

静态链表

数组里边寄存两个元素, 模仿链表

ArrayList能否进一步优化?

int first: 存储首元素的方位
删去0号位, 改动first指针指向, first = 1

双向链表和动态数组的差异

动态数组: 开荒、毁掉内存空间的次数相对较少, 但或许构成内存空间浪费(可以通过缩容解决)
双向链表: 打开、毁掉空间的次数相对较多, 但不会构成内存空间的浪费

ArrayList和LinkList的运用选择建议

假设一再在尾部进行添加、删去操作, 动态数组、双向链表均可选择
假设一再在头部进行添加、删去操作, 建议选择运用双向链表
假设有一再的在任意方位添加、删去操作, 建议选择运用双向链表
假设有一再的查询操作, 建议选择运用动态数组

二、树形结构, 树

树的根本概念

二叉树

二叉树的性质

真二叉树(Proper Binary Tree)

全部节点的度要么为0, 要么为2

满二叉树(Full Binary Tree)

完全二叉树(Complete Binary Tree)

完全二叉树的性质

下面就不是完全二叉树

常考点

二叉树的遍历

遍历是数据结构中的常见操作, 把全部元素都访问一遍
线性结构的遍历比较简略, 正序遍历/逆序遍历
根据节点访问次第的也不同, 二叉树的常见遍历办法有四种
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历

前序遍历(Preorder Traversal)

访问次第

中序遍历(Inorder Traversal)

访问次第
- 中序遍历左子树、根节点、中序遍历右子树

后序遍历 (Postorder Traversal)

访问次第
- 后序遍历左子树、后序遍历右子树、根节点

层序遍历 (Level Order Traversal)

访问次第
- 从上到下、从左到右依次访问每一个节点

力扣226. 翻转二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // 前序遍历, 先自己, 再左右
        TreeNode tmpNode = root.left;
        root.left = root.right;
        root.right = tmpNode;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // 后序遍历, 先左右, 再自己
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tmpNode = root.left;
        root.left = root.right;
        root.right = tmpNode;        
        return root;
    }
}
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // 中序遍历
        invertTree(root.left);
        TreeNode tmpNode = root.left;
        root.left = root.right;
        root.right = tmpNode;        
        invertTree(root.left);
        return root;
    }
}

力扣刷题

排序

冒泡排序

实行流程
- 从头初步比较每一对相邻元素, 假设第一个比第二个大, 就沟通他们的方位
- - 实行完一轮后, 最完毕的那个元素就是最大的元素
- 疏忽早年找到的最大元素, 重复实行第一步, 直到全部元素有序
最坏、均匀时间复杂度: O(n)
最好时间复杂度: O(n)
空间复杂度: O(1)

for (int end = array.length - 1; end > 0; end--) {
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(begin, begin - 1) < 0) {
            swap(begin, begin - 1);
        }
    }
}
// OC写法
for (NSInteger end = result.count - 1; end > 0; end--) {
    for (NSInteger begin = 1; begin <= end; begin++) {
        NSInteger left = [result[begin-1] integerValue];
        NSInteger right = [result[begin] integerValue];
        if (left > right) {
            [result exchangeObjectAtIndex:begin-1 withObjectAtIndex:begin];
        }
    }
}

假设序列现已完全有序, 可以提早终止冒泡排序, 优化1

for (int end = array.length - 1; end > 0; end--) {
    boolean sorted = true;
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(begin, begin - 1) < 0) {
            swap(begin, begin - 1);
            sorted = false;
        }
    }
    if (sorted) break;
}
// OC写法
NSMutableArray *result = [[NSMutableArray alloc] initWithArray:@[@1, @2, @5, @4, @3]];
for (NSInteger end = result.count - 1; end > 0; end--) {
  BOOL sorted = YES;
  for (NSInteger begin = 1; begin <= end; begin++) {
    NSInteger left = [result[begin-1] integerValue];
    NSInteger right = [result[begin] integerValue];
    if (left > right) {
      [result exchangeObjectAtIndex:begin-1 withObjectAtIndex:begin];
            sorted = NO;
    }
  }
  if (sorted) {
    break;
  }
}

假设序列尾部现已部分有序, 可以记载终究一次沟通的方位, 削减比较次数, 优化2

for (int end = array.length - 1; end > 0; end--) {
    int sortedIndex = 1;
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(begin, begin - 1) < 0) {
            swap(begin, begin - 1);
            sortedIndex = begin;
        }
    }
    end = sortedIndex;
}
// OC写法
NSMutableArray *result = [[NSMutableArray alloc] initWithArray:@[@1, @2, @5, @4, @3]];
for (NSInteger end = result.count - 1; end > 0; end--) {
  NSInteger sortedIndex = 1;
  for (NSInteger begin = 1; begin <= end; begin++) {
    NSInteger left = [result[begin-1] integerValue];
    NSInteger right = [result[begin] integerValue];
    if (left > right) {
      [result exchangeObjectAtIndex:begin-1 withObjectAtIndex:begin];
    }
    sortedIndex = begin;
  }
    end = sortedIndex;
}

排序算法的稳定性(Stability)

假设持平的2个元素, 在排序前后的相对方位保持不变, 那么这是稳定的排序算法
- 排序前: 5, 1, 3, 4, 7, 3
- 稳定的排序: 1, 3, 3, 4, 5, 7
- 不稳定的排序:1, 3, 3, 4, 5, 7
对自定义目标进行排序时, 稳定性会影响终究的排序作用
冒泡排序归于稳定的排序算法
- 稍有不小心, 稳定的排序算法也能被写成不稳定的排序算法

for (NSInteger end = result.count - 1; end > 0; end--) {
    for (NSInteger begin = 1; begin <= end; begin++) {
        NSInteger left = [result[begin-1] integerValue];
        NSInteger right = [result[begin] integerValue];
        if (left >= right) {// > 不小心写成 >=
            [result exchangeObjectAtIndex:begin-1 withObjectAtIndex:begin];
        }
    }
}

原地算法(In-place Algorithm)

什么是原地算法?
- 不依赖额外的资源或许依赖少数的额外资源, 仅依托输出来掩盖输入
- 空间复杂度为O(1)的都可以认为是原地算法
非原地算法, 称为Not-in-place或许Out-of-place
冒泡排序归于In-place

选择排序

实行流程

从序列中找出最大的那个元素, 然后与最完毕的元素沟通方位

- 实行完一轮后, 最完毕的那个元素就是最大的元素

疏忽过程1中现已找到的最大元素, 重复实行过程1

for (int end = array.length - 1; end > 0; end--) {
    int max = 0;
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(max, begin) < 0) {
            max = begin;
        }
    }
    swap(max, end);
}
// OC写法
NSMutableArray *result = [[NSMutableArray alloc] initWithArray:@[@1, @2, @5, @4, @3]];
for (NSInteger end = result.count - 1; end > 0; end--) {
  NSInteger max = 0;
  for (NSInteger begin = 1; begin <= end; begin++) {
    NSInteger begin = [result[begin] integerValue];
    NSInteger max = [result[max] integerValue];
    if (begin > max) {
      max = begin;
    }
  }
    [result exchangeObjectAtIndex:end withObjectAtIndex:max];
}

选择排序的沟通次数要远少于冒泡排序, 均匀功能优于冒泡排序
最好、最坏、均匀时间复杂度: O(n), 空间复杂度: O(1), 归于不稳定排序

堆排序

堆排序可以认为是对选择排序的一种优化.
大顶堆

数据结构&算法

把握最常见的数据结构

数组 @[@”12″, @”34″]
- 长处: 查询快index 遍历便当
- 缺点: 增删慢(找到第5个, 删掉, 678前移) 只能存储一种数据类型(新的tuple元组) 大小固定不便当扩容(int[10]就固定了)
链表
- 长处: 增删快(改动链表的指针)
- 缺点: 查询特别费事(先从头结点依次走下去)
双向链表
- 指针指向前后数据
- @autoreleasepool
线性表
队伍
- queue, 里边放使命
仓库
栈, 压栈, 先进后出, 页面pop
图

树

- 二叉树, 遍历, 次第, 二叉树的翻转
- 二叉树既有链表的长处, 也有数组的长处

hash(散列表)

- 1-10 找到7, 遍历
- 二分法削减了时间复杂度
- 一次到位, 直接通过key找到value, 字典的底层就是hash
哈希函数:f
- 1 – key – f(key) -> index=1
- 哈希把值1放到index=1的方位,
11 12 13 15 18
- 浪费资源, 哈希函数没有规划好
- f(key) = key – 10 = index 定义域key > 10
- 核算简略 + 分布均匀, 直接地址法, 数据分析法,
- 平方取中法(增大落差规划, 导致冲突下降), 哈希冲突
- 取余法
- - 9 13 14 15 16 18 % 10
- - 9 3 4 5 6 8
数据分析 – 位运算 – index – 取值
规划出一个合理的, 分布均匀的哈希函数(散列函数)很难

哈希冲突

平方取中法
- 9 13 14 15 16 18
- 81 169 196 225 256 324 — 哈希冲突
持续哈希 – 再规划哈希函数
判别法 – 每一次移动
再平办法 – 削减你的操作
- 11 12 22 32
- 1 + 2^2 = 5
- 1 + 2^2 + 3^2 = 14
拉链法 –
- 11 12 22 32 42 52

常见的算法标题

1. 字符串翻转

Hello,word =>
Dorw,olleh
- 两个变量记载, 一个早年面走, 一个从完毕走, 换到最中心中止
- 移动换值指针

void char_reverse(char *cha) {
    // 定义第一个字符
    // 空间的首位就是指针的方位
    char *begin = cha;
    // 定义一个完毕
    char *end = cha + strlen(cha) - 1;
    while (begin < end) {
        // 核心逻辑 -- 换值, 移动
        char jh_tmp = *begin;
        *(begin++) = *end;
        *(end--) = jh_tmp;
    }
}

2. 翻转链表

链表有个特性, 从头初步, 没有下标, 断开非常容易
建立一个空的头结点

struct JHNode* reverseList(struct JHNode *head) {
    // 定义遍历指针, 初始化为头结点
    struct JHNode *p = head;
    // 反转后的链表头部
    struct JHNode *newH = NULL;
    // 遍历链表
    while (p != NULL) {
        // 记载下一个节点
        struct JHNode *temp = p->next;
        // 其时节点的next指向新链表头部
        p->next = newH;
        // 更改新链表头部为其时节点
        newH = p;
        // 移动p指针
        p = temp;
    }
    // 回来反转后的链表头结点
    return newH;
}

力扣刷题

力扣151. 翻转字符串里的单词

消除字符串中的多余空格
先0-10先逆序, 再逐个逆序

public String reverseWords(String s) {
        // 容错处理
        if (s == null) return "";
        char[] chars = s.toCharArray();
        // 1. 铲除多余的空格
        // 字符串终究的有用长度
        int len = 0;
        // 其时用来寄存字符的方位
        int cur = 0;
        // 前一个字符是为空格字符
        boolean preIsSpace = true;
        // 遍历字符串
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {// 其时字符chars[i]不是空格字符
                chars[cur] = chars[i];
                cur++;
                preIsSpace = false;// cur指针++移动后, 前一个字符不是空格字符
            } else if (preIsSpace == false) {// chars[i]是空格字符 且 前一个字符chars[i - 1]不是空格
                chars[cur] = ' ';
                cur++;
                preIsSpace = true;
            }
        }
        // 遍历完毕后, 终究的 前一个字符是空格字符
        len = preIsSpace ? (cur - 1) : cur;
        if (len <= 0) return "";
        // 2. 对整个字符串进行逆序
        reverse(chars, 0, len);
        // 3. 对每一个单词进行逆序
        // 前一个空格字符的方位(在-1方位有个想象的岗兵, 就是要一个想象的空格符)
        int preSpaceIdx = -1;
        for (int i = 0; i < len; i++) {
            if (chars[i] != ' ') continue;
            // 遍历到空格字符
            reverse(chars, preSpaceIdx + 1, i);
            preSpaceIdx = i;
        }
        // 4. 对终究一个单词进行逆序
        reverse(chars, preSpaceIdx + 1, len);
        return new String(chars, 0, len);
    }
    // 将[li, ri)规划内的字符串进行逆序
    private void reverse(char[] chars, int li, int ri) {
        ri--;
        while (li < ri) {
            char tmp = chars[li];
            chars[li] = chars[ri];
            chars[ri] = tmp;
            li++;
            ri--;
        }
    }
}

力扣3. 无重复字符的最长子串

给定一个字符串, 请你找出其间不含有重复字符的最长子串的长度.
有点动态规划的感觉
最长无重复字串

哈希表技术

public int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;
        char[] chars = s.toCharArray();
        if (chars.length== 0) return 0;
        // 用来保存每一个字符上一次出现的方位
        Map<Character, Integer> prevIdxes = new HashMap<>();
        // 扫描过零号方位
        prevIdxes.put(chars[0], 0);
        /**
        // 小写字母26数组优化, ASCII 128, 假设是单字节字符
        // 用来保存每一个字符上一次出现的方位
        int[] prevIdxed = new int[128];
        for (int i = 0; i < prevIdxed.length; i++) {
            prevIdxes[i] = -1;
        }
        prevIdxes[chars[0]] = 0;
        */
        // 以i - 1方位字符完毕的最长不重复字符串的初步索引(最左索引)
        int li = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // i方位字符上一次出现的方位
            Integer pi = prevIdxes.get(chars[i]);
            if (pi != null && li <= pi) {
                li = pi +1;
            }
            // 存储这个字符出现的方位
            prevIdxes.put(chars[i], i);
            /**
            // i方位字符上一次出现的方位
            int pi = prevIdxes[chars[i]];
            if (li <= pi) {
                li = pi + 1;
            }
            // 存储这个字符出现的方位
            prevIdxes[chars[i]] = i;
            */
            // 求出最长不重复子串的长度
            max = Math.max(max, i - li + 1);
        }
        return max;
    }

动态规划(Dynamic Programming)

动态规划, 建成DP
- 是求解最优化问题的一种常用战略
一般的运用套路(一步一步优化)

暴力递归(自顶向下, 出现了堆叠子问题)
回忆化查找(自顶向下)
递推(自底向上)

力扣剑指Offer47. 礼物的最大价值

public int maxValue(int[][] grid) {
        // 行数
        int rows = grid.length;
        // 列数
        int cols = grid[0].length;
        // 动态规划, 创建队伍数的二维数组
        int[][] dp = new int[rows][cols];
        // 确认初始方位
        dp[0][0] = grid[0][0];
        // 第0行, 遍历列, 给动态规划二维数组赋值0行全部列值
        for (int col = 1; col < cols; col++) {
            dp[0][col] = dp[0][col - 1] + grid[0][col];
        }
        // 第0列, 遍历行, 给动态规划二维数组赋值0列全部行值
        for (int row = 1; row < rows; row++) {
            dp[row][0] = dp[row - 1][0] + grid[row][0];
        }
        // 全部遍历, 对比哪个大, 赋值其他方位
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                dp[row][col] =  Math.max(dp[row - 1][col], dp[row][col - 1]) + grid[row][col];
            }
        }
        return dp[rows - 1][cols - 1];
    }

力扣121. 生意股票的最佳时机

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

public int maxProfit(int[] prices) {
    if ( prices == null || prices.length == 0) return 0;
    // 其时扫描过的最小股票价格, 默认0号位
    int minPrice = prices[0];
    // 其时扫描过的最大获利
    int maxProfit = 0;
    // 从1号位初步遍历全部价格
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {// 最小股票价格小于第i天的价格
            minPrice = prices[i];
        } else {// 有最小股票价格时以第i天的价格卖出股票, 对比获得最大获利
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
    }
    return maxProfit;
}

力扣72. 修改距离困难

修改距离算法被数据科学家广泛应用, 是用作机器翻译和语音辨认评价标准的根本算法.
给定两个单词word1和word2, 核算出将word1转换成word2所运用的最少操作数.
- 你可以对一个单词进行如下三种操作:

刺进一个字符
删去一个字符
替换一个字符

输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将'h' 替换为 'r')
rorse -> rose (删去 'r')
rose -> ros (删去 'e')

前两种情况

第三种情况

第四种情况
三条路: 从上面、从左面、从左上角
挑一个最小的

public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) return 0;
        char[] cs1 = word1.toCharArray();// 行
        char[] cs2 = word2.toCharArray();// 列
        int[][] dp = new int[cs1.length + 1][cs2.length + 1];
        dp[0][0] = 0;
        // 第0列, 最短途径就是其时行字符串的长度
        for (int i = 1; i <= cs1.length; i++) {
            dp[i][0] = i;
        }
        // 第0行, 最短途径就是其时列字符串的长度
        for (int j = 1; j <= cs2.length; j++) {
            dp[0][j] = j;
        }
        // 其他行其他列的最短途径
        for (int i = 1; i <= cs1.length; i++) {
            for (int j = 1; j <= cs2.length; j++) {
                // 或许的三条核算途径: 从上面、从左面、从左上角 
                int top = dp[i - 1][j] + 1;// 上一行, 同一列
                int left = dp[i][j - 1] + 1;// 上一列, 同一行
                int leftTop = dp[i - 1][j - 1];
                // 假设终究一个字符串不持平, 需求多一步替换操作
                if (cs1[i - 1] != cs2[j - 1]) {
                    leftTop++;
                }
                dp[i][j] = Math.min(Math.min(top, left), leftTop);
            }
        }
        return dp[cs1.length][cs2.length];
    }

难点在情况定义、情况转移方程, 怎么推导出下一个
二维数组可以优化成一维数组

力扣5. 最大回文子串

暴力法

动态规划法

对比暴力法, 其实是暴力法的优化把时间复杂度优化从 n^3 到了 n^2
空间复杂度O(n^2), 空间换时间

从下到上, 从做到右

public String longestPalindrome(String s) {
        if (s == null) return null;
        char[] cs = s.toCharArray();
        if (cs.length == 0) return s;
        // 最长回文子串的长度(至少是1)
        int maxLength = 1;
        // 最长回文子串的初步索引
        int begin = 0;
        // 创建布尔类型的动态规划二维数组
        boolean[][] dp = new boolean[cs.length][cs.length];
        // 从下到上 (i由大到小)
        for (int i = cs.length - 1; i >= 0; i--) {
            // 从左到右(j有小到大)
            for (int j = i; j < cs.length ; j++) {
                // cs[i, j]字符串的长度
                int length = j - i + 1;
                // 两种情况
                /**
                1. 字符串长度 <= 2时, 长度为1或2, cs[i]字符等于cs[j]字符, 那么cs[i, j]是回文串, 
                此刻dp[i][j] = cs[i] == cs[j]
                2. 字符串长度 > 2时, 假设动态规划表其时字符串的左下方cs[i + 1, j - 1]是回文串 aaadefed, 
                且cs[i]字符等于cs[j]字符, 那么cs[i, j]是回文串
                此刻dp[i][j] = dp[i + 1][j - 1] && ()cs[i] == cs[j])
                 */
                dp[i][j] = (cs[i] == cs[j]) && (length <= 2 || dp[i + 1][j - 1]);
                // 其时cs[i, j]是回文子串 且 长度大于保存的最大长度, 重新赋值
                if (dp[i][j] && (length > maxLength)) {
                    maxLength = length;
                    begin = i;
                }
            }                   
        }
          return new String(cs, begin, maxLength);  
    }

给定一个三角形 `triangle`, 找出自顶向下的最小途径和.

每一步只能移动到下一行中相邻的结点上. 相邻的结点 在这里指的是下标与上一层结点下标 相同或许等于 上一层结点下标 + 1 的两个结点.

输入: triangle = [[2], [3,4], [6,5,7], [4,1,8,3]]
输出: 11
解释: 如下面简图所示

自顶向下的最小途径和为11(即, 2 + 3 + 5 + 1 = 11).
解法选用:

从上往下的动态规划
从下往上的动态规划
从下往上的动态规划(运用一维数组)

思路
存储的是抵达第i+1层各个结点的最小途径之和

class Solution {
    public int miniumTotal(List<List<Integer>> triangle) 
        // triangle 是个二维数组
        // 先获取 triangle 的层数, 即一维数组的个数
        int n = triangle.size();
        // 设置一个一维数组, 动态的更新每一层中其时结点对应的最短途径
        int[] dp = new int[n + 1];
        // 从终究一层初步核算结点的最短途径, 直到顶层 0层 中止
        for (int i = n - 1; i >= 0; i--) {
            // dp 中存储的是前 i 个方位存储的是抵达第 i 层各个结点的最小途径和
            // 从每一层的第 0 个方位初步
            for (int j = 0; j <=i ; j++) {
                // dp[j] 标明第 i 层中第 j 个结点的最小途径和
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
            }
        }
        // 回来结果
        return dp[0];
    }
}

力扣链接

发文不易, 喜欢点赞的人更有好运气 :), 守时更新+关注不迷路~

ps：欢迎参加笔者18年建立的研讨iOS审核及前沿技术的三千人扣群：662339934，坑位有限，备注“网友”可被群管通过~

恋上数据结构与算法

什么是数据结构？

一、线性结构, 线性表

根本概念

时间复杂度

空间复杂度

1. 数组（Array）

动态数组的接口规划

动态数组的规划

2. 链表(LinkedList)

反转链表

递归法翻转链表

双向循环链表

双向循环链表添加 – add(int index, E element)

双向循环链表删去 – remove(int index, E element)

约瑟夫问题(Jesephus Problem)

静态链表

ArrayList能否进一步优化?

双向链表和动态数组的差异

ArrayList和LinkList的运用选择建议

二、树形结构, 树

树的根本概念

二叉树

真二叉树(Proper Binary Tree)

满二叉树(Full Binary Tree)

完全二叉树(Complete Binary Tree)

常考点

二叉树的遍历

前序遍历(Preorder Traversal)

中序遍历(Inorder Traversal)

后序遍历 (Postorder Traversal)

层序遍历 (Level Order Traversal)

力扣226. 翻转二叉树

力扣刷题

排序

冒泡排序

排序算法的稳定性(Stability)

原地算法(In-place Algorithm)

选择排序

堆排序

数据结构&算法

把握最常见的数据结构

树

hash(散列表)

哈希冲突

常见的算法标题

1. 字符串翻转

2. 翻转链表

力扣刷题

力扣151. 翻转字符串里的单词

力扣3. 无重复字符的最长子串

动态规划(Dynamic Programming)

力扣剑指Offer47. 礼物的最大价值

力扣121. 生意股票的最佳时机

力扣72. 修改距离 困难

力扣5. 最大回文子串

暴力法

动态规划法

给定一个三角形 triangle, 找出自顶向下的最小途径和.

发文不易, 喜欢点赞的人更有好运气 :), 守时更新+关注不迷路~

相关文章

ThreadPoolExecutor源码细节探索

Java Stream API 操作完全攻略：让你的代码更加出色 (一)

MATLAB神经网络工具箱Neural Net Fitting操作方法

魔改xxl-job，彻底告别手动配置任务！

作者信息

推广

力扣72. 修改距离困难

给定一个三角形 `triangle`, 找出自顶向下的最小途径和.