标签:算法
力扣初级算法(六)【动态规划】 本文中的题目均来自力扣,代码默认以C#实现,伪代码仅用来帮助描述,不严格遵循某种语言的语法。 本章中是一些经典的动态规划面试问题。 我们推荐以下题目:爬楼梯,买卖股票最佳时机 和 最大子序和。 目录力扣初级算法(六)【动态规划】70. 爬楼梯解题思路方法
选择排序 选择排序也是利用了“挡板法”这个经典思想。 挡板左边是已排序区间,右边是未排序区间,那么每次的“选择”是去找右边未排序区间的最小值,找到之后和挡板后面的第一个值换一下,然后再把挡板往右移动一位,保证排好序的这些元素在挡板的左边。 比如之前的例子:{5, 2, 0, 1} 我们用一
题意是给出先序遍历和中序遍历求后序遍历。 显然,先序遍历的第一个数字就是整棵树的根。我们找到该数字在中序遍历中出现的位置,前半部分就是根的左子树,后半部分就是右子树。 按照这种思路,我们每次递归左右子树,都先从先序遍历中找到该子树的根,从而确定整棵树。 代码如下 #include<
输入一个递增排序的数组和一个数字 S,在数组中查找两个数,使得他们的和正好是 S,如果有多对数字的和等于 S,输出两个数的乘积最小的 解题思路 和上一题思路差不多,左右加逼,要注意的是:最小乘积一定是最外围两个数相乘! 证明如下,假设 b > a,且存在 a + b = s (a
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序 解题思路 采用双指针技术,就是相当于有一个窗口,窗口的左右两边就是两个指针,我们根据窗口内值之和来确定窗口的位置和宽度。 import java.util.ArrayList; public cl
链表 链表是数据结构里一个很基础但是又很爱考的线性结构,链表的操作相对来说比较简单,但是非常适合考察面试者写代码的能力,以及对 corner case 的处理,还有指针的应用很容易引起 NPE (null pointer exception)。综合以上原因,链表在面试中很重要。 提到链表就
一副扑克牌,里面有两个大王,两个小王,随机从中抽出了五张牌,例如:红心A、黑桃3、小王、大王、方片5,现决定大小王可以看成任何数字,并且 A 看作 1,J 为 11,Q 为 12,K 为 13,上面的 5 张牌就可以变成 1、2、3、4、5(大小王分别看作 2 和 4)。现在,要求使用这
例如,"student. a am I",正确的句子应该是 "I am a student." 解题思路 先使用空格将字符串切割为字符串数组,再重新拼接新的字符串 public class Solution { public String ReverseSentence(Str
对于一个给定的字符序列S,请把其循环左移 K 位后的序列输出。例如,字符序列 S= "abcXYZdef",要求输出循环左移 3 位后的结果,即 "XYZdefabc" 解题思路 最简单的做法,拼接字符串 public class Solution { public Strin
求 1 + 2 + 3 + ... + n,要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 A ? B : C 解题思路 需要利用逻辑与的短路特性来实现递归的终止,当 n == 0 时,(n > 0) &&
有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,随机指定一个数 m,让编号为 0 的小朋友开始报数。每次喊到 m - 1 的那个小朋友要出列唱首歌,然后可以在礼品箱中任意挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续 0 ... m - 1 报数 .... 这样下去 ..
力扣中级算法(一)【数组和字符串】 本文中的题目均来自力扣,代码默认以C#实现,伪代码仅用来帮助描述,不严格遵循某种语言的语法。 可前往GitHub下载Markdown 笔记 数组和字符串问题在面试中出现频率很高,你极有可能在面试中遇到。 我们推荐以下题目:字母异位词分组,无重复字符的最
​ 在程序员的世界里,索引都是从零开始,我们也不例外。 ​ 虽然是开篇词,却非开篇之时写下,也非收尾之时补充,不过一时兴起,有感而发。 这里先引用力扣官方在概述中的一段话 记住:刻意练习并不意味着寻找答案并记住它,这种练习方法不是长久之计。 在没有参考答案情况下,越能自主解决问题,才越能
题解   正规解法是 dfs + 并查集,首先用 dfs 将其所有的情况枚举出来,再用并查集来判断是否在一个连通块上。        许多小伙伴计算的答案为76,主要是判断连通块这方面有问题,倘若不用并查集,直接枚举一条边是否和其余剩下的边相连,是就成立,不是就可以直接退出了,但是有一个