第6章：LeetCode--数组（冒泡排序、快速排序）
2024-09-01 15:20:03
11. Container With Most Water
class Solution {
public:
int maxArea(vector<int>& height) {
int maxarea = 0;
int l = 0, r = height.size()-1;
if(height.size()<2) return maxarea;
while(l<r){
maxarea = max(maxarea, min(height[l],height[r])*(r-l));
if(height[l]<height[r])
l++;
else
r--;
}
return maxarea;
}
};
//Brute Force --Time Limit Exceed
/*class Solution {
public:
int maxArea(vector<int>& height) {
int maxarea = 0;
if(height.size()<2) return maxarea;
for(int i=0; i<height.size()-1; i++){
for(int j=i+1; j<height.size(); j++)
maxarea = max(maxarea, min(height[i],height[j])*(j-i));
}
return maxarea;
}
};*/
16. 3Sum Closest //最接近target的 三数和
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if(nums.size()<3) return 0;
if(nums.size() == 3) return nums[0]+nums[1]+nums[2];
sort(nums.begin(), nums.end());
//int diff = abs(nums[0]+nums[1]+nums[2]-target);
int diff = INT_MAX;
//int sum = 0, front, end, ret=diff;
int sum = 0, front, end, ret=0;
for(int i=0; i<nums.size(); i++){
front = i+1;
end = nums.size()-1;
while(front<end){
sum = nums[i]+nums[front]+nums[end];
if(sum == target) return target;
if(abs(sum-target)<diff){
diff = abs(sum-target);
ret = sum;
}
(sum > target) ? end-- : front++;
}
}
return ret;
}
};
49. Group Anagrams
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string s : strs) { //auto s: strs also ok
string t = s;
sort(t.begin(), t.end());
mp[t].push_back(s);
}
vector<vector<string>> anagrams;
for (auto p : mp) {
anagrams.push_back(p.second);
}
return anagrams;
}
};
819. Most Common Word
Input:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball" class Solution {
public:
string mostCommonWord(string paragraph, vector<string>& banned) { // Map out each banned word
// Go through each word, if it isn't in the banned list
// put it in another map and keep track of how many times it appears
// Keep two variables to maintain the mostCommonWord and how many times it appeared
// This prevents us from looping thorugh the map at the end to find the most common word map<string, int> bannedWords;
map<string, int> tracker; string mostCommonWord = "";
int mostCommonWordCount = 0; for(int x = 0; x < banned.size(); x++)
{
bannedWords[banned[x]] = 0;
} for(int x = 0; x < paragraph.length(); x++)
{
string temp = "";
while(x < paragraph.length() && paragraph[x] != ' ')
{
if(!isalpha(paragraph[x]))
{
break;
} temp += tolower(paragraph[x]);
x++;
} if(temp == " " || temp == "")
continue; if(bannedWords.count(temp) != 0)
continue;
else
{
tracker[temp]++; if(mostCommonWordCount < tracker[temp])
{
mostCommonWordCount = tracker[temp];
mostCommonWord = temp;
}
} } return mostCommonWord;
}
};
Question1？？？:
Input:
inputStr = awaglknagawunagwkwagl
num = 4 Output:
{wagl, aglk, glkn, lkna, knag, gawu, awun, wuna, unag, nagw, agwk, kwag}
Explanation:
Substrings in order are: wagl, aglk, glkn, lkna, knag, gawu, awun, wuna, unag, nagw, agwk, kwag, wagl
"wagl" is repeated twice, but is included in the output once.
class Solution {
public:
vector<string> numKLenSubstrNoRepeats(string S, int K) {
vector<string>ans;
int cnt = 0, ,i=0, j;
while(i < S.size() && j<k) {
if(S[i] == S[j]){
j++;
}else{
i = i-j+1;
j = 0;
}
if (j == K){
ans.push_back(S.substr(i-K, K));
i = i-j+1;
j = 0;
}
}
return ans;
}
};
数组排序
https://www.cnblogs.com/taotingkai/p/6214367.html
/* 冒泡排序 */
/* 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 */ （每次把最大值放后面）
/* 2. 对所有元素均重复以上步骤，直至最后一个元素 */
void bubbleSort (int arr[], int len) {
int temp;
int i, j;
for (i=0; i<len-1; i++) /* 外循环为排序趟数，len个数进行len-1趟 */
for (j=0; j<len-1-i; j++) { /* 内循环为每趟比较的次数，第i趟比较len-i次 */
if (arr[j] > arr[j+1]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
/* 每次选出最小的 */
void bubbleSort (int arr[], int len) {
int temp;
int i, j;
for (i=0; i<len-1; i++) /* 外循环为排序趟数，len个数进行len-1趟 */
for (j=i+1; j<len-1; j++) { /* 内循环为每趟比较的次数，第i趟比较len-i次 */
if (arr[i] > arr[j]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
/*快速排序*/
#include <iostream>
using namespace std;
void Qsort(int arr[], int low, int high){
if (high <= low) return;
int i = low;
int j = high + 1;
int key = arr[low];
while (true)
{
/*从左向右找比key大的值*/
while (arr[++i] < key)
{
if (i == high){
break;
}
}
/*从右向左找比key小的值*/
while (arr[--j] > key)
{
if (j == low){
break;
}
}
if (i >= j) break;
/*交换i,j对应的值*/
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*中枢值与j对应值交换*/
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
Qsort(arr, low, j - 1);
Qsort(arr, j + 1, high);
} int main()
{
int a[] = {6, 2, 7, 3, 8, 9};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}/*参考数据结构p274(清华大学出版社，严蔚敏)*/
求一个数组里面连续子集的和的最大值，比如[1,2,-4,7,8,-2,4]=>[7,8,-2,4]
思路：每次求出max(sub(i-1), arr[i])，看那个大取那个。
int arrMaxsub(int [] arr, int len){
int maxsum = arr[0];
for(int i=1; i<len; i++){
if(maxsum+arr[i] <arr[i])
maxsum = arr[i];
else
maxsum = maxsum+arr[i];
}
return maxsum;
}
最新文章
- 浅析java内存模型--JMM(Java Memory Model)
- Spark入门实战系列--10.分布式内存文件系统Tachyon介绍及安装部署
- js execCommand
- 关于L'Hopital法则
- Lab1--关于安装JUnit的简要描述
- 用批处理文件来手动启动和停止Oracle服务
- [工作积累] Google Play Game SDK details
- 使用自定义任务审批字段创建 SharePoint 顺序工作流
- string应用
- 晕，hibernate 的 merge和cascade="all-delete-orphan"要慎重合在一起使用
- php增删改查，自己写的demo
- C++中多重继承构造函数执行顺序
- centos单用户模式：修改ROOT密码和grub加密
- 2017-07-04（sudo wc sort）
- PHP7CMS 无条件前台GETSHELL
- IdentityServer4（8）- 使用密码认证方式控制API访问（资源所有者密码授权模式）
- Java int类型与String类型互转
- VS2015在win10上编译的程序不能在Win7上运行的原因
- 洛谷 P1076 寻宝 解题报告
- 理解 Linux 配置文件【转】