当前位置:网站首页>Number conclusion LC skimming review - 1

Number conclusion LC skimming review - 1

2022-07-06 02:16:00 Forina_ Han

217. There are duplicate elements

  • There are duplicate elements
  • Use Set Of size and Array Of length Just judge .
  • At first, we tried to divide and conquer , But the problem cannot be decomposed into the smallest problem , Because there are no duplicate elements in the left array , There are no duplicate elements on the right , It does not mean that there are no duplicate elements in the original array ( That is, when the left and right arrays contain the same elements , Such as [1,2,3,1]
  • Traversable arrays , Use hashMap Mark values , If duplicate marks are found, exit the traversal .
  • You can sort against arrays , Scan whether adjacent elements have the same value , Time for space .

53. Maximum subarray and

  • Maximum subarray and

  • Dynamic gauge ,dp[i] The subscript in the input array is i The largest subarray and .

  • Divide and conquer , Bisection decomposition array , And derive the parent optimal solution from the child optimal solution

    const mid = Math.floor((l + r) / 2);
       let L_res = R_res= {
          
           iSum: 0,
           lSum: 0,
           rSum: 0,
           aSum: 0
       };
       if(mid - 1 >= l) {
          
           L_res = getlmr(arr, l, mid - 1);
       }
       if(mid <= r) {
          
           R_res = getlmr(arr, mid, r)
       }
       const {
           iSum: L_iSum, lSum: L_lSum, rSum: L_rSum, aSum: L_aSum} = L_res
       const {
           iSum: R_iSum, lSum: R_lSum, rSum: R_rSum, aSum: R_aSum} = R_res;
       return {
          
           iSum: Math.max(L_iSum, R_iSum, L_rSum + R_lSum),
           lSum: Math.max(L_lSum, L_aSum + R_lSum),
           rSum: Math.max(R_rSum, R_aSum + L_rSum),
           aSum: L_aSum + R_aSum,
       }
    
原网站

版权声明
本文为[Forina_ Han]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/02/202202140034415765.html