ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವುದು


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಫೇಸ್ಬುಕ್
ಬ್ರೈನ್ಟೀಸರ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಎ, ಬಿ ಮತ್ತು ಸಿ ಸ್ಥಾನಗಳಲ್ಲಿ ನಮಗೆ ಮೂರು ಕಲ್ಲುಗಳನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ಕೆಳಗಿನ ಹಂತವನ್ನು ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ಬಾರಿ ನಿರ್ವಹಿಸುವ ಮೂಲಕ ನಾವು ಅವುಗಳನ್ನು ಸತತವಾಗಿ ಮಾಡಬೇಕು.
ಪ್ರತಿ ಹಂತದಲ್ಲೂ, ನಾವು ಎಡ ಕಲ್ಲು ಅಥವಾ ಬಲ ಕಲ್ಲನ್ನು ಆರಿಸಿ ಎಡದಿಂದ ಬಲ ಕಲ್ಲಿನ ವ್ಯಾಪ್ತಿಯ ನಡುವೆ ಎಲ್ಲೋ ಇಡುತ್ತೇವೆ.
ಚಿತ್ರವನ್ನು ಅನುಸರಿಸುವ ಮೂಲಕ ಇದನ್ನು ಉತ್ತಮವಾಗಿ ನಿಲ್ಲಿಸೋಣ:
ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವುದು
ಈ ಕಲ್ಲುಗಳನ್ನು ಸತತವಾಗಿ ಮಾಡಲು ನಾವು ಅಂತಹ ಕನಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಹಂತಗಳಿಗೆ ಉತ್ತರಿಸಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

a = 1, b = 2, c = 5
[1,2]

ವಿವರಣೆ: ಕಲ್ಲನ್ನು 5 ರಿಂದ 3 ಕ್ಕೆ ಸರಿಸಿ, ಅಥವಾ ಕಲ್ಲನ್ನು 5 ರಿಂದ 4 ಕ್ಕೆ 3 ಕ್ಕೆ ಸರಿಸಿ.

a = 4, b = 3, c = 2
[0,0]

ನಾವು ಯಾವುದೇ ಚಲನೆಗಳನ್ನು ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ.

a = 3, b = 5, c = 1
[1,2]

1 ರಿಂದ 4 ರವರೆಗೆ ಕಲ್ಲು ಸರಿಸಿ; ಅಥವಾ ಕಲ್ಲನ್ನು 1 ರಿಂದ 2 ರಿಂದ 4 ಕ್ಕೆ ಸರಿಸಿ.

ಅಪ್ರೋಚ್

ಮೊದಲು ಗರಿಷ್ಠ ಹಂತಗಳನ್ನು ಹೇಗೆ ಲೆಕ್ಕ ಹಾಕಬೇಕು ಎಂಬುದರ ಕುರಿತು ಮಾತನಾಡೋಣ. ವಿಪರೀತದಲ್ಲಿರುವ ಎರಡೂ ಕಲ್ಲುಗಳು 1 ಘಟಕದಿಂದ ಮಧ್ಯದ ಕಲ್ಲಿಗೆ ಹತ್ತಿರವಾದಾಗ ಮಾತ್ರ ಚಲಿಸುವಿಕೆಯ ಸಂಖ್ಯೆ ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ ಎಂದು ನಾವು ಸರಳವಾಗಿ ಹೇಳಲಾಗುವುದಿಲ್ಲ.
ಹೀಗೆ ಎಡ ಕಲ್ಲು ಮತ್ತು ಮಧ್ಯದ ಕಲ್ಲಿನ ನಡುವಿನ ಸ್ಥಾನಗಳ ಸಂಖ್ಯೆ + ಮಧ್ಯದ ಕಲ್ಲು ಮತ್ತು ಬಲ ಕಲ್ಲಿನ ನಡುವಿನ ಸ್ಥಾನದ ಸಂಖ್ಯೆ ಅವುಗಳನ್ನು ಸತತವಾಗಿ ಮಾಡಲು ನಮ್ಮ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಹಂತಗಳಾಗಿರುತ್ತದೆ.
ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವುದು
ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಹಂತಗಳನ್ನು ಹೇಗೆ ಲೆಕ್ಕ ಹಾಕುವುದು ಎಂಬುದು ಈಗ ಮುಖ್ಯ ಸಮಸ್ಯೆ. ಕೆಳಗಿನವುಗಳನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವ ಮೂಲಕ ನಾವು ಕನಿಷ್ಠವನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು ಪರಿಸ್ಥಿತಿಗಳು.
ಎಡ ಕಲ್ಲು ಮತ್ತು ಮಧ್ಯ ಕಲ್ಲಿನ ನಡುವಿನ ಸ್ಥಾನಗಳ ಸಂಖ್ಯೆ lspace ಮತ್ತು ಮಧ್ಯದ ಕಲ್ಲು ಮತ್ತು ಬಲ ಕಲ್ಲಿನ ನಡುವಿನ ಸ್ಥಾನಗಳ ಸಂಖ್ಯೆ rspace ಎಂದು ಕರೆಯೋಣ.
ಈ ಕಲ್ಲುಗಳ ಆರಂಭಿಕ ಸ್ಥಾನದ ಬಗ್ಗೆ ಈ ಕೆಳಗಿನ 4 ಸನ್ನಿವೇಶಗಳಲ್ಲಿ ಒಂದನ್ನು ಮಾತ್ರ ಹೇಳಬಹುದು.

1. ಕಲ್ಲುಗಳು ಈಗಾಗಲೇ ಸತತವಾಗಿ ಅಂದರೆ lspace = 0 ಮತ್ತು rspace = 0 ಆಗಿದ್ದರೆ min_steps = 0.

ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವುದು2. ಮೂರು ಕಲ್ಲುಗಳಲ್ಲಿ ಎರಡು ಸತತವಾಗಿದ್ದರೆ ಅಂದರೆ lspace = 0 ಅಥವಾ rspace = 0 ಆಗಿದ್ದರೆ ನಾವು ಕೇವಲ 1 ಹೆಜ್ಜೆಯಲ್ಲಿ ಮಧ್ಯದ ಕಲ್ಲಿನ ಹತ್ತಿರ ಹೆಚ್ಚಿನ ಕಲ್ಲುಗಳನ್ನು ಹಾಕಬಹುದು. ಹೀಗೆ min_steps = 1.

ಬ್ರೈನ್ಟೀಸರ್3. ಮೂರು ಕಲ್ಲುಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಎರಡು ನಡುವಿನ ಸ್ಥಳವು 1 ಆಗಿದ್ದರೆ lspace = 1 ಅಥವಾ rspace = 1 ಆಗಿದ್ದರೆ. ನಂತರ, ಒಂದೇ ಕಲ್ಲಿನಲ್ಲಿ ಎರಡು ಹತ್ತಿರವಿರುವ ಕಲ್ಲುಗಳ ನಡುವೆ (ಹತ್ತಿರವಿರುವ ಕಲ್ಲುಗಳ ನಡುವೆ ಕೇವಲ ಒಂದು ಸ್ಥಾನವನ್ನು ಹೊಂದಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ) ಇಡಬಹುದು.
ಆದ್ದರಿಂದ, ಅವುಗಳನ್ನು ಸತತವಾಗಿ ಮಾಡುವುದು ಕೇವಲ 1 ಹಂತದಲ್ಲಿ ಸಂಭವಿಸಬಹುದು. ಹೀಗಾಗಿ, min_steps = 1.

ಬ್ರೈನ್ಟೀಸರ್4. ಬೇರೆ ಎರಡೂ ಕಲ್ಲುಗಳನ್ನು ತಲಾ 1 ಹೆಜ್ಜೆ ಮೂಲಕ ಮಧ್ಯದ ಕಲ್ಲುಗಳ ನೆರೆಹೊರೆಯಲ್ಲಿ ಇಡಬಹುದು. ಹೀಗಾಗಿ, min_steps = 1 + 1 = 2.
ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವುದು

ಅನುಷ್ಠಾನ

ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವ ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

ಸತತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದವರೆಗೆ ಕಲ್ಲುಗಳನ್ನು ಚಲಿಸುವ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (1): ನಮ್ಮ ಅಲ್ಗಾರಿದಮ್‌ನಲ್ಲಿ ನಾವು ಸರಳ ಷರತ್ತುಬದ್ಧ ಹೇಳಿಕೆಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಒ (1) ಆಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (1): ಎಡ, ಬಲ, ಎಲ್‌ಸ್ಪೇಸ್, ​​ಗಾತ್ರ 2 ರ ಅನ್ಸ್ ಅರೇ ಮುಂತಾದ ಅಸ್ಥಿರಗಳನ್ನು ಹೊರತುಪಡಿಸಿ, ನಾವು ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ರಚಿಸಿಲ್ಲ, ಆದ್ದರಿಂದ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯು ಒ (1) ಆಗಿದೆ.