文章 224
评论 11
浏览 167375
Dynamic Programming - 62. Unique Paths

Dynamic Programming - 62. Unique Paths

62. Unique Paths A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there? Note: m and n will be at most 100. Example 1: Input: m = 3, ....

Dynamic Programming - 70. Climbing Stairs

Dynamic Programming - 70. Climbing Stairs

70. Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2....

LinkedList - 86. Partition List

LinkedList - 86. Partition List

86. Partition List Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. Example: Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5 思路: 题目意思是给一个链表和一个数字,将链表前半部分变成小于这个数字后半部大于等于这个数字。考的是链表基本操作。使用两个指针,记录下比输入小的链表和大于等于该数字的链表,再把两个链表接起来。 代码: java: /** * Definition for sing....

LinkedList - 148. Sort List

LinkedList - 148. Sort List

148. Sort List Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->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 sortList(ListNode head) { ....

Array - 188. Best Time to Buy and Sell Stock IV

Array - 188. Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV Say you have an array for which the _i_th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Example 1: Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2. ....

LinkedList - 61. Rotate List

LinkedList - 61. Rotate List

61. Rotate List Given a linked list, rotate the list to the right by k places, where k is non-negative. Example 1: Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL Example 2: Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right....

LinkedList - 143. Reorder List

LinkedList - 143. Reorder List

143. Reorder List Given a singly linked list L: L_0→_L_1→…→_L__n-1→_L_n, reorder it to: L_0→_L__n_→_L_1→_L__n-1→_L_2→_L__n_-2→… You may not modify the values in the list’s nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it to 1->4->2->3. Example 2: Given 1->2->3->4->5, reorder it to 1->5->2->4->3. 思路: 题目意思是给一个链表,然后重新按照一个前一个后的顺序重新排序。题目主要是考链表的操作,比如找到链表的终点,然后翻转链表,然后交换链表的节点,考的就是链表操作基本功。注意找中点的时候,找到的....

LinkedList - 160. Intersection of Two Linked Lists

LinkedList - 160. Intersection of Two Linked Lists

160. Intersection of Two Linked Lists Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: begin to intersect at node c1. Example 1: ``` Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input Explanation: The intersected node’s value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it r....

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 ....

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