Commit4923264

committed

linkedListCycle, permutations

1 parent3c36ab4 commit4923264Copy full SHA for 4923264

File tree

+72

-4

lines changed

+72

-4

lines changed

Lines changed: 4 additions & 4 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,10 +1,10 @@`
`1`	`1`	`/**`
`2`	`2`	`* Solution: Dynamic programming`
`3`		`- * match[i][j], the number of matched substringswhen s with the length i and t with the length j.`
`4`		`- * if s[i-1] !== s[j-1], then the matched number equals to the matched number of s with length i - 1.`
	`3`	`+ * match[i][j], the number of matched substringsbetween s[0...i) and t[0...j).`
	`4`	`+ * if s[i-1] !== s[j-1], then the matched number equals to the matched number of s[0...i-1).`
`5`	`5`	`* that is, match[i][j] = match[i-1][j].`
`6`		`- * if s[i-1] == s[j-1], the matched number is the mathched number when s with length i - 1 and t with length j,`
`7`		`- * plus the matched number when s with i - 1 lengthand t with j - 1 length.`
	`6`	`+ * if s[i-1] == s[j-1], the matched number is the mathched number when s[0...i-1] and t[0...j),`
	`7`	`+ * plus the matched number when s[0...j-1)and t[0...j-1).`
`8`	`8`	`*`
`9`	`9`	`*@param {string} s`
`10`	`10`	`*@param {string} t`

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,42 @@`
	`1`	`+/**`
	`2`	`+ * Definition for singly-linked list.`
	`3`	`+ * function ListNode(val) {`
	`4`	`+ * this.val = val;`
	`5`	`+ * this.next = null;`
	`6`	`+ * }`
	`7`	`+ */`
	`8`	`+`
	`9`	`+/**`
	`10`	`+ * Solution: Two pointers. Slow moves one step a time, fast moves two steps a time.`
	`11`	`+ * Once fast meets slow, the steps fast moved is twice as the steps slow moved.`
	`12`	`+ * After they met, in order to move to the cycle start place, the steps fast needs to move`
	`13`	`+ * equals to the steps the head need to mve. Here is the reason:`
	`14`	`+ * n1 -> n2 -> n3 -> n4 -> n2 the cycle starts at n2, slow and fast meet at n4`
	`15`	`+ * assume n1 -> n4 needs a steps, n2 -> n4 needs b steps, n4-> n2 needs c steps.`
	`16`	`+ * when fast reach n4, it takes (a + b + c + b) steps, slow reached n4, it takes a + b,`
	`17`	`+ * a + b + c + b = 2 * (a + b), so a = c. => head && fast move at the same, when they meet, that's`
	`18`	`+ * the place where the cycle starts`
	`19`	`+ *`
	`20`	`+ *@param {ListNode} head`
	`21`	`+ *@return {ListNode}`
	`22`	`+ */`
	`23`	`+vardetectCycle=function(head){`
	`24`	`+if(!head\|\|!head.next)returnnull;`
	`25`	`+varslow=head;`
	`26`	`+varfast=head;`
	`27`	`+`
	`28`	`+while(slow.next&&fast.next&&fast.next.next){`
	`29`	`+slow=slow.next;`
	`30`	`+fast=fast.next.next;`
	`31`	`+if(slow===fast){`
	`32`	`+slow=head;`
	`33`	`+while(slow!==fast){`
	`34`	`+slow=slow.next;`
	`35`	`+fast=fast.next;`
	`36`	`+}`
	`37`	`+returnslow;`
	`38`	`+}`
	`39`	`+}`
	`40`	`+`
	`41`	`+returnnull;`
	`42`	`+};`

Lines changed: 25 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -63,3 +63,28 @@ var permute = function(nums) {`
`63`	`63`
`64`	`64`	`returnresults;`
`65`	`65`	`};`
	`66`	`+`
	`67`	`+// Backtracking.`
	`68`	`+varpermute=function(nums){`
	`69`	`+varresult=[];`
	`70`	`+varresults=[];`
	`71`	`+varisVisited=[];`
	`72`	`+dfsHelper(nums,isVisited,result,results);`
	`73`	`+returnresults;`
	`74`	`+};`
	`75`	`+`
	`76`	`+vardfsHelper=function(nums,isVisited,result,results){`
	`77`	`+if(result.length===nums.length){`
	`78`	`+results.push(result.slice());`
	`79`	`+return;`
	`80`	`+}`
	`81`	`+`
	`82`	`+for(vari=0;i<nums.length;i++){`
	`83`	`+if(isVisited[i])continue;`
	`84`	`+isVisited[i]=true;`
	`85`	`+result.push(nums[i]);`
	`86`	`+dfsHelper(nums,isVisited,result,results);`
	`87`	`+result.pop();`
	`88`	`+isVisited[i]=false;`
	`89`	`+}`
	`90`	`+};`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -136,6 +136,7 @@`
`136`	`136`	`*[136. Single Number](https://leetcode.com/problems/single-number/) -[Solution](./Medium/136-singleNumber.js)`
`137`	`137`	`*[139. Word Break](https://leetcode.com/problems/word-break/) -[Solution](./Medium/139-wordBreak.js)`
`138`	`138`	`*[141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) -[Solution](./Medium/141-linkedListCycle.js)`
	`139`	`+*[142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) -[Solution](./Medium/142-linkedListCycleII.js)`
`139`	`140`	`*[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) -[Solution](./Medium/144-binaryTreePreorder.js)`
`140`	`141`	`*[151. Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/) -[Solution](./Medium/151-reverseWordsInAString.js)`
`141`	`142`	`*[152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) -[Solution](./Medium/152-MaxProductSubarray.js)`

Comments

(0)