Design Guru(Day2)

3. Sqrt

-> Binary Search approach

-> Since the floor of the square root of a number x lies between 0 and x/2 for all x > 1, we can use binary search within this range to find the square root

-> binary Search : O(logN)

-> O(1) for space complexity

class Solution {
  public int mySqrt(int x) {
    if(x<2) return x;
    int left = 2;
    int right = x/2;
    int pivot;
    long num;

    while(left<=right) {
      pivot = left + (right-left)/2;
      num = (long) pivot * pivot;
      if(num<x) {
        left = pivot+1;
      }else if(num>x) {
        right = pivot -1;
      }else {
        return pivot;
      }
    }
    return right;
  }
}

4. Reverse Vowels

public class Solution {
  public String reverseVowels(String s) {
    Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
    char [] ch = s.toCharArray();
    Stack<Character> st = new Stack<>();

    for (int i = 0; i < ch.length; i++) {
            if (set.contains(ch[i])) {
                st.push(ch[i]);
                ch[i] = '1';
            }
        }

        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == '1') {
                ch[i] = st.pop();
            }
        }

        return new String(ch);
    }
}

public class Solution {
  static final String vowels = "aeiouAEIOU";

  public String reverseVowels(String s) {
    int first = 0, last = s.length() - 1; // Initialize the two pointers
    char[] array = s.toCharArray();
    while (first < last) {
      while (first < last && vowels.indexOf(array[first]) == -1) {
        first++; // Skip non-vowel characters from the start
      }
      while (first < last && vowels.indexOf(array[last]) == -1) {
        last--; // Skip non-vowel characters from the end
      }
      char temp = array[first]; // Swap the vowels found at first and last
      array[first] = array[last];
      array[last] = temp;
      first++;
      last--;
    }
    return new String(array); // Return the reversed string
  }

// 있는지 없는지 확인을 indexOf로 할 수도 있다는 것 기억하기