1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin() , g.end());
        sort(s.begin() , s.end());

        int childen = 0;
        int cookies = 0;
        
        while(cookies < s.size() && childen < g.size() )
        {
            if(s[cookies] >= g[childen]) childen++;
            cookies++;
        }
        return childen;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int candy(vector<int>& ratings) {
        if(ratings.empty()) return 0;

        int n = ratings.size();
        vector<int> ans(n , 1);

        for(int i = 0 ; i < n - 1; i++){
            if(ratings[i + 1] > ratings[i]) 
                ans[i + 1] = ans[i] + 1;
        }

        for(int i = n - 1 ; i >= 1 ; i--){
            if(ratings[i - 1] > ratings[i]) 
                ans[i - 1] = max(ans[i - 1] , ans[i] + 1);
        }

        int sum = 0;
        for(auto ch : ans) sum += ch;

        return sum;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() == 1)return 0;

        sort(intervals.begin() , intervals.end() , [](vector<int>& a , vector<int>& b){
            return a[1] < b[1]; //按照区间第二个数来排序,越小排的越前面
        });

        int pre = intervals[0][1] , total = 0 ;

        for(int i = 1 ; i < intervals.size() ; ++i)
        {
            //如果这两个有重叠,那么就略过这个元素往后继续找
            if(pre > intervals[i][0]){
                total++;
            }
            else{
                //没有重叠的话就要更换pre
                pre = intervals[i][1];
            }
        }
        return total;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;

	//对组排序,默认根据第一个元素排序
    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for(int i = 0 ; i < segs.size() ; i++){
        if(ed < segs[i].first){
            st = segs[i].first,ed = segs[i].second;
            if(i != 0) //如果不是第一个元素
                res.push_back({st,ed});
        }
        else{
            ed = max(ed , segs[i].second);
        }
    }
    //最后一次循环有两种结果:1,把最后第二个加入res  2,把最后两个合并成一个
    //无论是上面那两种情况,最后都有一个没法加入res
    
    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

int main()
{
    int n;
    scanf("%d", &n);

    vector<PII> segs;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {

        for(int i = 0; i< flowerbed.size() && n > 0 ; ++i)
        {
            if(flowerbed[i] == 1)continue;

            //到达此处意味着,上一个点为0
            //这里找出这个点两旁的元素是否为0,如果都为0那么可以插入
            //这里考虑到两端,一个没有前驱,一个没有后继,所以用三元运算符
            int pre = (i == 0 ? 0 : flowerbed[i - 1]);
            int next = (i == flowerbed.size() - 1 ? 0 : flowerbed[i + 1]);
            if(pre == 0 && next ==0){
                n--;
                flowerbed[i] = 1;
            }
        }
        return n == 0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
		  //这里必须要用引用,不然会报超时
        sort(points.begin() , points.end() , [](vector<int>& v1 , vector<int>& v2){
            return v1[1] < v2[1];//区间第二个数小的排前面，是便于后面找是否有重叠
        });

        int cur = points[0][1];
        int count = 1;
        for(int i =1 ; i < points.size() ; ++i)
        {
            if(cur >= points[i][0])continue;

            //若气球没有重叠，则再加一只箭
            cur = points[i][1];
            count++;
        }
        return count;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> ans;
        if(s.empty()) return ans;

        unordered_map<int , int> mm;
        for(int i = 0 ; i < s.size() ; i++){
            mm[s[i]] = i;
        } 

        int start = 0 , end = 0;
        for(int i = 0 ; i < s.size() ; i++){
            end = max(end , mm[s[i]]);

            // 若相等,则end这个下标是之前所有字母的最大下标
            // 则在这个位置可以把之前所有字母都隔离
            if(end == i){
                ans.push_back(end - start + 1);
                start = end + 1;
            }
        }

        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int total = 0;
        for(int i = 1 ; i < prices.size() ; i++){
            if(prices[i] > prices[i - 1])
            {
                total+=(prices[i] - prices[i - 1]);
            }
        }
        return total;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
using namespace std;
#define N 7

//钱的金额以及个数
int value[N] = { 100 , 50 , 20 , 10 , 5 , 2 , 1 };
int mcount[N] = { 10, 2, 3, 1 ,2 ,3 , 5 };

int getMomey(int momey)
{
	if (momey <= 0)return -1;

	int i = 0;
	int sheetNum = 0;

	while (1)
	{
		int m = momey / value[i];
		int num = mcount[i] < m ? mcount[i] : m;

		if (num == 0)
		{
			i++;
			continue;
		}
		sheetNum += num;
		momey -= value[i];

		cout << value[i] << "   " << num << endl;

		i++;

		if (momey == 0 )break;
		if (i == N - 1)return -1;
	}

	return sheetNum;
}

int main()
{
	int momey;
	cout << "请输入钱数 :";
	cin >> momey;

	int sheetNum = getMomey(momey);

	if (sheetNum == -1)
	{
		cout << "没有这么多钱" << endl;
	}
	else
	{
		cout << "一共用了" << sheetNum << "张钱" << endl;
	}

	system("pause");
}

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& numbers, int target) {
	int l = 0, r = numbers.size() - 1, sum;
	while (l < r) {
		sum = numbers[l] + numbers[r];
		if (sum == target) break;
		if (sum < target) ++l;
		else --r;
	}
	return vector<int>{l + 1, r + 1};
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int , int> mm;
        vector<int> v;

        for(int i = 0 ; i<numbers.size() ;++i)
        {
            int find = target - numbers[i];
            if(mm.count(find)!=0){
                v.push_back(mm[find] + 1);
                v.push_back(i + 1);
                return v;
            }
            else{
                mm[numbers[i]] = i;
            }
        }
        return v;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int pos = m-- + n-- - 1;
        //在这里 while(m>=0 && n>=0)，m条件必须在前面，如果n条件在前，
        //有一种错误情况，m初始就为0，导致第一个while循环和第二个循环都运行不了;
        while(n >= 0 && m >= 0){
            nums1[pos--] = nums1[m]>nums2[n]?nums1[m--]:nums2[n--];
        }

        while(m>=0){
            nums1[pos--] = nums1[m--];
        }

    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        /*
        这个方法,太好解了,可能不是面试官想要的解法
        for(int i = 0 ; i <n ; i++){
            nums1[m + i] = nums2[i];
        }

        sort(nums1.begin(),nums1.end());
        */
        
        int pos = m-- + n-- - 1;//先取出最大下标,再--
        while(m>=0 && n>=0){
            nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }

        while(n >= 0){
            nums1[pos--] = nums2[n--];
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL)return false;

       ListNode * slow = head , * fast = head;
       do
       {
           //因为快指针跑的快,如果有指针指向NULL代表不是环形链表
           //如果有一个为NULL,后续走两步也会报错.
           if(fast==NULL||fast->next==NULL)return false;
           slow = slow->next;
           fast = fast->next->next;
       }while(slow != fast);
        
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	bool hasCycle(ListNode *head) {
		ListNode *slow = head, *fast = head;
		// 判断是否存在环路
		do {
			if (!fast || !fast->next) return NULL;//如果不是环状则从这退出
			fast = fast->next->next;
			slow = slow->next;
		} while (fast != slow);//如果是环状则从这退出循环
        
		// 运行到这里就是存在环状，查找环路节点
		fast = head;
		while (fast != slow) {
			slow = slow->next;
			fast = fast->next;
		}
		return fast;
	}
};

1
2
3
4
5
6
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        
    }
}

1
2
3
4
5
6
7
8
9
10
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int q[N], c[N];  // 这里对于判断重复, 采用了计数排序的思想, 若数的范围较大, 或者数不是整数, 可以考虑用哈希表

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    int res = 0;
    for(int i = 0, j = 0; i < n; i++) {
        c[q[i]]++; // i往后移动一位, 计数加一, 将q[i]这个数纳入判重的集合
        while(c[q[i]] > 1) {  // 若在[j, i]区间内有重复元素的话, 只可能重复新加入的这个q[i], 只需判断q[i]的个数大于1
            // 有重复, j 往右移动一位
            c[q[j]]--; // 将j这个位置的数的计数减1, 即把q[j]从判重的集合中移除
            j++;
        }
        res = max(res, i - j + 1); // 针对该i, 找到最远的左端点j
    }
    printf("%d", res);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main() {
	int n, m, x;
	scanf("%d%d%d", &n, &m, &x);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < m; i++) scanf("%d", &b[i]);
	int i = 0, j = m - 1;
	while(i < n && j >= 0) {
		int sum = a[i] + b[j];
		if(sum < x) i++;
		else if(sum > x) j--;
		else break;
	}
	printf("%d %dn", i, j);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < m; i++) scanf("%d", &b[i]);

	int i = 0, j = 0;
	while(i < n && j < m) {
		if(a[i] == b[j]) {
			i++;
			j++;
		} else j++;
	}
	if(i < n) printf("Non");
	else printf("Yesn");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int ret = 0;

        //把这两个看成左指针右指针
        int Lptr=0 ;
        unordered_map<char,int> mm;

        for(int Rptr = 0 ; Rptr < len ; Rptr++)
        {
            //把每一个元素都加入哈希表中
            //就算有相同的元素，新加入的元素依然在会有自己的位置，
            //哈希表中元素和字符串中元素排列相同
            mm[s[Rptr]]++;
            
            //这里运用循环很关键，可以参图片来考虑
            while(mm[s[Rptr]] == 2)
            {
                //此时，把左指针向右移动，
                //那么窗口中就少了一个元素，所以要-- ， 此时符合情况
                mm[s[Lptr]]--;   
                Lptr++;
            }
            ret = max(ret , Rptr - Lptr + 1);
        }
        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool judgeSquareSum(int c) {
        long left = 0;
        long right = (int)sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isNo(string s , int L , int R){
        while(L<R){
            if(s[L]!=s[R]) return false;
            L++;
            R--;
        }
        return true;
    }

    bool validPalindrome(string s) {
        for(int L = 0 , R = s.size() - 1 ; L < R ; L++,R--){
            if(s[L]!=s[R]){
                return isNo(s,L+1,R)||isNo(s,L,R-1);
            }
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string ans = "" , dstr = "";
        for(int m = 0 ; m < dictionary.size() ; m++){
            dstr = dictionary[m];
            for(int i = 0 , j = 0 ; i < s.size() && j < dstr.size() ; i++){
                if(s[i] == dstr[j])j++;
                if(j == dstr.size()){
                    if(dstr.size() > ans.size() || 
                       (dstr.size() == ans.size() && ans.compare(dstr) > 0))
                    ans = dstr;
                }
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0;
        int l = 0 , r = x;
        int ans = 0;

        while(r > l){
            long mid = ((long)r + (long)l + 1) / 2;
            long a = mid * mid;

            if(a <= x){
                l = mid;
                ans = mid;
            }else{
                r = mid - 1;
            }
        }

        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    //主函数
     vector<int> searchRange(vector<int>& nums, int target) {
        int L = start(nums , target);
        int R = end(nums , target);

        vector<int> v{L , R};
        return v;
    }

    //取出下标最小的目标值
    int start(vector<int>& nums, int target) {
        //- 1 是为了取出第一个有用的值
        int L = 0 , R = nums.size() - 1 , ans = -1;
        while(R >= L){
            int mid = L + (R - L)/2;
            //一开始因为>所以移动,后来因为=移动找到最左边符合的值
            if(nums[mid] >= target){
                ans = mid;
                R = mid - 1;
            }else{
                L  = mid +1;
            }
        }
        if(ans == -1 || nums[ans] != target) return -1;
        return ans;
    }
    //取出下标最大的目标值
    int end(vector<int>& nums, int target) {
        int L = 0 , R = nums.size() - 1, ans = -1;
        while(R >= L){
            int mid = L + (R - L)/2;
            //一开始因为<所以移动,后来因为=移动找到最右边符合的值
            if(nums[mid] <= target){
                ans = mid;
                L  = mid +1;
                
            }else{
                R = mid - 1;
            }
        }
        if(ans == -1 || nums[ans] != target) return -1;
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
	int search(vector<int>& nums, int target) {
		int left = 0, right = nums.size() - 1;

		while (right >= left) {
			int mid = left + (right - left) / 2;

			if (nums[mid] == target)return mid;
            
			//[1,2,3,4,5] 但左指针和右指针分别指向1,2 查找元素2 在if有=的情况下,执行 右边界有序的else
            //在第一个没有=的情况下,执行 左边界有序else 则right = -1越界,出错
            //所以在两个数字的情况下,若要分成两部分则,第一个数一部分,第二个数一部分
            //所以if一个有=


			if (nums[mid] >= nums[left]) { //= 是为了接受两个元素情况下的中间元素
				//在左边有序的情况下,判断元素是否在左半侧
				if (target < nums[mid] && target >= nums[left]) {
					right = mid - 1;
				}
				else {
					left = mid + 1;
				}
			}
			else {
				if (target > nums[mid] && target <= nums[right]) {
					left = mid + 1;
				}
				else {
					right = mid - 1;
				}
			}

		}
		return -1;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//整数二分查找
#include <iostream>
#include <stdio.h>
using namespace std;

const int N = 1e6 + 10;
int q[N];
int n, m;


int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", &q[i]);

	while (m--)
	{
		int x;
		scanf("%d", &x);

		int l = 0, r = n - 1;
		//取第一个等于x的数，右边界等于mid
		while (l < r)
		{
			int mid = l + r >> 1;
			if (x <= q[mid])
				r = mid;
			else
				l = mid + 1;
		}
		if (q[l] != x)
			cout << "-1 -1" << endl;
		else
		{
			cout << l << " ";
			int l = 0, r = n - 1;
			//取最后一个等于x的数，左边界等于mid
			while (l < r)
			{
				int mid = l + r + 1 >> 1;
				if (x >= q[mid])
					l = mid;
				else
					r = mid - 1;
			}
			cout << l << endl;
		}
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;
	int x = q[l], i = l - 1, j = r + 1;
	while (i < j)
	{
		//如果12 12不先进行++，--操作的话，会造成死循环
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	//会一直存在(0,i)区间，死循环
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}
int main()
{
    //数组元素个数n
	scanf("%d", &n);
    //接收数组元素
	for (int i = 0; i < n; i++)
		scanf("%d", &q[i]);
    
	quick_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++)
		printf("%d ", q[i]);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
using namespace std;

const int N = 1e5 +10;
int n, k;
int q[N];

// 选取[l, r]区间内数组q第k小的数
int quick_select(int q[], int l, int r, int k) {
    if(l == r) return q[l]; // 找到答案
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        while(q[++i] < x);
        while(q[--j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    int left = j - l + 1;
    if(k <= left) return quick_select(q, l, j, k);
    else return quick_select(q, j + 1, r, k - left);
}

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    printf("%d", quick_select(q, 0, n - 1, k));
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int , vector<int> , less<int>> q;
        for(int i = 0 ; i < nums.size() ; i++){
            q.push(nums[i]);
        }

        for(int i = 0 ; i < k - 1; i++){
            q.pop();
        }

        return q.top();
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int , int> mm;
        for(auto & num : nums) mm[num]++;

        vector<pair<int , int>> vv;
        for(auto & it : mm) vv.push_back(it);
        sort(vv.begin() , vv.end() , [](pair<int , int> pa1 , pair<int , int> pa2){
            return pa1.second > pa2.second;
        });

        vector<int> ans;

        for(auto & a : vv){
            ans.push_back(a.first);
            if(ans.size() == k) return ans;
        }

        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int , int> mm;
        for(int x : nums) mm[x]++;

        priority_queue<pair<int , int>> pq;
        for(auto& p : mm)pq.push({p.second , p.first});

        vector<int> ans(k);
        for(int i = 0 ; i < k ; i++){
            ans[i] = pq.top().second;
            pq.pop();
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <stdio.h>
using namespace std;

const int N = 1e6 + 10;
int q[N], tmp[N];
int n;

void merge_sort(int q[], int l, int r)
{
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    //记录左右两边的起点
	int k = 0, i = l, j = mid + 1;
    
	while (i <= mid && j <= r)
		if (q[i] <= q[j])
			tmp[k++] = q[i++];
		else
			tmp[k++] = q[j++];
    
	while (i <= mid)
		tmp[k++] = q[i++];
    
	while (j <= mid)
		tmp[k++] = q[j++];

    //排好序的写回原来的数组
	for (i = l, j = 0; i <= r; i++, j++)
		q[i] = tmp[j];
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &q[i]);

	merge_sort(q, 0, n - 1);

	for (int i = 0; i < n; i++)
		printf("%d ", q[i]);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n;
int q[N], tmp[N];

// 返回区间[l, r]中的逆序对的数量
LL merge_sort(int q[], int l, int r) {
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL cnt = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); // 计算左右区间内各自的逆序对数量
    // 合并时, 计算左右两个区间中的数组成的逆序对
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            cnt += mid - i + 1;
            tmp[k++] = q[j++];
        }
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(int i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k];
    return cnt;
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    LL cnt = merge_sort(q, 0, n - 1);
    printf("%lld", cnt);
    return 0;
}

1
2
3
4
5
输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char , int> mm;
        for(char & ch : s) mm[ch]++;

        vector<pair<char , int>> v;
        for(auto pa : mm) v.push_back(pa);

        sort(v.begin() , v.end() , [](pair<char , int> p1 , pair<char , int> p2){
            return p1.second > p2.second;
        });

        string ss = "";

        for(auto pa : v){
            for(int i = 0 ; i < pa.second ; i++){
                ss.push_back(pa.first);
            }
        }

        return ss;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:

    int dir[5] = {1 , 0 , -1 , 0 , 1};
    int dfs(int x , int y , vector<vector<int>>& grid){
        
        int ans = 1;
        grid[x][y] = 0;//标记这个点不可再被访问

        for(int i = 0 ; i < 4 ; ++i){
            int nx = x + dir[i];
            int ny = y + dir[i+1];
           if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == 1){
               ans = ans + dfs(nx , ny , grid); 
           }
        }
        return ans;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for(int i = 0 ; i < grid.size() ; ++i){
            for(int j = 0 ; j < grid[0].size() ; ++j){
                if(grid[i][j] == 1){
                    ans = max(ans , dfs(i , j , grid));
                }
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//辅助函数
void dfs(int index, vector<vector<int>>& isConnected, vector<bool> & v) {

	v[index] = true;//这个节点已经被访问了
	for (int i = 0; i < isConnected.size(); ++i) {
		if (isConnected[index][i] == 1 && v[i] == false) {
			dfs(i, isConnected, v);
		}
	}
}
//主函数
int findCircleNum(vector<vector<int>>& isConnected) {
	int size = isConnected.size(), ans = 0;
	vector<bool> v(size, false);//先设为都没有被访问过


	for (int i = 0; i < size; ++i) {
		if (v[i] == false) {
			//不需要返回任何值,只需要遍历与当前节点相连的节点,并设为true
			dfs(i, isConnected, v);
			ans++;
		}
	}

	return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int row = 0, col = 0;
int dir[5] = { 1 , 0 , -1 , 0 , 1 };

void dfs(int x, int y, vector<vector<bool>> & vb, vector<vector<int>>& heights) {

	vb[x][y] = true;
	for (int i = 0; i < 4; ++i) {
		int nx = x + dir[i];
		int ny = y + dir[i + 1];
		if (nx >= 0 && nx < row && ny >= 0 && ny < col
			&& heights[nx][ny] >= heights[x][y] && vb[nx][ny] == false) {
			dfs(nx, ny, vb, heights);
		}
	}
}

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
	row = heights.size(); //行数
	col = heights[0].size();//列数
	vector<vector<bool>> P(row, vector<bool>(col, false)), A(row, vector<bool>(col, false));

	for (int i = 0; i < row; ++i) {
		dfs(i, 0, P, heights);//遍历最左边的那列,即靠近太平洋
		dfs(i, col - 1, A, heights);//遍历最右边的那一列,即靠近大西洋
	}
	for (int j = 0; j < col; ++j) {
		dfs(0, j, P, heights);//遍历最上面那一行,即靠近太平洋
		dfs(row - 1, j, A, heights);//遍历最下面那一行,即靠近大西洋
	}

	vector<vector<int>> v;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (P[i][j] && A[i][j]) v.push_back({ i , j });
		}
	}

	return v;
}