文章 217
评论 6
浏览 143919
LinkedList - 82. Remove Duplicates from Sorted List II

LinkedList - 82. Remove Duplicates from Sorted List II

82. Remove Duplicates from Sorted List II Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2: Input: 1->1->1->2->3 Output: 2->3 思路: 题目意思是移除所有重复过的节点,做法就是得要找到当前节点和下一个节点不相同的节点,然后把链表接上,跳过重复的节点。 代码: java: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * Li....

LinkedList - 203. Remove Linked List Elements

LinkedList - 203. Remove Linked List Elements

203. Remove Linked List Elements Remove all elements from a linked list of integers that have value val. Example: Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5 思路: 移除制定的节点,需要注意的是,如果移除的是第一个节点,也需要移除。 代码: java: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeElements(ListNode head, int val) { if (head == null) return head....

LinkedList - 83. Remove Duplicates from Sorted List

LinkedList - 83. Remove Duplicates from Sorted List

83. Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1->2->3 思路: 这一题和26题移除数组中重复的元素一样都是去重,只不过这里的数据是链表,思路就是判断当前节点数值和下一个的节点值是否相同,如果相同就跳过下一个节点。不同就移动指针到下一个节点继续判断。 代码: java: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ ....

LinkedList - 19. Remove Nth Node From End of List

LinkedList - 19. Remove Nth Node From End of List

19. Remove Nth Node From End of List Given a linked list, remove the n-th node from the end of list and return its head. Example: Given linked list: **1->2->3->4->5**, and **_n_ = 2**. After removing the second node from the end, the linked list becomes **1->2->3->5**. Note: Given n will always be valid. Follow up: Could you do this in one pass? 思路: 删除链表倒数第n个节点,就是要走到倒数第n+1个节点进行操作,如果一次遍历解决问题,就得使用两个指针,两个指针开始都在同一个位置,然后fast指针先走n+1步,然后slow指针开始和fast指针一起走,这样fa....

LinkedList - 24. Swap Nodes in Pairs

LinkedList - 24. Swap Nodes in Pairs

24. Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list’s nodes, only nodes itself may be changed.   Example: Given 1->2->3->4, you should return the list as 2->1->4->3. 思路: 链表的翻转实现题,题目意思是翻转相邻的两个节点,题目难点在于容易产生断链的情况。所有链表的题目,基本都是先做一个dummy节点去指向头结点,然后再去用其他指针操作链表的时候,就很方便。题目可以扩展为每隔k个节点翻转一次。 代码: java: /** * Definition for singly-linked list. * public class ListNode { * int val; ....

LinkedList - 141. Linked List Cycle

LinkedList - 141. Linked List Cycle

141. Linked List Cycle Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. Example 1: Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node. Follow up: Can you solve ....

Subsequence - 187. Repeated DNA Sequences

Subsequence - 187. Repeated DNA Sequences

187. Repeated DNA Sequences All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. 思路: 题目意思是找出重复的序列,采用滑动窗口和hashset不可以重复的特性来做。 代码: java: class Solution { public List<String> findRepeatedDnaSequences(String s) { Set curr = new HashSet....

Subsequence - 392. Is Subsequence

Subsequence - 392. Is Subsequence

Is Subsequence Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and sis a short string (<=100). A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remainin....

parentheses - 241. Different Ways to Add Parentheses

parentheses - 241. Different Ways to Add Parentheses

Different Ways to Add Parentheses Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Example 1: Input: “2-1-1” Output: [0, 2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2 Example 2: Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation: (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10 思路:....

parentheses - 32. Longest Valid Parentheses

parentheses - 32. Longest Valid Parentheses

Longest Valid Parentheses Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: “(()” Output: 2 Explanation: The longest valid parentheses substring is “()” Example 2: Input: “)()())” Output: 4 Explanation: The longest valid parentheses substring is “()()” 思路: 括号问题常规解法都是使用栈。 代码: java: class Solution { public int longestValidParentheses(String s) { Stack<Integer> stack = ne....

parentheses - 22. Generate Parentheses

parentheses - 22. Generate Parentheses

22. Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ] 思路: 题目意思是给一个整形数字,返回合法左右括号这种组合的所有组合,典型的使用回溯法来做。 代码: java: class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<String>(); backtrack(res, "", 0, 0, n); return res; } private void ba....

Parentheses - 20. Valid Parentheses

Parentheses - 20. Valid Parentheses

20. Valid Parentheses Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1: Input: “()” Output: true 思路: 使用栈来做,遇到左括号入栈,遇到右括号出栈,如果不匹配就不合法。 代码: java: class Solution { /*public boolean ....

palindrome - 132. Palindrome Partitioning II

palindrome - 132. Palindrome Partitioning II

132. Palindrome Partitioning II Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example: Input: “aab” Output: 1 Explanation: The palindrome partitioning [“aa”,“b”] could be produced using 1 cut. 思路: 这一题和131题的条件增加了只要找出切割字符串最少的一种分割方法。用dp来做,状态转移方程就是i到j是否是文字符串。 代码: java: class Solution { public int minCut(String s) { char[] c = s.toCharArray(); int n = c.leng....

palindrome - 131. Palindrome Partitioning

palindrome - 131. Palindrome Partitioning

131. Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: “aab” Output: [ [“aa”,“b”], [“a”,“a”,“b”] ] 思路: 题目意思是找出字符串中子串是回文字符串的所有组合,使用回溯来做。 代码: java: public class Solution { List<List<String>> resultLst; ArrayList<String> currLst; public List<List<String>> partition(String s) { resultLst = new ArrayList<Li....

Palindrome  - 9. Palindrome Number

Palindrome - 9. Palindrome Number

Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3: Input: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome. Follow up: Coud you solve it wi....

Palindrome - 5. Longest Palindromic Substring

Palindrome - 5. Longest Palindromic Substring

Longest Palindromic Substring Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” 思路: 找出字符串中的回文字符串,解法有很多,比如dp,这里采用中容易想到的中心扩散法。主要区分一下偶回文和奇回文的处理,时间复杂度O(n^2),空间复杂度O(1) 代码: java: class Solution { public String longestPalindrome(String s) { if (s == null || s.length() == 0) return ""; int start = 0,....

Sliding Window - 395. Longest Substring with At Least K Repeating Characters

Sliding Window - 395. Longest Substring with At Least K Repeating Characters

395. Longest Substring with At Least K Repeating Characters Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times. Example 1: Input: s = "aaabb", k = 3 Output: 3 The longest substring is "aaa", as 'a' is repeated 3 times. Example 2: Input: s = "ababbc", k = 2 Output: 5 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times. ....

Sliding Window - 340. Longest Substring with At Most K Distinct Characters

Sliding Window - 340. Longest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters Given a string S, find the length of the longest substring T that contains at most k distinct characters. Example 1: Input: S = “eceba” and k = 3 Output: 4 Explanation: T = “eceb” Example 2: Input: S = “WORLD” and k = 4 Output: 4 Explanation: T = “WORL” or “ORLD” 思路: 题目意思是说给定一个k,找出一个连续子串,子串里面最多只允许出现k个不同的字符。所以,使用两个指针来限定窗口大小,当超过k个不同的字符的时候,就调整窗口大小,而调整窗口的时候,需要用字符出现的频率来区分去除的字符是重复的还是不重复的。 代码: java: public class Solution { /** *....

Sliding Window - 3. Longest Substring Without Repeating Characters

Sliding Window - 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. Example 1: Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Example 2: Input: “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1. Example 3: Input: “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence....

Sliding Window - 76. Minimum Window Substring

Sliding Window - 76. Minimum Window Substring

76. Minimum Window Substring Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = “ADOBECODEBANC”, T = “ABC” Output: “BANC” Note: If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S. 思路: 这是一道经典的sliding window的题目,题目意思是给定两个字符串,字符串S如果包含另一个字符串T的所有字符,....

Nothing just happens, it's all part of a plan.