算法题① —— 数组专栏

2024-05-12 07:30:07
开发
12

1. 滑动窗口

1.1 长度最小的子数组

力扣：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

int minSubArrayLen(int s, vector<int>& nums) {
	int result = INT32_MAX; 
    int sum = 0; // 子序列的数值之和
    int subLength = 0; // 子序列的长度
    int i = 0;
    for (int j = 0; j < nums.size(); j++) { 
       sum += nums[j];
        while (sum >= s) {
            subLength = j - i + 1;
            result = result < subLength ? result : subLength;
            sum -= nums[i++]; 
        }
    }
    return result == INT32_MAX ? 0 : result;
}

2. 哈希

2.1 求两数组的交集

力扣：https://leetcode.cn/problems/intersection-of-two-arrays/description/

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> result_set; 
    unordered_set<int> nums_set(nums1.begin(), nums1.end());
    for (int num : nums2) {
        if (nums_set.find(num) != nums_set.end()) {
            result_set.insert(num);
        }
    }
    return vector<int>(result_set.begin(), result_set.end());
}

2.2 两数之和

力扣：https://leetcode.cn/problems/two-sum/description/

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map <int,int> map;
    for(int i = 0; i < nums.size(); i++) {
        auto iter = map.find(target - nums[i]); 
        if(iter != map.end()) {
            return {iter->second, i};
        }
        map.insert(pair<int, int>(nums[i], i)); 
    }
    return {};
}

3. 双指针

3.1 三数之和

力扣：https://leetcode.cn/problems/3sum/description/

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) 
        if (nums[i] > 0) return result;
        if (i > 0 && nums[i] == nums[i - 1])  continue;
        int left = i + 1;
        int right = nums.size() - 1;
        while (right > left) {
            if (nums[i] + nums[left] + nums[right] > 0) right--;
            else if (nums[i] + nums[left] + nums[right] < 0) left++;
            else {
                result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                right--;
                left++;
            }
        }
    }
    return result;
}

4. 回溯

4.1 求子集（不包含重复元素）

力扣：https://leetcode.cn/problems/subsets/description/

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
	result.push_back(path); // 如果结果要包括自己就把push_back放在终止条件上面
	if (startIndex >= nums.size())  return;
	for (int i = startIndex; i < nums.size(); i++) {
		path.push_back(nums[i]);
		backtracking(nums, i + 1);
		path.pop_back();
	}
}
vector<vector<int>> subsets(vector<int>& nums) {
	backtracking(nums, 0);
	return result;
}

4.2 求子集（包含重复元素）

力扣：https://leetcode.cn/problems/subsets-ii/description/
和4.1的区别在于解集中可能会包含重复子集，需要去重（回溯+去重）

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
	result.push_back(path);
	for (int i = startIndex; i < nums.size(); i++) {
		// 对同一树层使用过的元素进行跳过
		if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
		path.push_back(nums[i]);
		used[i] = true;
		backtracking(nums, i + 1, used);
		used[i] = false;
		path.pop_back();
	}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
	vector<bool> used(nums.size(), false);
	sort(nums.begin(), nums.end()); // 去重需要排序
	backtracking(nums, 0, used);
	return result;
}

used[i - 1] == true，说明同一树枝使用过，可以重复选
used[i - 1] == false，说明同一树层使用过，不可重复选

4.3 递增子序列

力扣：https://leetcode.cn/problems/non-decreasing-subsequences/description/
特点：同一父节点下同一树层使用过的元素不能重复使用
和4.2的区别是：不能排序，只能在原数组基础上搜索

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
	if (path.size() > 1) {
		result.push_back(path);  // 只要path中数组个数大于一个就返回一个结果
	}
	unordered_set<int> uset; // 使用set对本层元素进行去重
	for (int i = startIndex; i < nums.size(); i++) {
		if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()) continue;
		uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
		path.push_back(nums[i]);
		backtracking(nums, i + 1);
		path.pop_back();
	}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
	backtracking(nums, 0);
	return result;
}

4.4 全排列（无重复数）

力扣：https://leetcode.cn/problems/permutations/description/

vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
	if (path.size() == nums.size()) {
		result.push_back(path);
		return;
	}
	for (int i = 0; i < nums.size(); i++) {
		if (used[i] == true) continue; // path里已经收录的元素，直接跳过
		used[i] = true;
		path.push_back(nums[i]);
		backtracking(nums, used);
		path.pop_back();
		used[i] = false;
	}
}
vector<vector<int>> permute(vector<int>& nums) {
	vector<bool> used(nums.size(), false);
	backtracking(nums, used);
	return result;
}

4.5 全排列（有重复数）

力扣：https://leetcode.cn/problems/permutations-ii/description/

vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
	if (path.size() == nums.size()) {
		result.push_back(path);
		return;
	}
	for (int i = 0; i < nums.size(); i++) {
		if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
		if (used[i] == false) {
			used[i] = true;
			path.push_back(nums[i]);
			backtracking(nums, used);
			path.pop_back();
			used[i] = false;
		}
	}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
	sort(nums.begin(), nums.end()); // 排序
	vector<bool> used(nums.size(), false);
	backtracking(nums, used);
	return result;
}

used[i - 1] == true，说明同一树枝使用过，可以重复选
used[i - 1] == false，说明同一树层使用过，不可重复选

5. 动态规划

5.1 最大子序和（连续子数组）

力扣：https://leetcode.cn/problems/maximum-subarray/description/

int maxSubArray(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    vector<int> dp(nums.size());
    dp[0] = nums[0];
    int result = dp[0];
    for (int i = 1; i < nums.size(); i++) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]); 
        if (dp[i] > result) result = dp[i]; 
    }
    return result;
}

5.2 最长上升序列（不是连续子数组）

力扣：https://leetcode.cn/problems/longest-increasing-subsequence/description/

int lengthOfLIS(vector<int>& nums) {
    if (nums.size() <= 1) return nums.size();
    vector<int> dp(nums.size(), 1);
    int result = 0;
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++)  if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
        if (dp[i] > result) result = dp[i]; 
    }
    return result;
}

5.3 最长连续递增子序列（连续子数组）

力扣：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

int findLengthOfLCIS(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    int result = 1;
    vector<int> dp(nums.size() ,1);
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1])  dp[i] = dp[i - 1] + 1;
        if (dp[i] > result) result = dp[i];
    }
    return result;
}

5.4 最长重复子数组（连续子数组）

力扣：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

int findLength(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
    int result = 0;
    for (int i = 1; i <= nums1.size(); i++) {
        for (int j = 1; j <= nums2.size(); j++) {
                if (nums1[i - 1] == nums2[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;
            if (dp[i][j] > result) result = dp[i][j];
        }
    }
    return result;
}

5.5 最长公共子序列（不是连续子序列）

力扣：https://leetcode.cn/problems/longest-common-subsequence/description/

int longestCommonSubsequence(string text1, string text2) {
    vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
    for (int i = 1; i <= text1.size(); i++) {
        for (int j = 1; j <= text2.size(); j++) {
            if (text1[i - 1] == text2[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;
            else  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[text1.size()][text2.size()];
}

原文地址:https://blog.csdn.net/qq_51148151/article/details/138731762 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1789437861276291072.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部