N-Queens II Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. tag: backtracking 此题与上一题非常相似，只是把“输出所有可能情况”改成了“输出所有可能情况的个数”。详细解析请看上一题的结题报告： N-Queens class Solution { public: int totalNQueens(int n) { if(n == 0){ return 0; } int queen[n] = {0}; int sum = 0; for(int i = 0; i < […]
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. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ […]
Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. A partially filled sudoku which is valid. Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only […]
Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Follow up: Can you solve it without using extra space? 与上一题类似，这里我直接复用并修改了上一题的代码。 我们这样来想： 设置两个指针fast和slow，fast指针每次走2步，slow指针每次走1步。 假设进入环之前的路径长为n，环的长度为m。那么当slow指针进入环的第一个节点时，slow指针走了n步，fast指针在环里走了n步。两个指针的距离为m-n步。slow指针每走1步，fast指针都会追近1步。那么，当slow指针走了m-n步时，两个指针相遇。此时，fast-slow指针距离下次抵达环入口的距离为n步。 在fast-slow指针相遇时，在链表入口处放置一个指针p，p指针每次走一步。slow指针也每次走一步。这样当slow和p都再走n步时，两者在环的入口处相遇。即返回结果。 /** * Definition for singly-linked list. * struct ListNode { * int val; […]
Linked List Cycle Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? tag: two pointers, linked-list 很巧妙的一道题。最暴力的解法，给访问过的node做一个标记，如果新访问的node已经被标记为已访问的话，则存在环。否则如果node的next为null的话，不存在环。但是需要线性额外空间。 本题我们可以用双指针算法。 定义一个fast指针，每次移动两个node。定义一个slow指针，每次移动一个node。 假设存在环，当slow指针进入环的第一个节点时，fast指针已经在环里绕了一圈或多圈了。 这是，如果以slow指针为相对参考坐标系（上点高中物理的知识），那么slow指针静止不动，fast指针每次以一个node的速度接近slow指针。这样两个指针必定会相遇。证明存在环。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; […]
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 […]
Reverse Linked List II Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. tag: […]
Binary Tree Inorder Traversal Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? confused what “{1,#,2,3}” means? > read more on how binary tree […]
Valid Palindrome Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, “A man, a plan, a canal: Panama” is a palindrome. “race a car” is not a palindrome. Note: Have you consider that the string might be empty? This is a […]
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. tag: hashtable, linked-list 虽然被标记为hard，但代码不长。 问题关键是，在拷贝完next指针后，要根据原来链表中的random的地址，找到新建的链表中对应的node的地址，这里我们用一个hashtable来实现，在拷贝next指针时，将对应关系记录下来。 空间复杂度o(n)，时间复杂度o(n)。 /** * Definition for singly-linked list with […]
