API tools faq
paste
samimwebdev

binary search and step

samimwebdev
Jul 1st, 2022 (edited)
196
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
JavaScript 10.60 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. hello
  3. ll
  4.  
  5. */
  6.  
  7. // var strStr = function (string, subString) {
  8. //   if (subString === '') return 0
  9. //   for (let i = 0; i <= string.length - subString.length; i++) {
  10. //     let j = 0
  11. //     for (; j < subString.length; j++) {
  12. //       if (string[i + j] !== subString[j]) break
  13. //     }
  14. //     if (j === subString.length) return i
  15. //   }
  16. //   return -1
  17. // }
  18.  
  19. // console.log(strStr('hello', 'll'))
  20.  
  21. /*
  22. building A prefix suffix table
  23. aabaaab
  24.  
  25.  
  26. aabaabaaab
  27.   aabaaab
  28. 0101223
  29.  
  30. abceabcd
  31. abcd
  32. aabaaab
  33.  i
  34. j
  35. table = [0, 1, 0, 1, 2, 2, 3 ]
  36. */
  37.  
  38. // var strStr = function (string, subString) {
  39. //   if (subString === '') return 0
  40. //   const prefixTable = buildPrefixTable(subString)
  41. //   let i = 0
  42. //   let j = 0
  43. //   while (i < string.length && j < subString.length) {
  44. //     if (string[i] === subString[j]) {
  45. //       i++
  46. //       j++
  47. //     } else if (j > 0) {
  48. //       j = prefixTable[j - 1]
  49. //     } else {
  50. //       i++
  51. //     }
  52. //   }
  53. //   return j === subString.length ? i - j : -1
  54. // }
  55.  
  56. // console.log(strStr('abceabcd', 'abcd'))
  57.  
  58. // function buildPrefixTable(s) {
  59. //   const table = [0]
  60. //   let i = 1
  61. //   let j = 0
  62. //   while (i < s.length) {
  63. //     if (s[i] === s[j]) {
  64. //       j += 1
  65. //       table[i] = j
  66. //       i++
  67. //     } else if (j > 0) {
  68. //       j = table[j - 1]
  69. //     } else {
  70. //       table[i] = 0
  71. //       i++
  72. //     }
  73. //   }
  74. //   return table
  75. // }
  76. //Recursion
  77. //iterative solution
  78. // function countDown(num) {
  79. //   for (let i = num; i >= 0; i--) {
  80. //     console.log(i)
  81. //   }
  82. // }
  83. // countDown(10)
  84.  
  85. //recursive solution
  86. // function countDown(num) {
  87. //   //Must have a base case
  88. //   if (num < 0) return
  89. //   //must return and something properly
  90. //   console.log(num)
  91. //   //input must be changed in some sort of fashion in recursive function
  92. //   countDown(num - 1)
  93. // }
  94. // countDown(10)
  95.  
  96. // function sumRange(num){
  97. //   let sum = 0
  98. //   for(let i = num; i > 0; i--){
  99. //     console.log(i)
  100. //     sum += i
  101. //   }
  102. //   console.log(sum)
  103. // }
  104.  
  105. // sumRange(10)
  106.  
  107. //recursive solution
  108.  
  109. /*
  110. 10 + SumRange(9)
  111.     9 + sumRange(8)
  112.          8 + sumRange(7)
  113.             7 + sumRange(6)
  114.               6 + sumRange(5)
  115.                 5 + sumRange(4)
  116.                     4 + sumRange(3)
  117.                        3 + sumRange(2)
  118.                            2 + sumRange(1)
  119.                                  1 + sumRange(0)
  120.                                       0
  121.  
  122. */
  123.  
  124. // function sumRange(num){
  125. //   if(num === 0) return 0
  126. //   console.log(num)
  127. //   return num + sumRange(num -1)
  128. // }
  129.  
  130. // sumRange(10)
  131.  
  132. //iterative solution
  133. //factorial  5! = 5 * 4 * 3 * 2 * 1
  134. // function factorial(num){
  135. //   let result = 1
  136. //   for(let i = num; i >= 1; i--){
  137. //     console.log(i)
  138. //     result *= i
  139. //   }
  140. //   console.log(result)
  141. // }
  142. // factorial(1)
  143.  
  144. //recursive solution
  145.  
  146. //factorial  5! = 5 * 4 * 3 * 2 * 1
  147. // function factorial(num){
  148. //   //must have a base case
  149. //   if(num === 0) return 1
  150. //   //must return and console right thing in right time(What you need!)
  151. //   //change function argument some sort of fashion
  152. //   return num * factorial(num-1)
  153. // }
  154. // console.log(factorial(5))
  155.  
  156. //impure recursive function
  157. // function createRange(num1, num2) {
  158. //   let rangeArr = []
  159. //   function helper(helperInput, targetNum = 0) {
  160. //     //modify the outerScoped variable
  161. //     rangeArr.push(helperInput)
  162. //     console.log(helperInput)
  163. //     if (helperInput === targetNum) return helperInput
  164. //     helper(helperInput - 1, targetNum)
  165. //   }
  166. //   helper(10, num1)
  167.  
  168. //   console.log(rangeArr)
  169. // }
  170.  
  171. //pure recursive function
  172. // function createRange(num1, num2) {
  173.  
  174. // }
  175.  
  176. // createRange(5, 10)
  177.  
  178. // function findOdds(arr) {
  179. //   const result = []
  180. //   function helper(helperInput) {
  181. //     //base case
  182. //     console.log(helperInput)
  183. //     if (helperInput.length === 0) return
  184. //     if (helperInput[0] % 2 !== 0) {
  185. //       result.push(helperInput[0])
  186. //     }
  187. //     helper(helperInput.slice(1))
  188. //   }
  189. //   helper(arr)
  190. // }
  191.  
  192. // findOdds([10, 11, 12, 13, 14, 15])
  193.  
  194. function findOdds(arr) {
  195.   let result = []
  196.   if (arr.length === 0) return result
  197.   if (arr[0] % 2 !== 0) {
  198.     result.push(arr[0])
  199.   }
  200.   result = result.concat(findOdds(arr.slice(1)))
  201.   return result
  202. }
  203.  
  204. console.log(findOdds([10, 11, 12, 13, 14, 15]))
  205.  
  206. function power(base, exponent) {
  207.   //iterative
  208.   // return base ** exponent
  209.   //recursive
  210.   if (exponent === 0) return 1
  211.  
  212.   return base * power(base, exponent - 1)
  213. }
  214.  
  215. console.log(power(2, 3))
  216. /*
  217.  
  218.  2 * power(2, 2)
  219.     2 * power(2, 1)
  220.         2 * power(2, 0)
  221.         1
  222. */
  223.  
  224. //product of array
  225. // function productOfArray(arr) {
  226. //   if (arr.length === 0) {
  227. //     return 1
  228. //   }
  229. //   return arr[0] * productOfArray(arr.slice(1))
  230. // }
  231. // console.log(productOfArray([1, 2, 3, 4]))
  232.  
  233. //fibronaci series
  234.  
  235. // FIBONACCI SOLUTION
  236. // 1, 2, 3, 5, 8, 13, 21, 34, 55
  237. // function fib(n){
  238. //     if (n <= 2) return 1;
  239. //     return fib(n-1) + fib(n-2);
  240. // }
  241.  
  242. // fib(4) + fib(3)
  243. // fib(2) + fib(1)
  244.  
  245. // 10 * 9
  246. // 10 * 9
  247. // 0 1
  248. // console.log(fib(5))
  249.  
  250. // (0, 1, 1, 2, 3, 5)
  251.  
  252. // function fib(n) {
  253. //   // const result = [0, 1]
  254. //   // for (let i = 2; i <= n; i++) {
  255. //   //   result.push(result[i - 1] + result[i - 2])
  256. //   // }
  257. //   // console.log(result[n])
  258. //   if (n <= 2) return 1
  259.  
  260. //   const result = fib(n - 1) + fib(n - 2)
  261. //   console.log(result)
  262. //   return result
  263. // }
  264.  
  265. // console.log(fib(10))
  266. // //iterative solution
  267. // function flatten(arr) {
  268. //   let newArr = []
  269. //   let i = 0
  270. //   while (i < arr.length) {
  271. //     if (!Array.isArray(arr[i])) {
  272. //       newArr.push(arr[i])
  273. //       console.log(newArr)
  274. //     } else {
  275. //       while (Array.isArray(arr[i])) {
  276. //         console.log(arr[i])
  277. //       }
  278. //     }
  279. //     console.log(arr[i])
  280.  
  281. //     i++
  282. //   }
  283. //   // newArr.push(arr[i])
  284.  
  285. //   console.log(newArr)
  286.  
  287. // }
  288.  
  289. function flatten(arr) {
  290.   var i = 0
  291.  
  292.   if (!Array.isArray(arr)) {
  293.     /* return non-array inputs immediately to avoid errors */
  294.     return arr
  295.   }
  296.  
  297.   while (i < arr.length) {
  298.     if (Array.isArray(arr[i])) {
  299.       arr.splice(i, 1, ...arr[i])
  300.     } else {
  301.       i++
  302.     }
  303.   }
  304.   return arr
  305. }
  306.  
  307. console.log(flatten([1, 2, 3, [4, [6], [5]]]))
  308.  
  309. //binary search
  310.  
  311. var searchInsert = function (nums, target) {
  312.   let lo = 0
  313.   let hi = nums.length - 1
  314.   let mid
  315.   while (lo <= hi) {
  316.     mid = Math.floor((lo + hi) / 2)
  317.     console.log(mid)
  318.     const midVal = nums[mid]
  319.     if (midVal === target) return mid
  320.     if (target > midVal) {
  321.       lo = mid + 1
  322.     } else {
  323.       hi = mid - 1
  324.     }
  325.   }
  326.   return -1
  327. }
  328.  
  329. console.log(searchInsert([1, 3, 5, 6, 7, 8], 8))
  330. // console.log(searchInsert([1, 3, 5, 6], 2))
  331.  
  332. /*
  333. we are looking for 9
  334.  
  335. [1, 2, 3, 4, 5, 6, 7, 8]   0+7 = 7/2 = 3.5 = 3
  336.  l        m           h
  337.  
  338. [1, 2, 3, 4, 5, 6, 7, 8]  7 + 4 = 11/2 = 5.5 = 5  
  339.              l  m     h  
  340.          
  341. [1, 2, 3, 4, 5, 6 , 7, 8]   7 + 6 = 13/2 = 6  
  342.                     l
  343.                        h  
  344.                     m
  345.  
  346. [1, 2, 3, 4, 5, 6 , 7, 8]   7 + 6 = 13/2 = 6  
  347.                       l
  348.                       h  
  349.                       m
  350. */
  351.  
  352. //6 3
  353.  
  354. // log₂³² = 5
  355. // 2 * 2 * 2 * 2 * 2 = 32
  356. var strStr = function (haystack, needle) {
  357.   if (needle === '') return 0
  358.   for (let i = 0; i <= haystack.length - needle.length; i++) {
  359.     let j = 0
  360.     for (; j < needle.length; j++) {
  361.       console.log(haystack[i +j], needle[j])
  362.       if (haystack[i + j] !== needle[j]) break
  363.     }
  364.     console.log(j)
  365.     if (j === needle.length) return i
  366.   }
  367.  
  368.   return -1
  369. }
  370.  
  371. console.log(strStr('mississippi', 'mississippi'))
  372.  
  373.  
  374. // --- Directions
  375. // Write a function that accepts a positive number N.
  376. // The function should console log a step shape
  377. // with N levels using the # character.  Make sure the
  378. // step has spaces on the right hand side!
  379. // --- Examples
  380. //   steps(2)
  381. //       '# '
  382. //       '##'
  383. //   steps(3)
  384. //       '#  '
  385. //       '## '
  386. //       '###'
  387. //   steps(4)
  388. //       '#   '
  389. //       '##  '
  390. //       '### '
  391. //       '####'
  392.  
  393. // function steps(n) {
  394. //   for (let row = 0; row < n; row++) {
  395. //     let stair = ''
  396. //     for (let column = 0; column < n; column++) {
  397. //       if (column <= row) {
  398. //         stair += '#'
  399. //       } else {
  400. //         stair += ' '
  401. //       }
  402. //     }
  403. //     console.log(stair)
  404. //   }
  405. // }
  406.  
  407.  
  408.  
  409. // --- Directions
  410. // Write a function that accepts a positive number N.
  411. // The function should console log a pyramid shape
  412. // with N levels using the # character.  Make sure the
  413. // pyramid has spaces on both the left *and* right hand sides
  414. // --- Examples
  415. //   pyramid(1)
  416. //       '#'
  417. //   pyramid(2)
  418. //       ' # '
  419. //       '###'
  420. //   pyramid(3)
  421. //       '  #  '
  422. //       ' ### '
  423. //       '#####'
  424.  
  425. // function pyramid(n) {
  426. //   //midpoint of proposed column
  427. //   const midPoint = Math.floor((2 * n - 1) / 2)
  428. //   for (let row = 0; row < n; row++) {
  429. //     let level = ''
  430. //     for (let column = 0; column < 2 * n - 1; column++) {
  431. //       if (midPoint - row <= column && midPoint + row >= column) {
  432. //         level += '#'
  433. //       } else {
  434. //         level += ' '
  435. //       }
  436. //     }
  437. //     console.log(level)
  438. //   }
  439. //   console.log(midPoint)
  440. // }
  441.  
  442.  
  443.  
  444.  
  445.  
  446. //   matrix(3)
  447. //     [[1, 2, 3],
  448. //     [8, 9, 4],
  449. //     [7, 6, 5]]
  450. //  matrix(4)
  451. //     [[1,   2,  3, 4],
  452. //     [12, 13, 14, 5],
  453. //     [11, 16, 15, 6],
  454. //     [10,  9,  8, 7]]
  455. function matrix(n) {
  456.   const results = []
  457.   for (let i = 0; i < n; i++) {
  458.     results.push([])
  459.   }
  460.   console.log(results)
  461.   let counter = 1
  462.   let startColumn = 0
  463.   let endColumn = n - 1
  464.   let startRow = 0
  465.   let endRow = n - 1
  466.   while (startColumn <= endColumn && startRow <= endRow) {
  467.     //top row
  468.     for (let i = startColumn; i <= endColumn; i++) {
  469.       results[startRow][i] = counter
  470.       counter++
  471.     }
  472.    
  473.     startRow++
  474.  
  475.     //right column
  476.     for (let i = startRow; i <= endRow; i++) {
  477.       results[i][endColumn] = counter
  478.       console.log(results[i][endColumn])
  479.       counter++
  480.     }
  481.     endColumn--
  482.     console.log(results)
  483.  
  484.     //Bottom row
  485.     for (let i = endColumn; i >= startColumn; i--) {
  486.       results[endRow][i] = counter
  487.       counter++
  488.     }
  489.     endRow--
  490.     console.log(endRow)
  491.     //start column
  492.     for (let i = endRow; i >= startRow; i--) {
  493.       results[i][startColumn] = counter
  494.       counter++
  495.     }
  496.  
  497.     startColumn++
  498.     // console.log(str)
  499.     // if (startColumn === endColumn && startRow === endRow) {
  500.     //   results[startColumn][startRow] = counter
  501.     // }
  502.     console.log(startColumn, endColumn, startRow, endRow)
  503.     console.log(results)
  504.   }
  505.  
  506. }
  507.  
  508. matrix(3)
  509.  
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!