Java教程

算法笔记啊

本文主要是介绍算法笔记啊,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

数组中重复的数字

  1. 利用哈希集合查找重复元素,熟悉unordered_set用法

当我们允许使用额外空间时,set是一个不错的选择。我们可以遍历数组来将nums中的元素放入set;如果nums[i] 已经存在于集合,则返回该值;如果不存在,将该值添加到集合中。

  1. 先排序,再前后比较
  2. 原地交换

本题条件,长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内,因此我们可以将数组中的元素nums[i]与下标i进行匹配,当出现相同数字,但下标不同的时候,说明出现的了重复。

无重复字符的最长字串

用unordered_map处理重复字符<字符,索引>

当遇到重复字符时,把左指针指向重复字符的下一个,并更新长度

最小的k个数

priority_queue(优先队列),大顶堆

二维数组中的查找

我们从左下角开始遍历,当该值小于 target 值时,向右搜索;大于 target 值时,向上搜索。如果找到 target 则返回 True,否则返回 False。

替换空格

在原字符串后增加新的字节空间,双指针从后向前遍历。

不用加减乘除做加法

使用位运算的二进制数的相加过程相同:

1) 两个二进制数各位异或,得到无进位的和

2) 二进制数各位与再左移,计算进位

3) 无进位和与进位异或

重复上面操作,直到不再有进位,即进位为0。

二进制中 1 的个数

在排序数组中查找数字 I

二分查找分别查找左右边界

顺时针打印矩阵

调整数组顺序使奇数位于偶数前面

头尾双指针

斐波那契数列、青蛙跳台阶

  1. 递归,超时
  2. 动态规划

连续子数组的最大和

动态规划(循环遍历数组,从头到尾计算每个位置上的最大值)

和为s的连续正数序列

包含 min 函数的栈

A数据栈,B辅助栈

从尾到头打印链表

  1. 递归调用,注意中止条件。

递归的调用需要建立大量的函数的副本,尤其是函数的参数,每一层递归调用时参数都是单独的占据内存空间,他们的地址是不同的,因此递归会消耗大量的时间和内存。而非递归函数虽然效率高,但相对比较难编程。

  1. 利用堆栈先进后出的特点,

先依次将元素压入堆栈中,然后将所有元素从堆栈中弹出,即可实现反转。

  1. 反转链表,前中后三指针

四步,保后,改中,前移,中下,一个闭环

两数相加

竖式加法的思想:

1、从低位开始,逐位相加,若sum >= 10,保留个位,进一;

2、若最高位上存在进位,要在最前面补1;

做链表题目常用技巧:添加虚拟头结点:ListNode *res = new ListNode(-1);以简化边界情况的判断;

复杂度:O(n)因为只遍历了一遍;

反转链表

  1. 前中后三指针
  2. 递归

使用递归函数,一直递归到链表的最后一个结点,该结点就是反转后的头结点,记作 ret .

此后,每次函数在返回的过程中,让当前结点的下一个结点的 next 指针指向当前节点。

同时让当前结点的 next 指针指向 NULL ,从而实现从链表尾部开始的局部反转,当递归函数全部出栈后,链表反转完成。

删除链表中的节点

  1. 前中双指针,可以申请一个虚拟dummy头节点,指向head,设置dummy节点,所有节点删除统一处理,注意:返回dummy->next
  2. 快慢指针,相差k

删除链表中的倒数k个节点

设置虚拟头节点,快慢指针

合并两个排序链表

  1. 迭代

  1. 递归

环形链表Ⅰ

快慢指针,快指针是慢指针的两倍。

循环中止条件为快指针是否为空

环形链表Ⅱ(找出入环点)

先找到相遇节点

慢指针退到头节点,再循环(快慢指针是否相等)

两个链表的第一个公共节点

是不是一定存在 A 的长度加上相交前 B 的长度 = B 的长度加上相交前 A 的长度,所以我们可以用两个指针分别指向 A 和 B,当到达末尾时指向另一个链表的开头,相遇的时候一定是交点,如果不相遇那么说明这两个链表不相交。

旋转数组的最小数字

二分法,注意相等时,右指针前移

复杂链表的复制

  1. 哈希,unordered_set
  2. 复制节点,复制random,拆分链表

二叉树的遍历

方法:递归、迭代,堆栈

  1. 先序(DFS):中前后
  2. 中序(DFS):前中后
  3. 后序(DFS):前后中

二叉树的层次遍历(BFS)

队列,BFS

Z字形输出二叉树

二叉树的深度

二叉树的镜像

本质还是二叉树的先序及层次遍历

递归

拆分为子问题

动态规划

动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

状态定义

转移方程

初始状态

返回值

贪心

局部最优推到出全局最优

这篇关于算法笔记啊的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!