Let's Have Fun with LeetCode

labuladongOriginalAbout 2701 words

In the previous chapters on programming language fundamentals, I have introduced the basic syntax of each language and the usage of common data structures. Now, let's solve a few simple algorithm problems. This will allow us to practice using programming languages and get familiar with the process of solving problems on LeetCode.

If this is your first time solving problems, make sure to personally submit the following code on LeetCode to experience the process.

The solutions in this article may not be optimal

The focus of this article is to help beginners apply the programming language basics learned previously, rather than explaining algorithm strategies. Therefore, the approaches and solution codes provided are relatively simple and straightforward, and may not be the optimal solutions.

These algorithm problems will be explained and optimized in more detail in later chapters. As you delve deeper into data structures and algorithms, you will naturally gain a deeper understanding of them.

1. Two Sum

1. Two Sum | LeetCode |

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

As the first problem on LeetCode, this problem is quite classic. Let's try to solve it.

The simplest approach is brute-force. Use nested for loops, with the outer loop fixing the first number and the inner loop finding another number to see if their sum equals the target value.

java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[0];
    }
}

cpp

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return vector<int>{i, j};
                }
            }
        }
        return vector<int>{};
    }
};

python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

golang

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int{}
}

javascript

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
};

This is a simple use of the for loop and if condition. It is important to note that when we traverse j, we start from i+1 instead of i to avoid using the same element twice. Also, starting from 0 is unnecessary because combinations of elements before i with nums[i] have already been covered in previous iterations.

217. Contains Duplicate

217. Contains Duplicate | LeetCode |

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

This problem asks you to determine if there are duplicate elements in the array. Removing duplicates is a classic use case for hash sets, as they allow you to quickly check if an element is already present in the set.

We can insert each element of the array into a hash set one by one, and if we find an element that is already in the set, we immediately return true.

java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            // if the element already exists, return true
            if (set.contains(num)) {
                return true;
            }
            // put the element into the hash set
            set.add(num);
        }
        return false;
    }
}

cpp

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        for (int num : nums) {
            // if the element already exists, return true
            if (set.count(num)) {
                return true;
            }
            // put the element into the hash set
            set.insert(num);
        }
        return false;
    }
};

python

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        count = set()
        for num in nums:
            # if the element already exists, return True
            if num in count:
                return True
            # put the element into the hash set
            count.add(num)
        return False

golang

func containsDuplicate(nums []int) bool {
    count := make(map[int]bool)
    for _, num := range nums {
        // if the element already exists, return true
        if count[num] {
            return true
        }
        // put the element into the hash set
        count[num] = true
    }
    return false
}

javascript

var containsDuplicate = function(nums) {
    const count = new Set();
    for (const num of nums) {
        // if the element already exists, return true
        if (count.has(num)) {
            return true;
        }
        // put the element into the hash set
        count.add(num);
    }
    return false;
};

136. Single Number

136. Single Number | LeetCode |

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

This problem requires you to find the number that appears only once in an array. For issues related to counting elements, we typically use key-value pairs to store the relationship between elements and their occurrence counts. This involves using a data structure like a hash table.

java

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        // traverse the array, count the frequency of each number
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // find the number that only appears once
        for (int num : nums) {
            if (count.get(num) == 1) {
                return num;
            }
        }
        return -1;
    }
}

cpp

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> count;
        // traverse the array, count the frequency of each number
        for (int num : nums) {
            count[num]++;
        }

        // find the number that only appears once
        for (int num : nums) {
            if (count[num] == 1) {
                return num;
            }
        }
        return -1;
    }
};

python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = {}
        # traverse the array, count the frequency of each number
        for num in nums:
            count[num] = count.get(num, 0) + 1

        # find the number that only appears once
        for num in nums:
            if count[num] == 1:
                return num
        return -1

golang

func singleNumber(nums []int) int {
    count := make(map[int]int)
    // traverse the array, count the frequency of each number
    for _, num := range nums {
        count[num]++
    }

    // find the number that only appears once
    for _, num := range nums {
        if count[num] == 1 {
            return num
        }
    }
    return -1
}

javascript

var singleNumber = function(nums) {
    const count = new Map();
    // traverse the array, count the frequency of each number
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }

    // find the number that only appears once
    for (const num of nums) {
        if (count.get(num) === 1) {
            return num;
        }
    }
    return -1;
};

20. Valid Parentheses

20. Valid Parentheses | LeetCode |

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

This is a classic problem involving parentheses. Such problems can generally be solved using a stack. The approach is: when encountering a left parenthesis, push it onto the stack; when encountering a right parenthesis, pop the top left parenthesis from the stack to check if it matches with the right parenthesis.

java

class Solution {
    public boolean isValid(String str) {
        Stack<Character> left = new Stack<>();
        for (char c : str.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                // character c is a left parenthesis, push to the stack
                left.push(c);
            } else {
                // character c is a right parenthesis
                if (!left.isEmpty() && leftOf(c) == left.peek()) {
                    left.pop();
                } else {
                    // does not match the most recent left parenthesis
                    return false;
                }
            }
        }
        // check if all left parentheses have been matched
        return left.isEmpty();
    }

    char leftOf(char c) {
        if (c == '}') return '{';
        if (c == ')') return '(';
        return '[';
    }
}

cpp

class Solution {
public:
    bool isValid(string str) {
        stack<char> left;
        for (char c : str) {
            if (c == '(' || c == '{' || c == '[') {
                // character c is a left parenthesis, push to the stack
                left.push(c);
            } else {
                // character c is a right parenthesis
                if (!left.empty() && leftOf(c) == left.top()) {
                    left.pop();
                } else {
                    // does not match the most recent left parenthesis
                    return false;
                }
            }
        }
        // check if all left parentheses have been matched
        return left.empty();
    }

    char leftOf(char c) {
        if (c == '}') return '{';
        if (c == ')') return '(';
        return '[';
    }
};

python

class Solution:
    def isValid(self, s: str) -> bool:
        # use list to simulate stack
        left = []
        for c in s:
            if c in '({[':
                # character c is a left parenthesis, push to the stack
                left.append(c)
            else:
                # character c is a right parenthesis
                if left and self.leftOf(c) == left[-1]:
                    left.pop()
                else:
                    # does not match the most recent left parenthesis
                    return False
        # check if all left parentheses have been matched
        return not left

    def leftOf(self, c: str) -> str:
        if c == '}': return '{'
        if c == ')': return '('
        return '['

golang

func isValid(s string) bool {
    // use slice to simulate stack
    left := []rune{}
    for _, c := range s {
        if c == '(' || c == '{' || c == '[' {
            // character c is a left parenthesis, push to the stack
            left = append(left, c)
        } else {
            // character c is a right parenthesis
            if len(left) > 0 && leftOf(c) == left[len(left)-1] {
                left = left[:len(left)-1]
            } else {
                // does not match the most recent left parenthesis
                return false
            }
        }
    }
    // check if all left parentheses have been matched
    return len(left) == 0
}

func leftOf(c rune) rune {
    if c == '}' {
        return '{'
    }
    if c == ')' {
        return '('
    }
    return '['
}

javascript

var isValid = function(s) {
    const left = [];
    for (const c of s) {
        if (c === '(' || c === '{' || c === '[') {
            // character c is a left parenthesis, push to the stack
            left.push(c);
        } else {
            // character c is a right parenthesis
            if (left.length > 0 && leftOf(c) === left[left.length - 1]) {
                left.pop();
            } else {
                // does not match the most recent left parenthesis
                return false;
            }
        }
    }
    // check if all left parentheses have been matched
    return left.length === 0;
};

var leftOf = function(c) {
    if (c === '}') return '{';
    if (c === ')') return '(';
    return '[';
}

2073. Time Needed to Buy Tickets

2073. Time Needed to Buy Tickets | LeetCode |

There are n people in a line queuing to buy tickets, where the 0^th person is at the front of the line and the (n - 1)^th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the i^th person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k (0-indexed) to finish buying tickets.

Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation: 
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Example 2:

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

Constraints:

n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

This is a practical scenario algorithm problem and quite interesting. If we directly use a queue to simulate the entire process, we can definitely solve this problem. Let's look at the code directly:

java

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        // use queue to simulate the whole process
        // initialize the queue, store the id of each person
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < tickets.length; i++) {
            queue.offer(i);
        }

        int time = 0;
        while (!queue.isEmpty()) {
            // the person at the front of the queue buys a ticket
            int front = queue.poll();
            time++;
            tickets[front]--;
            
            if (front == k && tickets[front] == 0) {
                // if person k has bought the ticket, return the total time
                return time;
            }

            if (tickets[front] == 0) {
                continue;
            }

            // if the person needs to buy more tickets, put him back to the end of the queue
            queue.offer(front);
        }
        return time;
    }
}

cpp

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        // use queue to simulate the whole process
        // initialize the queue, store the id of each person
        queue<int> queue;
        for (int i = 0; i < tickets.size(); i++) {
            queue.push(i);
        }

        int time = 0;
        while (!queue.empty()) {
            // the person at the front of the queue buys a ticket
            int front = queue.front();
            queue.pop();
            time++;
            tickets[front]--;
            
            if (front == k && tickets[front] == 0) {
                // if person k has bought the ticket, return the total time
                return time;
            }

            if (tickets[front] == 0) {
                continue;
            }

            // if the person needs to buy more tickets, put him back to the end of the queue
            queue.push(front);
        }
        return time;
    }
};

python

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        # use queue to simulate the whole process
        queue = collections.deque()
        for i in range(len(tickets)):
            queue.append(i)

        time = 0
        while queue:
            # the person at the front of the queue buys a ticket
            front = queue.popleft()
            time += 1
            tickets[front] -= 1
            
            if front == k and tickets[front] == 0:
                # if person k has bought the ticket, return the total time
                return time

            if tickets[front] == 0:
                continue

            # if the person needs to buy more tickets, put him back to the end of the queue
            queue.append(front)
        return time

golang

func timeRequiredToBuy(tickets []int, k int) int {
    // use slice to simulate the whole process
    queue := make([]int, len(tickets))
    for i := 0; i < len(tickets); i++ {
        queue[i] = i
    }

    time := 0
    for len(queue) > 0 {
        // the person at the front of the queue buys a ticket
        front := queue[0]
        queue = queue[1:]
        time++
        tickets[front]--
        
        if front == k && tickets[front] == 0 {
            // if person k has bought the ticket, return the total time
            return time
        }

        if tickets[front] == 0 {
            continue
        }

        // if the person needs to buy more tickets, put him back to the end of the queue
        queue = append(queue, front)
    }
    return time
}

javascript

var timeRequiredToBuy = function(tickets, k) {
    // use array to simulate the whole process
    let queue = []
    for (let i = 0; i < tickets.length; i++) {
        queue.push(i)
    }

    let time = 0;
    while (queue.length > 0) {
        // the person at the front of the queue buys a ticket
        const front = queue.shift();
        time++;
        tickets[front]--;
        
        if (front === k && tickets[front] === 0) {
            // if person k has bought the ticket, return the total time
            return time;
        }

        if (tickets[front] === 0) {
            continue;
        }

        // if the person needs to buy more tickets, put him back to the end of the queue
        queue.push(front);
    }
    return time;
};

Summary & Outlook

Through practicing the problems mentioned above, you should now be familiar with how to tackle questions on LeetCode and how to use your programming skills to solve them.

Some of the solutions provided may not be the most optimal, but that's not a concern. Algorithm optimization follows certain patterns, and there's nothing extraordinary about it.

For beginners, taking this first step is already a significant achievement. As the saying goes, "A journey of a thousand miles begins with a single step." Just keep going.

The upcoming content will be divided into two main sections:

We will first delve into the principles of data structures and the application scenarios of some special ones. Data structures are effective tools for solving algorithm problems. For instance, in the examples above, how would you count elements in an array without a hash table? To master algorithms, you need to understand what common data structures are available, their strengths and limitations, and the time complexity of each of their operations.
We will then combine algorithm templates with extensive practice, helping you become proficient in various algorithmic problem-solving strategies. The algorithms discussed earlier are relatively simple, and the following problems will gradually increase in difficulty. However, there is no need to worry. The essence of algorithms is brute-force. Once you grasp some common brute-force thinking patterns, you can tackle any challenge and find a breakthrough in problem-solving.

Finally, I wish you success in independently navigating the vast sea of problems!

Let's Have Fun with LeetCode

1. 两数之和 https://leetcode.cn/problems/two-sum

1. Two Sum https://leetcode.com/problems/two-sum

217. 存在重复元素 https://leetcode.cn/problems/contains-duplicate

217. Contains Duplicate https://leetcode.com/problems/contains-duplicate

136. 只出现一次的数字 https://leetcode.cn/problems/single-number

136. Single Number https://leetcode.com/problems/single-number

20. 有效的括号 https://leetcode.cn/problems/valid-parentheses

20. Valid Parentheses https://leetcode.com/problems/valid-parentheses

2073. 买票需要的时间 https://leetcode.cn/problems/time-needed-to-buy-tickets

2073. Time Needed to Buy Tickets https://leetcode.com/problems/time-needed-to-buy-tickets

1. Two Sum

217. Contains Duplicate

136. Single Number

20. Valid Parentheses

2073. Time Needed to Buy Tickets

Summary & Outlook