Algorithm Flashcards
- 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
- 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
- 用计数器来，有就加，没有就减
- 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
- 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
- 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，只是说，怎么解决不是一次走一格，而是一次走一列或者一行
- 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，来表示每层的结束
- 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的
- 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这个操作了
- 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. 用公式求和然后再减去
- 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
- Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
Linkedlist，你要删除一个点，一定是记录他前面一个值
- 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/
- 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);
}
- 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.
这题有意思，要再熟悉熟悉，先把点记录下来
- 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, 变化来的才要操作
- 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
- 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 && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
- 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.
对基本功的考察
- Linked List Cycle
Given a linked list, determine if it has a cycle in it.
快慢指针 遇到相等，就返回true
- Linked List Cycle II
快慢指针，遇到，将快指针挪到开头，直到碰到
- Rotate List
Given a linked list, rotate the list to the right by k places, where k is non-negative.
先得到len，然后对k进行取模，得到真正要的长度
用两个指针，确定要挪动的开头位置和结尾位置
有一个容易出bug的地方，先把尾巴挪过来，在确定头部，否则万一直接是null就尴尬了
- Merge k Sorted Lists
三种方法；pq，merge方法
注意corner case, 如果list 中node为null时怎么办
- 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出来
- 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的意思
- 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
把它后面一个值，给它自己，然后删掉它后面的点
- Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
三步走战略
一找中点，
二把后半部分reverse,
三一一对比
- Insertion Sort List
Sort a linked list using insertion sort.
其实是build了一个新的list，用dummy node，记下来
- Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
method1：
得到两个长度，差值，然后让其中一个先跑这么多
method2:
先跑一遍对方，再跑一遍自己
- 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.
两个指针
感觉不好总结，还是
- 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
- Remove Linked List Elements
Remove all elements from a linked list of integers that have value val.
dummy node，没啥特殊的
- 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，计算出需要反转几次
三，反转时，传入需要开始的前一个点，输出下一个要开始转的点
反转的方法很多
不用双指针的方法容易乱，还是双指针吧
- 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
- 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
- Number of Islands
grid[][] 就可以不用boolean visited，而是把‘1’变成‘0’
- Same Tree
divide and conquer
- Balanced Binary Tree
divide and conquer，返回层数和true and false
- Convert Sorted Array to Binary Search Tree
出口的case还是要再想想
left > right
return null
- 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
一个点的面积应该是它四周的面积的和
- 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, 那两个应该对应
- 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
- 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，不断往下传，然后再求和上传
- Construct Binary Tree from Preorder and Inorder Traversal
inorder 就相当于过了这个点
- Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
这个题真是难啊
- 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:
第一还没有时
第一次交换，第二次交换
- 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有没有来进行下一步操作
每一层保存
- Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
preorder travel 但是保存一个pre点，用于连接后面的点
post order traversal
- 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，到最后再输出成字符串形式
- Minimum Depth of Binary Tree
有些不好处理的corner case可以在最上面处理，而递归处只处理原先的
- 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.
把值往下传
- Clone Graph
hashmap 解决一切
- 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来解决
还有一个小技巧，用查有多少数字的办法
- 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.
传参数进去，告诉自己在第几层
- 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都可以
先走右边保证，右边先进来
然后，用层数来显示到哪一层了，然后在看对应的答案到这层有没有
- 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，也可以在进去之后再判断
- 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)
- Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
就是inorder 和 preorder 反过来，再做一遍
- 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
- 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的关系）
