Array
1.Array Definition
Array Initialization
//loops
int array[100];
for(int i=0;i<100;i++){
array[i]=i;
}
//using braces
int array[5]={1,2,3,4,5};
int array1[]={1,2,3,4,5};
//partial initializaiton, the first element sets to 1, every other element sets to 0
int array[5]={1};
//initialzie all elements to the same values, std::fill_n(array_name, number of elements, value)
int array[100];
std::fill_n(array, 100, -1);
STL
Vector Implementation
Vector API
- Find ```c++ //using std::find with array and pointer int array[]={10,20,30,40}; int *p;
p=std::find(array,array+4,30); if(p!=array+4){ std::cout«“element found in array”«endl; }
//using std::find with vector and iterator
std::vector
it=std::find(nums.begin(),nums.end(),30); if(it!=nums.end()) std::cout«“element found in vector”«endl;
* Resize
```c++
std::vector<int> array;
for(int i=1;i<10;i++) array.push_back(i);
array.resize(5);
array.resize(8,100);
array.resize(12)
- Insert
vector_name.insert(iterator::position, val)
vector_name.insert(iterator::position, size, val)
Array Basic Operation
Rotate Array
Note that reverse function range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
Complexity Linear in half the distance between first and last, swap elements.
Topic
Sum
- 259 3Sum Smaller(Q:A)
- 18 4Sum(Q:A)(two pointers)
- 325 Maximum Size Subarray Sum Equals K(Q:A)(Hash Table)
- 15 3Sum(Q:A)(Hash Table)
Permutations
Combinations
- 216 Combination Sum III(Q:A)
- 39 Combination Sum(Q:A)
- 77 Combinations(Q:A) Note that the subset we used when backtracking most cases should be passed as reference and pop_back during iteration.
Subarray
- House Robber II(Q:A)(double DP)
- 209 Minimum Size Subarray Sum(Q:A)(two pointers, binary search)
- 300 Longest Increasing Subsequence(Q:A)
Difference between lower_bound and upper_bound:
- lower_bound returns an iterator that is not less than val.
- upper_bound returns an iterator that is greater than val.
How to get index of lower_bound:
auto bound=lower_bound(array.begin(),array.end(),val);
int index = static_cast<int>(bound-array.begin());
std::cout << *bound << " is at " << bound - array.begin() << "\n";
Note that this will only work with a Random Access Iterator, type of bould-array.begin() is long.
- 309 Best Time to buy and sell stock with cooldown(DP, multi-states)(Q:A)
- 334 Increasing Triplet Subsequence(setting multiple states/variables and then compare)(Q:A) The key is to find smallest number B that there exists a number A before number B that is smaller than this number B.
Note that first always get the smallest number in the current length of array, second is not the real second smallest number in the current length of array, it is relative smallest number that is larger than current or previous smallest number in increasing order, note that if second smallest number index is smaller than current smallest number, it’s totally fine, it just means there must be a number that is smaller than second smallest number before. As long as there’s number larger than second number, even second number index is smaller than index of smallest number, it still means there must be a number that is smaller than second smallest number thus it returns true.
2D array
- 200 Number of Islands(Q:A)(DFS)
- 221 Maximal Square(Q:A)(DFS->DP)
- 286 Walls and Gates(Q:A)(DFS)
Think about when doing depth first search
- which position of array should be the first to be searched? Iteratively, from boundary, or starting with feature A or starting with feature B.
- how to set the boundary condition of DFS
- how to make sure each position not visited infinite times
- 304 Range Sum Query 2D - Immutable(Q:A)(DP)
How to initialize vector after it’s already declared?
class NumMatrix {
public:
Constructor(vector<vector<int>>& matrix) {
dp.resize(matrix.size(), vector<int>(matrix[0].size()));
...
}
private:
vector<vector<int>> dp;
};
Array Sort
- 215 Kth Largest Element in an Array(Q:A)
solution: nth_element, partial_sort, max heap, min heapDifference between nth_element and partial_sort
nth_element rearranges the nth position element in a sorted sequence, complexity on average is linear in the distance between first and last. partial_sort rearranges elements before the middle and sorted while remaining elements are left without any specific order. Complexity: Nlog(M) where N is this distance and M is the distance between first and middle.
- 280 wiggle sort
- 324 wiggle sort II(Q;A)
Think about why wiggle sort II starting from end of the array, check corner cases.
array search
220 Contains Duplicate III(Q:A)(map, integer overflow)
|n(i)-n(j)|<=t n(i)-t<=n(j)<=n(i)+t
std::map::lower_bound return iterator pointing to the first element in the container whose key is not consedered to go before K, k is Key to search for.
Boyer-Moore Voting Algorithm
int findMajority(vector<int>nums){
int maj_index=0;
int count=0;
for(int i=0;i<nums.size();i++){
if(nums[i]==nums[maj_index]){
count++;
}else{
count--;
}
if(count==0){
maj_index=i;
count++;
}
}
return nums[maj_index];
}
Array Search using hashmap
In-place Array Modification
By changing sign of each element in array:
Nested Array
Note that when reversely assigning or returning depth of nested list, using hash table as global variable to store value then loop through.
Note that when looping through array, some elements could be neglected if it’s already visited.