Search in Rotated Sorted Array Suppose a sorted array 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 […]
Best Time to Buy and Sell Stock IV 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 k transactions. Note: You may not engage in multiple […]
Compare Version Numbers Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal […]
Longest Valid Parentheses Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which […]
Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. […]
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; […]
