Skip to main content

Brute Force

The brute force is not a specific algorithm but a common concept. The basic idea is straightforward: when there is no faster way to solve the problem, we will incrementally try all the possible solutions.

Some algorithms in the previous sections can be considered as brute force methods as well, for example, bfs, dfs, and backtracking.

Or in general, if there is no clue to solve a problem, maybe we should start with the brute force way first: to solve the problem first, and then try to optimize it.


Question List


Upper Layer

Comments

Post a Comment

Popular posts from this blog

Dynamic Programming - Easy Level - Question 1

Dynamic Programming - Easy Level - Question 1 Leetcode 1646  Get Maximum in Generated Array You are given an integer n. An array nums of length n + 1 is generated in the following way: nums[0] = 0 nums[1] = 1 nums[2 * i] = nums[i] when 2 <= 2 * i <= n nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n Return the maximum integer in the array nums​​​. Constraints: 0 <= n <= 100 Analysis: This question is quick straightforward: the state and transitional formula are given; the initialization is also given. So we can just ready the code to iterate all the states and find the maximum. See the code below: class Solution { public: int getMaximumGenerated(int n) { int res = 0; if(n<2) return n; vector<int> f(n+1, 0); f[1] = 1; for(int i=2; i<=n; ++i) { if(i&1) f[i] = f[i/2] + f[i/2+1]; else f[i] = f[i/2]; // cout<<i<<" "<<f[i]<<endl; ...
Post a Comment
Read more

Bit Manipulation - Medium Level

 Leetcode 416 Partition Equal Subset Sum Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Constraints: 1 <= nums.length <= 200 1 <= nums[i] <= 100 Analysis: There are different ways to solve this problem, such as dp with a time complexity of O(N^2). Since N is small to this question, so it is Okay to pass OJ. Besides the small N, the value of each element is also very small. So this gives us some chance to use "space to trad off time". The data structure to be used is bitset. For bitset, each bit can be either 0 or 1. The index of that bit can be used as the corresponding sum. When the bit is 1, means there is a sum with the value of its index. When a new number comes, this number needs to be added to all the previous sums, to form new "previous" sums. Thus for each number, we need to go through all the previous sums, the time co...
Post a Comment
Read more