Algorithm Flashcards by Qianzhen Li

Pyramid Transition Matrix

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like 'Z'.

For every block of color C we place not in the bottom row, we are placing it on top of a left block of color A and right block of color B. We are allowed to place the block there only if (A, B, C) is an allowed triple.

We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

2 coupled DFS

How well did you know this?

Not at all

Perfectly

Ternary Expression Parser

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Stack
有时候有一大部分是不需要判断的，用character array
用计数器来，有就加，没有就减

How well did you know this?

Not at all

Perfectly

Keys and Rooms

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, …, N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, …, N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

just dfs

How well did you know this?

Not at all

Perfectly

Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

just dfs

How well did you know this?

Not at all

Perfectly

The Maze

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball’s start position, the destination and the maze, determine whether the ball could stop at the destination.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

还是dfs，只是说，怎么解决不是一次走一格，而是一次走一列或者一行

How well did you know this?

Not at all

Perfectly

Number of Distinct Islands

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

0,1 islands 这种题的做法，切记通过把1变成0，来表示已经visited了，用visited[][]这种做法，容易出bug，因为你要有两个条件，一是grid[][] !=0 or visited[][]

还有一个要注意的点，每层结束之后，加一个b，来表示每层的结束

How well did you know this?

Not at all

Perfectly

Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

这题还是挺有意思的，首先，如果你想组成几个框，可以用一个有限的array来组成，分别向里面填，其实这个思路还是挺straightforward的

How well did you know this?

Not at all

Perfectly

Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

其实更像一个linked list的题，有corner case要注意，比如当最后一个有children的是最后一个时，这时，你要注意你预留的next其实是null，这时就没有null.pre这个操作了

How well did you know this?

Not at all

Perfectly

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

sort and binary search(注意两个情况都不满足时)

2. 用公式求和然后再减去

How well did you know this?

Not at all

Perfectly

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

用dummy node，用另外一位单独来记录余数

我的写法有冗余并不好，可以结合一起写
while（l1 != null || l2 != null || rem != 0）
l1 == null ? 0 : l1.val

How well did you know this?

Not at all

Perfectly

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Linkedlist，你要删除一个点，一定是记录他前面一个值

How well did you know this?

Not at all

Perfectly

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.

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/

How well did you know this?

Not at all

Perfectly

Reverse Linked List

public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }

    return pre;
}

//recursion

public ListNode reverseList(ListNode head) {
    /* recursive solution */
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null)
        return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
}

How well did you know this?

Not at all

Perfectly

Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

这题有意思，要再熟悉熟悉，先把点记录下来

How well did you know this?

Not at all

Perfectly

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.

开两个list，一个保持小于的，一个保持大于的，分开进行操作,

注意尾巴要给null, 变化来的才要操作

How well did you know this?

Not at all

Perfectly

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

三大O(nlogn)时间复杂度：

merge sort, quick sort, heap sort

list - > merge sort
array -> quick sort

分治思想，注意有一步操作是mid.next == null

How well did you know this?

Not at all

Perfectly

Middle of the Linked List

fast slow pointer

private ListNode findMid(ListNode head) {
if (head == null) {
return null;
}

    ListNode slow = head;
    ListNode fast = head.next;

    while (fast != null &amp;&amp; fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

How well did you know this?

Not at all

Perfectly

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

对基本功的考察

How well did you know this?

Not at all

Perfectly

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

快慢指针遇到相等，就返回true

How well did you know this?

Not at all

Perfectly

Linked List Cycle II

快慢指针，遇到，将快指针挪到开头，直到碰到

How well did you know this?

Not at all

Perfectly

Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

先得到len，然后对k进行取模，得到真正要的长度

用两个指针，确定要挪动的开头位置和结尾位置

有一个容易出bug的地方，先把尾巴挪过来，在确定头部，否则万一直接是null就尴尬了

How well did you know this?

Not at all

Perfectly

Merge k Sorted Lists

三种方法；pq，merge方法

注意corner case, 如果list 中node为null时怎么办

How well did you know this?

Not at all

Perfectly

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

method 1 hashmap

method 2 加到list里，分三步走，将复制的点插入list，复制random pointer, split出来

How well did you know this?

Not at all

Perfectly

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

不太好总结，孰能生巧把

有点level-order traversal的意思

How well did you know this?

Not at all

Perfectly

237. Delete Node in a Linked List Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Given linked list -- head = [4,5,1,9], which looks like following: 4 -> 5 -> 1 -> 9

把它后面一个值，给它自己，然后删掉它后面的点

234. Palindrome Linked List Given a singly linked list, determine if it is a palindrome.

三步走战略一找中点，二把后半部分reverse, 三一一对比

147. Insertion Sort List Sort a linked list using insertion sort.

其实是build了一个新的list，用dummy node，记下来

160. Intersection of Two Linked Lists Write a program to find the node at which the intersection of two singly linked lists begins.

method1：得到两个长度，差值，然后让其中一个先跑这么多 method2: 先跑一遍对方，再跑一遍自己

24. Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. Given 1->2->3->4, you should return the list as 2->1->4->3.

两个指针感觉不好总结，还是

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.

两个指针 corner case, dummy node

203. Remove Linked List Elements Remove all elements from a linked list of integers that have value val.

dummy node，没啥特殊的

25. Reverse Nodes in k-Group Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

一，求出总长二，除k，计算出需要反转几次三，反转时，传入需要开始的前一个点，输出下一个要开始转的点反转的方法很多不用双指针的方法容易乱，还是双指针吧

817. Linked List Components We are given head, the head node of a linked list containing unique integer values. We are also given the list G, a subset of the values in the linked list. Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

不好总结，用hashset

725. Split Linked List in Parts Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list "parts". The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null. The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later. Return a List of ListNode's representing the linked list parts that are formed. Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

不好总结，注意，把node放进去之后，要断开node

200. Number of Islands

grid[][] 就可以不用boolean visited，而是把‘1’变成‘0’

100. Same Tree

divide and conquer

110. Balanced Binary Tree

divide and conquer，返回层数和true and false

108. Convert Sorted Array to Binary Search Tree

出口的case还是要再想想 left > right return null

695. Max Area of Island Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

dfs 一个点的面积应该是它四周的面积的和

101. Symmetric Tree Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

注意： helper method, 那两个应该对应

124. Binary Tree Maximum Path Sum Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

result type toRoot, max

129. Sum Root to Leaf Numbers Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers.

这个就是一个argument，不断往下传，然后再求和上传

105. Construct Binary Tree from Preorder and Inorder Traversal

inorder 就相当于过了这个点

301. Remove Invalid Parentheses Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

这个题真是难啊

99. Recover Binary Search Tree Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

corner case: 第一还没有时第一次交换，第二次交换

116. Populating Next Right Pointers in Each Node Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

dfs，bfs两种做法 dfs注意先右再左 bfs注意要先要以cur.left有没有来进行下一步操作每一层保存

114. Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-place.

preorder travel 但是保存一个pre点，用于连接后面的点 post order traversal

257. Binary Tree Paths Given a binary tree, return all root-to-leaf paths. Input: ``` 1 / \ 2 3 \ 5 ``` Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3

backtracking 小技巧：不一定要，一直用string形式来传递可以先记录integer，到最后再输出成字符串形式

111. Minimum Depth of Binary Tree

有些不好处理的corner case可以在最上面处理，而递归处只处理原先的

112. Path Sum Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children.

把值往下传

133. Clone Graph

hashmap 解决一切

394. Decode String Given an encoded string, return it's decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

用stack来解决，关键是用，当这种没办法一下确定，下一层的string，不适宜直接用dfs递归，而是尝试用stack来解决还有一个小技巧，用查有多少数字的办法

339. Nested List Weight Sum Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists.

传参数进去，告诉自己在第几层

199. Binary Tree Right Side View Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

dfs，bfs都可以先走右边保证，右边先进来然后，用层数来显示到哪一层了，然后在看对应的答案到这层有没有

547. Friend Circles There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends. Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

dfs + visited 注意，每个都可以从头开始 dfs，这个可以在进入之前判断是否visited，也可以在进去之后再判断

337. House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police.

noRoot, root if null return (0, 0)

106. Construct Binary Tree from Inorder and Postorder Traversal Given inorder and postorder traversal of a tree, construct the binary tree.

就是inorder 和 preorder 反过来，再做一遍

207. Course Schedule There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

topological sort bfs(indegree, queue) dfs() visited array ``` visited = 1 visiting visited = 2 visited visited = 0 unvisited ```

690. Employee Importance You are given a data structure of employee information, which includes the employee's unique id, his importance value and his direct subordinates' id. For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct. Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

还是一个dfs， map 记住（id，和employee的关系）

98. Validate Binary Search Tree Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

一种就是inorder traversal 另一个就是用dfs，传node, 左边界，右边界

329. Longest Increasing Path in a Matrix Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

dfs 加记忆化搜索

130. Surrounded Regions Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.

既然是边界才是出口，那就从边界出发，将所有是‘O’的都改标成‘U’，在dfs时，遇到O才接着往下走

332. Reconstruct Itinerary Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

这题很经典，还是要记一下！Euler Path

117. Populating Next Right Pointers in Each Node II Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

先右后左有一个while循环

113. Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

backtracking

542. 01 Matrix Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

这题到现在都没有掌握这题为啥dfs不好使，因为他可以来回走，没有评判标准让他能够控制一个方向来走这种最终有多种值可以影响的，都不适合用dfs 把值设为长+宽+1也这个技巧也可以多学习学习

679. 24 Game You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

DFS 题因为有除数，所以用 eps <= 0.00001来表示先是每两个一个组合，然后这两个组合又可以生成多个组合，进入下一轮

417. Pacific Atlantic Water Flow Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower. Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

dfs 从两个边界各自出发，各自渲染自己可以到的地方，然后两者相交，得到边界思路总结，从要去的地方出发

546. Remove Boxes Given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get k*k points. Find the maximum points you can get.

dp，[][][] 第三位代表后面有多少连续的

364. Nested List Weight Sum II Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

bfs 一层一层 | res 记录答案，unweighted 记录，从开始到现在加入的值，然后不断叠加

489. Robot Room Cleaner Given a robot cleaner in a room modeled as a grid. Each cell in the grid can be empty or blocked. The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees. When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell. Design an algorithm to clean the entire room using only the 4 given APIs shown below.

记住 dir 方向要记住

494. Target Sum You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S.

dfs，array是step，+，-是每一步的选择 dp，背包法

409. Longest Palindrome Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example "Aa" is not considered a palindrome here. Note: Assume the length of given string will not exceed 1,010.

trival

513. Find Bottom Left Tree Value Given a binary tree, find the leftmost value in the last row of the tree.

用一个int[] 记录深度，和大小

733. Flood Fill An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image. To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. At the end, return the modified image.

普通dfs，没啥难度

834. Sum of Distances in Tree An undirected, connected tree with N nodes labelled 0...N-1 and N-1 edges are given. The ith edge connects nodes edges[i][0] and edges[i][1] together. Return a list ans, where ans[i] is the sum of the distances between node i and all other nodes.

这一题的思路很难想，实现倒还好距离啥的，与node，多少个有关系先做一遍，看看与root头有什么关系，也就是先求出一个，再想想别的与这个有什么关系，还有一个就是预处理

529. Minesweeper You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine. Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules: If a mine ('M') is revealed, then the game is over - change it to 'X'. If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively. If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines. Return the board when no more squares will be revealed.

其实只是题目描述更复杂一些，题目描述也有问题

bidirectional search

bfs找最短路径 | 从start和end，都进行bfs，这样可以大幅降低复杂度

236. Lowest Common Ancestor of a Binary Tree without/with parent links

bottom up cover method + 先check 是否包含

572. Subtree of Another Tree

最笨方法，构造一个helper method，每个node, 都把它当作root, 来和另外一个比一下；有一个优化，root.val 相等时，才调用helper method

437. Path Sum III You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

preSum来解决

232. Implement Queue using Stacks

这题的意义是在multithreading的时候，offer和pop可以同步进行，只在从receiver捣腾到poper的时候要锁一下 https://www.cnblogs.com/CaiBaoZi/archive/2013/05/29/3105230.html

638. Shopping Offers In LeetCode Store, there are some kinds of items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price. You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer. You could use any of special offers as many times as you want.

不一定要一次减完，可以一个一个来，这个有求值，那就return一个值出来，嗯！

28. Implement strStr()

``` class Solution { public int strStr(String haystack, String needle) { if (haystack == null || needle == null) { return -1; } if (needle.length() == 0) { return 0; } ``` for (int i = 0; i <= haystack.length() - needle.length(); i++) { int j = 0; for (; j < needle.length(); j++) { if (haystack.charAt(i + j) != needle.charAt(j)) { break; } } if (j == needle.length()) { return i; } } return -1; } }

78. Subsets Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.

backtracking

90. Subsets II Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.

先排序，是好方法

46. Permutations Given a collection of distinct integers, return all possible permutations.

hashSet来记录已经有过的值，因为你每次都要从头开始，无法在用index来避免重复

47. Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations.

两种方法，记录visited，一是用hash来记录值，另一个是用一个boolean[] 来记录这个位置是不是用过了，prefer第二个

39. Combination Sum Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.

出口要确定

40. Combination Sum II Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be used once in the combination.

subsetII 的变种

216. Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Note: All numbers will be positive integers. The solution set must not contain duplicate combinations.

可以做一些减枝

377. Combination Sum IV Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

一道动态规划的题目，背包型动态规划，如果有negative怎么办？还没想透

17. Letter Combinations of a Phone Number Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

backtracking 难度不大 | 技巧，固定的对应关系，不一定要hashmap保存，可以用一个专门的helper method来处理这种对应关系

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.

因为palindrome被判断了很多次，所以可以先用dp求出一个二维矩阵，代表所有的substring的可能是不是true。还是这个思路，preprocessing来降低时间复杂度

69. Sqrt(x) Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

follow up（double怎么办），（end - start） < 1e-6

74. Search a 2D Matrix

binary search

35. Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

主要是处理两者都不满足时的情况

278. First Bad Version

binary search, first bad

153. Find Minimum in Rotated Sorted Array Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array.

注意和最后一个比来确认是在上面，还是下面

33. Search in Rotated Sorted Array Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of O(log n).

这个分法很好 ``` class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; ``` ``` while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] > nums[right]) { if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { if (target <= nums[right] && target > nums[mid]) { left = mid + 1; } else { right = mid - 1; } } } ``` return -1; }

162. Find Peak Element A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that nums[-1] = nums[n] = -∞.

看斜率

189. Rotate Array Given an array, rotate the array to the right by k steps, where k is non-negative.

三次反转法

wood cut

二分答案

120. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle ``` [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). ```

top down, bottom up dynamic programming

300. Longest Increasing Subsequence Given an unsorted array of integers, find the length of longest increasing subsequence.

dynamic programming 整个范围内不好想的话，就想想，以该数结尾的话，为结尾状态的话，怎么样 n(logn)方法，保持一个有序递增数列，二分法不断往里面插值

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.

dp trival

55. Jump Game Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

dp or greedy 算法

45. Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.

dp or greedy 算法 greedy不好写

88. Merge Sorted Array Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

从后开始算起！！！但是实现上，还是要想想， while（两个都有）还剩一个？省1？不用再动剩2？接着都动

121. Best Time to Buy and Sell Stock Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.

两个配合，循环一个，让另一个一直保持最优

123. Best Time to Buy and Sell Stock III Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

注意分割的概念，左一个数组，右一个数组，记录如果只有当前长度的最优值，然后再两者合并注意这里出现了一个小bug，array里面保存的是到这里为止的最值，而不是以该点为结尾的最优值

122. Best Time to Buy and Sell Stock II Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

占尽每一个小便宜

53. Maximum Subarray Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

注意前缀和的思想！注意其实没必要构造处一个array再来算！其实也可以考虑sliding window 注意转换成二维时，如何应用前缀和的思想

62 unique pathds 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?

dp，可以用一行解决没必要用一个矩阵

63 unique pathds II 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). Now consider if some obstacles are added to the grids. How many unique paths would there be?

dp，注意用一行时，列方向没法初始化，要用if语句来单独判断0开始的情况

64 Minimum Path Sum Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.

dp 只用一行来解决

关键是怎么写，分次的这种 ``` class Solution { public int jump(int[] nums) { if (nums == null || nums.length == 0) { return -1; } ``` int step = -1; int curPos = -1; int allowPos = 0; ``` while (curPos < allowPos) { step++; int temp = 0; while (curPos < allowPos) { curPos++; temp = Math.max(temp, curPos + nums[curPos]); } allowPos = Math.min(temp, nums.length - 1); } ``` return curPos == nums.length - 1 ? step : - 1; } }

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.

还好，不过坐标的对应关系要搞清楚序列型dp，0是一个要特殊考虑的地方，好好处理会有奇效前n个怎么怎么样！

139. Word Break Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

这里其实是有优化空间的，这一题和132 palindrome partitioning 2 很像，序列型坐标有一个tricky 的地方，单词是有一定长度的，所以当string 很长的时候，没必要从头开始，因为这样会导致剩下的部分很长，不可能有这么长的单词。所以可以求出，wordlist 里最大的单词长度，从后往前只算，最后几个， for 循环，也可以循环长度！ list.contains method 调用的是equal ，不是用地址，所以string时是可以判断相等的，还有一个优化小技巧，倒着来，从小往大去，因为大部分单词不长，所以这样会节省时间也是就是在第二层内循环是有优化空间的

161. One Edit Distance Given two strings s and t, determine if they are both one edit distance apart.

因为只能edit一次，所以可以一直往后比，知道比到有不一样的时候，然后根据长度是否相等，谁比谁大一，小一分别采取措施！

72. Edit Distance Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character

分析insert, replace, delete分别对应那种关系形式

115. Distinct Subsequences Given a string S and a string T, count the number of distinct subsequences of S which equals T. 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 remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

双序列动态规划还是考虑相等，还是不相等时

97. Interleaving String Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

看上去像是一个3d dp，但是只有[i][j][i + j]才有可能是true

155. Min Stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack.

用一个值记录当前最小值，如果比他还小，就把这个值放进stack里，

84. Largest Rectangle in Histogram Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

toLeft, toRight 方法思路，整体时，先考虑如果是其中的一个，是否可行找每个数左右两遍第一个比他大或者小的数

max tree

找一个node，左右两边第一个比它大的数原来是考虑，我的儿子是谁，现在是考虑我的父亲是谁！ public TreeNode maxTree(int[] arr) { if (arr == null || arr.length == 0) { return null; } ``` Stack stack = new Stack<>(); for (int i = 0; i < arr.length; i++) { TreeNode next = new TreeNode(arr[i]); while (!stack.isEmpty() && arr[i] >= stack.peek().val) { TreeNode cur = stack.pop(); if (stack.isEmpty() || arr[i] < stack.peek().val) { next.left = cur; } else { stack.peek.right = cur; } } stack.push(next); } ``` ``` TreeNode ans = stack.pop(); while (!stack.isEmpty()) { TreeNode next = stack.pop(); next.right = ans; ans = next; } ``` return ans; }

7. Reverse Integer Given a 32-bit signed integer, reverse digits of an integer.

这里需要考虑的情况是，如果越界了该怎么办 ``` class Solution { public int reverse(int x) { int res = 0; while (x != 0) { int next = res * 10 + x % 10; ``` ``` 注意这里只能是除十，不能在右边，否则还是右边会越界！ if ((next - x % 10) / 10 != res) { return 0; } res = next; x /= 10; } ``` return res; } }

146. LRU Cache 这题需要记住！

``` class LRUCache { private int size; private int capacity; private HashMap map; private Node dummy; ``` ``` public LRUCache(int capacity) { this.capacity = capacity; this.size = 0; map = new HashMap<>(); dummy = new Node(0, 0); ``` dummy.pre = dummy; dummy.next = dummy; } ``` public int get(int key) { if (map.containsKey(key)) { Node cur = map.get(key); delete(cur); addToTail(cur); return cur.val; } else { return -1; } } ``` ``` public void put(int key, int value) { if (map.containsKey(key)) { Node cur = map.get(key); cur.val = value; delete(cur); addToTail(cur); } else { Node cur = new Node(key, value); map.put(key, cur); addToTail(cur); size++; if (size > capacity) { map.remove(dummy.next.key); delete(dummy.next); size--; } ``` } } ``` private void addToTail(Node target) { target.pre = dummy.pre; target.next = dummy; dummy.pre = target; target.pre.next = target; } ``` private void delete(Node target) { Node before = target.pre; Node after = target.next; before.next = after; after.pre = before; } ``` private class Node{ private int key; private int val; private Node pre; private Node next; ``` ``` private Node(int key, int val) { this.key = key; this.val = val; pre = null; next = null; } } } ```

9. Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

palindrome技巧，反转过后，看是否相等。注意值为负的情况

295. Find Median from Data Stream Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For example, [2,3,4], the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: ``` void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far. ```

每次都先向左边放，然后传给右边，当右边比左边多两个时，才返回一个给左边

263. Ugly Number Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

``` public boolean isUgly(int num) { if (num == 0) { return false; } while (num % 2 == 0) { num /= 2; } while (num % 3 == 0) { num /= 3; } while (num % 5 == 0) { num /= 5; } ``` return num == 1; }

264. Ugly Number II Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

方法一： priorityQueue, 如何去重复, 如果他factor里面有3，说明已经到3了，就不能让他再去乘2 方法二：分别给2，3，5一个index，记录各自乘到哪里了如何处理重复，相等时，都往前走一步 public int nthUglyNumber(int n) { if (n <= 0) { return -1; } int[] res = new int[n + 1]; res[1] = 1; int twoIndex = 1; int thirdIndex = 1; int fifthIndex = 1; for (int i = 2; i <= n; i++) { int next = Math.min(2 * res[twoIndex], Math.min(3 * res[thirdIndex], 5 * res[fifthIndex])); if (next == 2 * res[twoIndex]) { twoIndex++; } if (next == 3 * res[thirdIndex]) { thirdIndex++; } if (next == 5 * res[fifthIndex]) { fifthIndex++; } res[i] = next; } return res[n]; }

323. Number of Connected Components in an Undirected Graph Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

dfs，bfs, union find 都行

bfs使用场景

find connect component; | shortest path in simple graph(无向，边的值为一)，所以其实matrix就是一个典型的simple graph

51. N-Queens The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

注意模块儿化！其实不难，这种输出格式复杂的，可以放到最后再处理，不一定要在递归内处理

52. N-Queens II Given an integer n, return the number of distinct solutions to the n-queens puzzle.

给一个n让你去求有多少种方案，有可能就不是动态规划了。这题还是backtrack，然后怎么判断对角线是否被占用，主要是用以斜对角线为index, 建立一个boolean[]

bfs和dfs的时间复杂度

bfs: 边+点的个数 dfs: 方案总数 ✖️构造每个方案需要的个数

127. Word Ladder Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

求最短距离什么的，都是用bfs! tree的bfs不会有重复访问的问题，但是一般的图会出现这样的情况，所以要注意要用一个hashset来避免这种情况的出现两端出发向中间的，更能节省时间！

4. Median of Two Sorted Arrays There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.

去值的一半，也是二分法！写起来也很费劲

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

从间隔开始，或者从一个数开始

6. ZigZag Conversion The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

这题写的太丑陋了！干嘛把往下，往上分成两个，往上往下当作一个来回，干嘛用time来计算次数，实际的范围不是有了么！已错点：

8. String to Integer (atoi) Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed. If no valid conversion could be performed, a zero value is returned.

+,- 号用 sign = 1 or -1来表示！ corner case, 用外部index 这题做的不好

10. Regular Expression Matching Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

双序列动态规划主要是注意在== ‘*’的时候，还要再分开判断一次，这题做的不好

11. Container With Most Water Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

two point, 向中间靠拢

12. Integer to Roman Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

佩服佩服，五体投地！

79. Word Search Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

backtracking! 这题有个corner case，[[a]]这种情况如何处理！因为你在往下走之前限制住了，不能越界，在这种刚刚好的情况下，走不到pos == word.length()的！如果上一个和下一个没有联系，可以通过在进入的时候再判断是否越界，如果要考虑联系，则在进入之前确认一下

3. Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters.

sliding window

13. Roman to Integer

没啥好讲的，记住就好了

15. 3Sum Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

注意重复，一个