AcKei

题解

设计模式(10)

/ 注册

全部文章 / 题解（共20篇）

动态规划求最长公共子序列

这是一道很经典的动态规划题目。求解步骤确定状态与选择状态是LCS的长度。如果S[i] == T[j]，LCS的长度 + 1; 当不等时，必须选择一个存在于LCS中的字符，但是我们当前肯定不知道哪个是属于LCS里的字符，所以就拿LCS的长度来比较。这里就有两个选择。明确dp...

题解

2021-04-17

0 585

通过备忘录来防止动态规划超时

吃掉n个橘子的最少天数直接使用动态规划 dp[i]表示吃掉i个橘子所需要的最少天数。可以先花一天吃1个，剩余 i-1个橘子，dp[i] = dp[i-1] + 1; 可以先花一天吃i / 2个，剩余i / 2个橘子， dp[i] = dp[i/2] + 1; 可以先花一天吃 2i...

2021-03-22

1 766

双指针解决字符的最短距离

暴力解法 class Solution { public int[] shortestToChar(String s, char c) { int len = s.length(); ArrayList<Integer> index = new ...

2021-03-14

0 590

字母异位词

有效的字母异位词 class Solution { public boolean isAnagram(String s, String t) { int slen = s.length(); int tlen = t.length(); ...

2021-03-14

0 719

双栈双队列实现API接口来自专栏

栈排序重点在push操作 class SortedStack { Stack<Integer> stackMin; Stack<Integer> stack; public SortedStack() { stackMin =...

2021-03-07

0 537

双指针解决链表倒数问题来自专栏

这道题用双指针即可，倒数第k个，其实就是正数n-k+1个。先让快指针走k步，然后slow从head出发，跟fast一步一步走，当fast走到尾（空节点）时，slow的位置正在n-k+1。但是还得注意一些极值情况，比如链表为空或者k大于链表节点时。上代码： public ListNode Fi...

2021-03-07

17 937

二分法查找两个有序数组的中位数

如果是一般的解法，只需要合并两个数组，并返回中位数即可。但这样的时间复杂度是O（m+n）。题目要求我们时间复杂度降为O（logm+n）。那就考虑用二分法了。看了题解区大佬的解法，实在是感觉自己好像白痴啊啊啊！！！tql呜呜呜此处贴上代码 class Solution { public dou...

2021-03-07

0 880

单调栈解决132模式来自专栏

这道题实在是想不出来，看了题解区的大佬的题解，恍然大悟。贴下大佬的代码： class Solution { public boolean find132pattern(int[] nums) { int len = nums.length; int last ...

2021-03-06

0 640

深度优先搜索+回溯解决网格问题来自专栏

class Solution { public boolean exist(char[][] board, String word) { char[] words = word.toCharArray(); int[][] flag = new int[bo...

2021-03-05

0 695

回溯搞定组合总和来自专栏

看到这道题，第一下想到用回溯模板。直接上代码： class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>>...

2021-03-05

0 614