By Long Luo

This article is the solution of Problem 81. Search in Rotated Sorted Array II .

Brute Force

The Brute Force solution is so easy.

Problem 33. Search in Rotated Sorted Array.

1
2
3
4
5
6
7
8
9
10

public static int search_bf(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target) {
            return i;
        }
    }

    return -1;
}

Problem 81. Search in Rotated Sorted Array II:

1
2
3
4
5
6
7
8
9
10

public static boolean search_bf(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target) {
            return true;
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(n)\).
• Space Complexity: \(O(1)\).

Binary Search

Step-by-step Binary Search Algorithm:

We basically ignore half of the elements just after one comparison.

1. Compare target with the middle element;
2. If target matches with the middle element, we return the mid index;
3. Else If target is greater than the mid element, then target can only lie in the right half subarray after the mid element. So we recursive for the right half;
4. Else (target is smaller) recursive for the left half.

The Key of Binary Search is Narrow the Search Interval, aka reducing the scale of the problem.

Every round exclusive the interval where the target element must not exist, so the scale of the problem is gradually reduced.

Problem 33. Search in Rotated Sorted Array.

By Long Luo

This article is the solution Greedy: Sorting the Costs Array by What? of Problem 1029. Two City Scheduling .

Intuition

Let’s use it by Brute Force way.

The array \(\textit{costs}\) length is \(n\), so all the total choices will be \(2^n\), that’s a really huge number, so we must find a better way!

Greedy

Obiviously, it’s solved by greedy.

We need to sort the array \(\textit{costs}\) first.

But how to sort it?

By what?

If we choose a person who has lower \(cost_A\), but if his \(cost_B\) is more lower than another person’s \(cost_B\), that means the total cost will be larger.

If let \(2 \times n\) people all fly to city B, then choose \(n\) people of them change to fly city A, the company need a extra cost \(cost_A - cost_B\).

Ahha, Eureka! We Got It!

Sort the array by \(cost_A - cost_B\), the fist \(n\) person to city A, others go to city B.

Let’s coding.

By Long Luo

This article is the solution Greedy: Let the Heaviest Match the Lightest, if Not Matched, Let it Alone of Problem 881. boats to save people.

Intuition

We should let the Heaviest person match the Lightest person and create the most pairs whose weight didn’t exceed the limit, and so on.

If not, let the Heavy person occupy a whole boat.

I write the Brute Force code first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public int numRescueBoats(int[] people, int limit) {
    int len = people.length;
    Arrays.sort(people);
    int ans = 0;
    int idx = 0;
    int right = len - 1;
    while (idx < len) {
        while (idx < len && people[idx] == 0) {
            idx++;
        }

        while (right > idx && people[right] > 0 && people[idx] + people[right] > limit) {
            right--;
        }

        if (right > idx && people[idx] + people[right] <= limit) {
            people[idx] = 0;
            people[right] = 0;
            idx++;
            right--;
            ans++;
        } else if (idx < len) {
            people[idx] = 0;
            idx++;
            ans++;
        }
    }

    return ans;
}

It was ugly, then I wrote such code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 public int numRescueBoats(int[] people, int limit) {
     int len = people.length;
     Arrays.sort(people);
     int left = 0;
     int right = len - 1;
     int ans = 0;
     while (left <= right) {
         if (people[left] + people[right] <= limit) {
             left++;
	right--;
	ans++;
         } else {
	right--;
	ans++;
}
     } 

     return ans;
 }

Analysis

• Time Complexity: \(O(n \log n)\)
• Space Complexity: \(O(\log n)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

By Long Luo

This article is the solution Greedy: Reverse Thinking with Binary Algorithm of Problem 991. Broken Calculator.

Intuition

1. If \(\textit{startValue} \gt \textit{target}\), so return \(\textit{startValue} \gt \textit{target}\);
2. Considering such cases: \(2 \to 3\), \(2 \to 5\), \(1 \to 128\), \(1 \to 100\);
3. \(\textit{startValue} = \textit{startValue} \times 2^i\), when \(\textit{startValue}\) grows bigger, the last \(\textit{startValue}\) is closer to \(\textit{target} / 2\) that we only need double \(\textit{startValue}\) once.

So think reversly:

1. if target is even, the minimum operand is convert \(startValue\) equal to \(\textit{target} / 2 + 1\);
2. if target is odd, the minimum operand is convert \(startValue\) equal to \((\textit{target} + 1) / 2 + 2\).

Let’s coding.

By Long Luo

This article is the solution Greedy O(n) Solution with Image Explanation of Problem 1663. Smallest String With A Given Numeric Value .

Greedy

As we want to minimize the lexicographical order of the constructed string, let’s start from the beginning of the string, select the smallest letter that satisfies the requirements each time, then we get the final answer.

Suppose we are currently constructed to a certain position, as the picture below shows.

Including this position, there are still \(n_{rest}\) left to fill in, the remaining sum of these rest positions is \(k_{rest}\).

If we put a letter \(\textit{ch}\), and so the remaining \(n_{rest} - 1\) positions with the sum is \(k_{rest}\) must satisfy:

\[ 1 \times (n_{rest}-1) \leq k_{rest}-ch \leq 26 \times (n_{rest}-1) \]

can be:

\[ k_{rest}-26 \times (n_{rest}-1 ) \leq ch \leq k_{rest}-1 \times (n_{rest}-1) \]

So \(\textit{ch}\)

1. \(k_{rest} - 26 \times (n_{rest}-1) \leq 0\), we choose the character \(a\);
2. \(k_{rest} - 26 \times (n_{rest}-1) \gt 0\), we choose the character corresponding to this value.

Let’s write the code: