Leecode-033 [Search in Rotated Sorted Array]

思路：二分法查找

Solution：binary search

• 需要的参数

  • start 初始化为0
  • end 初始化为length-1
  • mid 初始化为start + (end-start)/2

• 分以下三种情况进行查找

  • 第一种情况：target = mid

  

  阅读更多...

Leecode-032 [Longest Valid Parentheses]

思路：

Solution：stack

• leftmost: 指定最左侧的边界–>初始值为-1
• stack：初始为空
• idx: 每个括号的索引
• 原则：遇到正括号就push,反括号就pop
• max: 计算最大长度（反括号的index减去最上层的正括号的index）
  • [如果遇到反括号，pop之后stack为空，那么长度 = 当前idx - leftmost]
  • [如果遇到反括号，pop之前stack为空，那么leftmost = 当前 idx, 长度就是当前idx-leftmost]

Leecode-082 Remove Duplicates from Sorted List II

思路：

题目描述

• 本题是83题目的升级版本
• 给出一个链表，如果重复就直接把所有重复的元素都去掉，只保留没有重复的元素

Solution：一次遍历

• 需要的参数

  • dummynode(注意这个节点不能初始化时候就跟后面连起来)
  • preNode 前一个节点
  • currNode 当前指向的节点
  • realNode 记录不重复的节点（初始化为dummy）

• 步骤

  • 如果currNode的值跟前一个节点preNode不一样并且和下一个节点next的值不一样。那么realNode就记录下当前节点的位置
  • 同时需要考虑preNode为dummy 还有 currentNode.next最后为空的情况

Leecode-141 Linked List Cycle

思路：快慢指针

题目描述:

判断链表有没有环

Solution：

• 使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。

Leecode-279-完全平方数

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

1
2
3
4
5
6
7
8
9
10
11

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

Leecode-524 Longest Word in Dictionary through Deleting

思路：双指针

题目描述：

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例1：

1
2

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出

1

"apple"

示例2：

1
2

输入:
s = "abpcplea", d = ["a","b","c"]

输出：

1

"a"

1
2
3

所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

Solution：

• 题目中“字符串可以通过删除给定字符串的某些字符来得到” ==== 这句话的意思是：找的这个是给定字符串的子串，相同字符串的顺序相等。
• “如果答案不止一个，返回长度最长且字典顺序最小的字符串” ====这个话的意思是如果找到的字符串长度相等，那么需要比较字典顺序，用CompareTo()方法
• 考虑先对字符串进行条件判断.先排除不符合条件的，接下来对符合条件的字符串进行比对:
• 采用双指针：遍历给定字符串，因为找的是自己，与字典中的字符串一个个比，如果相等，他两的下标都加一，在判断字典中的字符串是否和下标相等了，如果相等，则证明找到了。

Leetcode-面试题46-把数字翻译成字符串

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：

0 翻译成 “a” ，1 翻译成 “b”，……，

11 翻译成 “l”，……，25 翻译成 “z”。

一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

1
2
3

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

Leecode-021-Merge Two Sorted Lists

思路：迭代

题目描述：

1
2

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Leecode-023 Merge k Sorted Lists

思路：

Solution：堆

Java

Solution : 利用Comparator接口和PriorityQueue

• 需要的参数：
  • 一个NodeComparator比较node.val的大小
  • 一个dummy node 初始为空节点
  • 一个current node 指向dummy
  • 一个PriorityQueue最小堆队列
• 步骤：
  • 首先构造NodeComparator比较node.val的大小
  • 一个current node 指向dummy
  • 遍历k个list中每一个的头结点，如果头结点不为空，都把它放进PriorityQueue形成一个最小堆
  • 如果PriorityQueue不为空，取出其中最小的节点（pqueue.poll()），current指向取出的节点，current向后移动一位; 同时如果取出后这个node的next不为空，那么把next丢进PriorityQueue中
  • 返回dummy.next

Leecode-001-Two Sum

思路：哈希表

题目描述

给出一个数组和一个两数之和的目标，找到对应目标的数组中两个数的下标。

1
2
3
4

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].