发表于 | 分类于 |

剑指Offer 14.剪绳子（LeetCode 343.整数拆分）

343.整数拆分 - LeetCode (Medium)

题目描述

把一根绳子剪成多段，并且使得每段的长度乘积最大。

1
2
3
4
5
n = 2
return 1 (2 = 1 + 1)

n = 10
return 36 (10 = 3 + 3 + 4)

解题思路

贪心

尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。

阅读全文 »

发表于 | 分类于 |

435.无重叠的区间个数

435.Non-overlapping Intervals (Medium)

Leetcode / 力扣

2020-7-24 11:00:19

题目描述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

1
2
3
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
阅读全文 »

发表于 | 分类于 |

哈希表使用 O(N) 空间复杂度存储数据，并且以 O(1) 时间复杂度求解问题。

  • Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。
  • Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。在对一个内容进行压缩或者其它转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。例如在一个简化 url 的系统中 Leetcdoe : 535. Encode and Decode TinyURL (Medium)

535.TinyURL 的加密与解密

535.Encode and Decode TinyURL (Medium)

LeetCode - TinyURL 的加密与解密

阅读全文 »

发表于 | 分类于 |

51. N皇后

51.N-Queens (Hard)

Leetcode / 力扣

题目描述

在 n*n 的矩阵中摆放 n 个皇后，并且每个皇后不能在同一行，同一列，同一对角线上，求所有的 n 皇后的解。

解题思路

这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

阅读全文 »