bloodfire

读书笔记

刷题(146) 知识点(10) 题解(49)

/ 注册

全部文章 / 读书笔记（共25篇）

4/20剑指offer

1.数组中的逆序对思路：先把数组分隔成子数组，统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需对数组进行排序。实际就是归并排序的思想。例如7564，我们先将其分为，75,64，再分解为7,5,6,4，然后把长度为1的子数组合并、排序并统计逆序对...

2020-04-20

0 0

4/19剑指offer

1.最长不含重复字符的子字符串思路：采用动态规划的思想，定义函数f(i)表示以第i个字符结尾的不包含重复字符的子字符串的最长长度。如果第i个字符之前没出现过，那么f(i)=f(i-1)+1.如果第i个字符之前已经出现过，那么就分为两种情况，我们计算第i个字符和它上次出现在字符串中的位置的距离，并记作...

2020-04-19

0 0

4/18剑指offer

1.礼物的最大价值思路一：利用动态规划的思想，先用递归的思路分析。先定义第一个函数f（i，j）表达能到达坐标f（i，j）的格子时能拿到礼物总和的最大值。根据题目要求，有两种可能的途径到达坐标为（i，j）的格子。因此的状态转移方程为f(i,j)=max(f(i-1,j),f(i,j-1))+gift[...

2020-04-18

0 0

4/17剑指offer

1.把数字翻译成字符串0-25分别表示a-z，给一个数字看有几种翻译方法，例如12258可以翻译为bccfi,bwfi,bczi,mcfi,mzi.思路：可以想到利用递归解决问题，但递归可能会出现重复计算的问题，为了避免重复计算，我们从右到左进行计算不同翻译的数目。以12258为例，首先计算c4，易...

2020-04-17

0 0

4/16剑指offer

1.把数组排成最小的数思路：定义一个新的排序规则。 class Solution { public: string PrintMinNumber(vector<int> numbers) { /*对vector容器内的数据进行排序，按照将a和b转为string后 ...

2020-04-16

0 0

4/13剑指offer

1. 连续子数组的最大和思路一：从头开始遍历，设置两个数，一个记录当前序列和，一个记录最大序列和。如果当前序列和小于等于0，说明前面的序列没有用，令当前序列和为下一个数字，如果大于0，就继续往上加，再与最大序列和做对比。 class Solution { public: int FindGr...

2020-04-13

0 0

4/12-剑指offer

1.数组中出现次数超过一半的数字思路一：数组中出现次数超过一半的数字是排好序后数组的中位数，我们采用随机快速排序的思路，先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中数字小的数字都在他的左面，大的都在他的右面。如果选中数字的下标刚好是2/n，这个数就是中位数，如果小于，则中位数位于...

2020-04-12

0 0

4/11-剑指offer

1.二叉搜索树与双向链表思路：二叉搜索树中序遍历是排好序的，按照中序遍历的顺序，当遍历转换到根节点时，左子树已经转换为一个排序的链表，并且处在链表中的最后一个节点是当前值最大的节点。我们把倒数第二个节点和根节点连接起来，此时链表的最后一个节点就是根节点。接着去遍历转换右子树，并把根节点和右子树中最小...

2020-04-11

0 0

4/8-剑指offer

1.复杂链表的复制思路：第一步，复制原始链表的任意节点，并将复制节点链接到原节点后面；第二步，如果原始链表上的节点N的指针指向s，那对应复制节点N’指向s的复制节点s’；第三步，将长链表按奇数和偶数位置，分成两个链表。 /* struct RandomListNode { int label...

2020-04-09

0 0

4/7-剑指offer

1.从上到下打印二叉树思路：利用队列，每次打印一个节点的时候，如果该节点有子节点，就把该节点的子节点放到一个队列的末尾。然后到队列的头部取出最早进入队列的节点，重复前面的打印操作，知道队列中所有的节点都被打印出来。 /* struct TreeNode { int val; stru...

2020-04-07

0 0