数组 + 区间

240 搜索二维数组矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5,返回 true。

给定 target = 20,返回 false。

思路:从最左下坐标开始

仔细观察矩阵左下角或者右上角,对于左下角,==往右走数字变大,往上走数字变小==,
那么我们从左下角出发,target比当前值大,我们就往右走,target比当前值小,我们就往上走,若target存在一定会找到

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return false;
        int i = matrix.size() - 1;
        int j = 0;
        while(i >= 0 && j < matrix[0].size()){
            if(matrix[i][j] > target)
                --i;
            else if(matrix[i][j] < target)
                ++j;
            else return true;
        }
        return false;
    }
};

1248 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1:

输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2:

输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。

示例 3:

输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16

思路:

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0,cnt = 0;
        int odd[n+2];
        for(int i = 0;i < n;++i){
            if(nums[i]%2 == 1)
                odd[++cnt] = i;
        }
        odd[0] = -1,odd[++cnt] = n;//边界处理
        for(int i = 1;i + k <= cnt;++i){
            ans += (odd[i] - odd[i - 1]) * (odd[i + k ] - odd[i + k - 1]);
        }
        return ans;
    }
};

数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

思路:

利用归并算法,在出现逆序归并情况时,更新计数器

如:

nums[i] > nums[j]时,意味着nums[i] 相对于 nums[j]是逆序的,之间的距离是j-i但是考虑到后面的归并,j的位置也不是不变的,因此,至少对于 [i:mid]这段距离是逆序的, 需要将计数器加上(mid - i + 1)

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/

class Solution {
public:
    int mergeSort(vector<int>& nums,vector<int>& tmp,int left,int right){
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        int cnt = mergeSort(nums,tmp,left,mid) + mergeSort(nums,tmp,mid + 1,right);
        int i = left,j = mid + 1;
        int k = left;
        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                tmp[k++] = nums[i++];
            }else{
                tmp[k++] = nums[j++];
                cnt += (mid - i + 1);
            }
        }
        while(i <= mid){
            tmp[k++] = nums[i++];
        }
        while(j <= right){
            tmp[k++] = nums[j++];
        }
        //将当前有序数组tmp更新到nums中去
        copy(tmp.begin() + left, tmp.begin() + right + 1, nums.begin() + left);
        return cnt;
    }
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);  
        return mergeSort(nums,tmp,0,n-1);
    }
};

如果要把一个序列(sequence)拷贝到一个容器(container)中去,通常用std::copy算法,代码如下:

std::copy(start, end, std::back_inserter(container));

这里,start和end是输入序列(假设有N各元素)的迭代器(iterator)container是一个容器,该容器的接口包含函数push_back。假设container开始是空的,那么copy完毕后它就包含N个元素,并且顺序与原来队列中的元素顺序一样。标准库提供的back_inserter模板函数很方便,因为它为container返回一个back_insert_iterator迭代器,这样,复制的元素都被追加到container的末尾了。

33 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

思路:

若nums[mid] != target
先判断是左区间有序还是右区间有序,再判断target在左区间还是在右区间。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0,right = n - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            if(nums[left] <= nums[mid]){//左区间有序
                if(nums[left] <= target && target <= nums[mid]){//target在左区间
                    right = mid - 1;
                }else{//target在右区间
                    left = mid + 1;
                }
            }else{//右区间有序
                if(nums[mid] <= target && target <= nums[right]){//target在右区间
                    left = mid + 1;
                }else{//target在左区间
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

56 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

思路:

让我们先来考虑一个比较简单的问题:

如果除了一个数字以外,其他数字都出现了两次,那么如何找到出现一次的数字?

答案很简单:全员进行异或操作即可。考虑异或操作的性质:对于两个操作数的每一位,相同结果为 000,不同结果为 111。那么在计算过程中,成对出现的数字的所有位会两两抵消为 000,最终得到的结果就是那个出现了一次的数字。

那么这一方法如何扩展到找出两个出现一次的数字呢?

如果我们可以把所有数字分成两组,使得:

两个只出现一次的数字在不同的组中;

相同的数字会被分到相同的组中。

那么对两个组分别进行异或操作,即可得到答案的两个数字。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int i = 0;i < n;++i){
            sum ^= nums[i];
        }
        int first = 1;
        while((sum & first ) == 0){
            first <<= 1;
        }
        int a = 0,b = 0;
        for(int i = 0;i < n;++i){
            if(nums[i] & first){
                a ^= nums[i];
            }else{
                b ^= nums[i];
            }
        }
        return vector<int> {a,b};
    }
};

最大重叠区间个数

已知小猪每晚都要约好几个女生到酒店房间。每个女生 i 与小猪约好的时间由 [si , ei]表示,其中 si 表示女生进入房间的时间, ei 表示女生离开房间的时间。由于小猪心胸开阔,思想开明,不同女生可以同时存在于小猪的房间。请计算出小猪最多同时在做几人的「多人运动」。

例子:
Input : [[ 0 , 30] ,[ 5 , 10 ] , [15 , 20 ] ]
OutPut :最多同时有两个女生的「三人运动」

思路

直觉:

我们来看下有哪些情况,看是否可以打开思路。 如下图:

img
(上面的情况,那么最大的人数是1,下面的情况最大的人数是2)

不难发现,除了关心开始时间,我们应该同样关心结束时间。 如果”相邻“的区间重合,则人数++,最后返回人数即可。

具体算法:

  • 按照女孩约会的开始时间进行一次升序排序

img

  • 然后用一个小顶堆,维护当前每个女孩约会的结束时间

     [![img](%E6%95%B0%E7%BB%84.assets/68747470733a2f2f747661312e73696e61696d672e636e2f6c617267652f30303753385a496c6c7931676538387567623931696a333063613036656466792e6a7067.jpeg)](https://camo.githubusercontent.com/443f2fd1c80617bb3b1356005429c6a69e5242cf/68747470733a2f2f747661312e73696e61696d672e636e2f6c617267652f30303753385a496c6c7931676538387567623931696a333063613036656466792e6a7067)
  • 然后当一个新的女孩出现的时候,判断一下是否和上一个女孩有重叠,如果有则入堆,即多人运动的人数+1。没有重叠的话(人数不变),我们可以弹出一个元素,保持堆的人数不变。
  • 堆的大小表示的就是多人运动的最大人数,返回堆的大小即可。

代码(C++)

class Solution {
public:
    int np(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>&b){
            return a[0] < b[0];
        });
        priority_queue<int, vector<int>, greater<int>> heap;
        for (int i = 0; i < intervals.size(); i++) {
            // 没重叠,弹出堆顶元素,并维持最小堆的性质不变
            if (!heap.empty() && heap.top() <= intervals[i][0]) {
                heap.pop();
            }
            // 女孩++
            heap.push(intervals[i][1]);
        }
        return heap.size();
    }
};

hash法

#include <bits/stdc++.h>
using namespace std;
#define up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
#define girl pair<int,int>   //first开始时间,second结束时间
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;
const int maxn = 1001;   //小猪每晚最多约的女生数量

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;    //小猪今晚约了n个女孩
    cin >> n;
    vector<girl> v;
    up(i,1,n)
    {
        int bg,ed;
        cin >> bg >> ed;
        v.push_back(mp(bg,ed));
    }
    int cnt[maxn];    //cnt[i]记录i时刻的多人运动人数
    ms(cnt,0);
    int ans = -INF;
    up(i,0,n-1)    //枚举
    {
        up(j,v[i].first,v[i].second)
        {
            cnt[j]++;
            ans = max(ans,cnt[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

区间合并

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

https://gblobscdn.gitbook.com/assets%2F-LrtQOWSnDdXhp3kYN4k%2F-LrtQYLCSR8P7gMTIQMt%2F-LrtQ_t9FC7xfZA0S44T%2F3.gif?generation=1571847827743527&alt=media

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        int n = intervals.size();
        vector<vector<int>> ans;
        vector<int> cur;
        if(intervals.size() == 0 || (intervals.size() == 1)) return intervals;
        cur = intervals[0];
        for(int i = 1;i < n;++i){
            if(intervals[i][0] <= cur[1] && intervals[i][1] >= cur[1]){
                cur[1] = intervals[i][1];
            }
            if(intervals[i][0] > cur[1]){
                ans.push_back(cur);
                cur = intervals[i];
            }
            if(i == n - 1)
                ans.push_back(cur);
        }
        return ans;
    }
};

区间重叠

给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的,并且已经排序。

返回这两个区间列表的交集。

(形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)

演示

示例:

输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
注意:输入和所需的输出都是区间对象组成的列表,而不是数组或列表。

思路:

双指针遍历

注意重叠区间是:{max(a1,b1),min(a2,b2)}

b2 < a2 时j++;其他情况:i++

https://gblobscdn.gitbook.com/assets%2F-LrtQOWSnDdXhp3kYN4k%2F-LrtQYLCSR8P7gMTIQMt%2F-LrtQ_dbojt04FrAL4bQ%2F4.gif?generation=1571847823484015&alt=media

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        int i = 0,j = 0;
        vector<vector<int>> ans;
        vector<int> cur;
        while(i < A.size() && j < B.size()){
            int a1 = A[i][0],a2 = A[i][1];
            int b1 = B[j][0],b2 = B[j][1];
            if(b2 >= a1 && b1 <= a2){
                ans.push_back({max(a1,b1),min(a2,b2)});
            }
            if(b2 < a2){
                j++;
            }else{
                i++;
            }
        }
        return ans;
    }
};

有序矩阵中的第k个最小数组和

给你一个 m * n 的矩阵 mat,以及一个整数 k ,矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

示例 1:

输入:mat = [[1,3,11],[2,4,6]], k = 5
输出:7
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。

示例 2:

输入:mat = [[1,3,11],[2,4,6]], k = 9
输出:17

示例 3:

输入:mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出:9
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。

示例 4:

输入:mat = [[1,1,10],[2,2,9]], k = 7
输出:12

提示:

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组

思路:

暴力解决法:每次多考虑一行,然后始终保证考虑后能取到第k小的结果

使用 vector<int> 记录各个行选一个数相加的和

  1. 记录的方法是,先保存第一行各数
  2. 然后把第二行的各数拿出来,组合相加
  3. 对其排列,超过 k 个就不需要保留了
  4. 相加之后记录回 ans ,下次拿出第三行各数,与其组合相加

    返回第 k 个最小数组和
    
class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int m=mat.size();
        int n=mat[0].size();
        vector<int> res(mat[0]);//将mat[0]的一串数字赋值给res
        for(int i=1;i<m;++i)
        {
            multiset<int> st;
            for(int x:res)
            {
                for(int y:mat[i])
                {
                    st.insert(x+y);
                }
            }//计算出前两行所有可能的解,放到st中,赋值给res,res代表着之前所有行的相加的所有可能解
            res.assign(st.begin(),st.end());
            res.resize(min(k,(int)res.size()));//对res长度随时进行修剪,丢去不必要的计算
        }
        return res[k-1];
    }
};

思路二:
先确定左右边界,即最小和与最大和,然后二分得到mid,每次判断和小于mid的数组有多少个,如果大于等于k那么更新r,否则更新l。

class Solution {
public:
//maxSum目标数组和,idx为当前的数组所在行,sum为当前数组和,cnt为第k大的意思
//数组和小于等于maxSum的不少于cnt个的数组
 void dfs(vector<vector<int>>& mat, int k, int maxSum, int idx, int sum, int& cnt) {
        if (idx == mat.size()) return;//每一行都扫描了
        if (sum > maxSum || cnt > k) return;
         //当期数组和超过目标数组和或者小于maxSum的数组和个数超过了k,及时剪枝
        //当前行不选其他数字,直接到下一行去选择
        dfs(mat, k, maxSum, idx + 1, sum, cnt);
        for (int j = 1; j < mat[idx].size(); j++) {
            int temp = sum + mat[idx][j] - mat[idx][0];//计算在只替换idx行某个数字时对应的数组和
            if (temp > maxSum) break;//数组和太大了,跳出
            cnt++;//比上个数组和大1,cnt++,到下一行深度优先搜索选数字
            dfs(mat, k, maxSum, idx + 1, temp, cnt);
        }
    }
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int l = 0;
        int r = 0;
        for (int i = 0; i < mat.size(); i++) {
            l += mat[i].front();
            r += mat[i].back();
        }
        //l为最小数组和,r为最大数组和
        int base = l;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int cnt = 1;
            dfs(mat, k, mid, 0, base, cnt);
            if (cnt < k) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        return r;
    }
};

小张刷题计划

为了提高自己的代码能力,小张制定了 LeetCode 刷题计划,他选中了 LeetCode 题库中的 n 道题,编号从 0 到 n-1,并计划在 m 天内按照题目编号顺序刷完所有的题目(注意,小张不能用多天完成同一题)。

在小张刷题计划中,小张需要用 time[i] 的时间完成编号 i 的题目。此外,小张还可以使用场外求助功能,通过询问他的好朋友小杨题目的解法,可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”,小张每天最多使用一次求助。

我们定义 m 天中做题时间最多的一天耗时为 T(小杨完成的题目不计入做题总时间)。请你帮小张求出最小的 T是多少。

示例 1:

输入:time = [1,2,3,3], m = 2

输出:3

解释:第一天小张完成前三题,其中第三题找小杨帮忙;第二天完成第四题,并且找小杨帮忙。
这样做题时间最多的一天花费了 3 的时间,并且这个值是最小的。

思路:

题意概述

给定一个数组,将其划分成 M 份,使得每份元素之和最大值最小,每份可以任意减去其中一个元素。

题解

如果不考虑每份可以任意减去一个元素,就是一个经典的二分问题,具有单调最优的性质:如果最大值为 t 可以满足条件划分,那么最大值为 t+1也可以。所以就直接二分最大值 t,找到最小满足条件的 t 即可。

本题加了一个条件:每份可以删除任意一个数组。为了能够让最大值最小,显然每份中删去的一定是最大元素,所以在二分判定可行性时,维护当前序列的最大值,然后记录删除最大值的结果,也就是说二分的判定是:是否可以让每组删除最大值之后,总和都小于等于 t。

  1. 找到一个数,把它作为分割后各个子数组的和的最大值
  2. 根据这个最大值,分割数组,使每个子数组的和都不超过这个最大值,根据题意顺序填充子数组
  3. 使用二分查找来确定这个值

    1. int l = 0;
    2. int r = INT_MAX; 注意这个值有可能比单一一个值还大
    3. 如果不能将数组中所有数字都分割进子数组,则表示这个最大值不够大
    4. 如果提前分割完了,说明这个值取得太大了
class Solution {
public:
    int minTime(vector<int>& time, int m) {
        if (time.size() <= m) return 0;
        int l = 0;
        int r = INT_MAX;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (canSplit(time, m, mid)) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        return r;
    }
//对time数组进行分割判断,是否在分数组总和为split_sum,分组个数最多为m情况下可以分割
    bool canSplit(vector<int>& time, int m, int split_sum) {
        int cnt = 0;
        int sum = 0;
        int maxT = 0;
        for (auto& t : time) {
            sum += t;//sum计算数组元素之和
            maxT = max(maxT, t);//maxT计算当前子数组的最大值
            if (sum - maxT > split_sum) {//如果去掉了子数组最大值后的子数组的和超过split_sum
                if (++cnt == m) return false;
                //当前分组个数+1,如果分组个数超出要求则说明当前方案不可行
                sum = t;//计算新的子数组
                maxT = t;//更新子数组最大值
            }
        }
        return true;
    }
};

分割数组的最大值

给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

示例:

输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

思路:

解题思路:

由题意可知:子数组的最大值是有范围的,即在区间[max(nums),sum(nums)] 之中。
l=max(nums)h=sum(nums)`mid=(l+h)/2`计算数组和最大值不大于mid对应的子数组个数 cnt(这个是关键!)
如果 cnt>m,说明划分的子数组多了,即我们找到的 mid 偏小,故 l=mid+1
否则,说明划分的子数组少了,即 mid 偏大(或者正好就是目标值),故 h=mid

#define LL long long
class Solution {
public:
    bool isOverflow(vector<int>& nums,int m,long split_sum){
        long sum = 0,cnt = 0;
        for(auto x:nums){
            sum += x;
            if(sum > split_sum){
                if(x > split_sum) return false;
                if(++cnt == m) return false;
                sum = x;
            }
        }
        if(sum > split_sum) return false;
        return true;
    }
    int splitArray(vector<int>& nums, int m) {
        long left = nums[0], right = 0;//int类型在这里不合适,因为h可能会超过int类型能表示的最大值
        for (auto i : nums)
        {
            right += i;
            left = left > i ? left : i;
        }
        while(left <= right){
            long mid = left + (right - left) / 2;
            if(isOverflow(nums,m,mid)){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
};

面试题29 顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

算法:

设计矩形四个点的坐标,每次打印从这些坐标点为基准开始

如果上方和右方已经打印完的情况下,四个顶点的位置不满足 top <= bottom && left <= right 就不需要再打印下方和左方的数字了,不然会发生重复打印的情况

打印过程

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return {};
        }

        int rows = matrix.size();
        int cols = matrix[0].size();
        int top = 0,bottom = rows - 1,left = 0,right = cols - 1;

        while(top <= bottom && left <= right){
            for(int col = left;col <= right;col++){
                ans.push_back(matrix[top][col]);
            }
            for(int row = top + 1;row <= bottom;row++){
                ans.push_back(matrix[row][right]);
            }
            if(top < bottom && left < right){
                for(int col = right - 1; col > left;col--){
                    ans.push_back(matrix[bottom][col]);
                }
                for(int row = bottom;row > top;row--){
                    ans.push_back(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }

        return ans;
    }
};

面试题50 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

示例:

s = "abaccdeff"
返回 "b"

s = ""
返回 " "

算法:

建立一个map,存储字符以及出现次数

//无序哈希表法

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char, int> mm;
        for (char& ch : s) ++mm[ch];
        for (char& ch : s) if (mm[ch] == 1) return ch;
        return ' ';
    }
};


//有序哈希表法
class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char, int> mm;
        int t[26] = { INT_MAX };
        for (int i = 0; i < s.size(); ++i) {
            ++mm[s[i]];
            t[s[i] - 'a'] = i;//多个同样的重复字符中的最后一个在数组的位置存在t中,只有一个字符出现的自然就只有一个位置
        }
        char ans = ' ';
        int mint = INT_MAX;
        for(auto& p:mm) //出现次数为1 并且 字符位置最靠前的
            if (p.second == 1 && t[p.first - 'a'] < mint) {
                ans = p.first;
                mint = t[p.first - 'a'];
            }
        return ans;
    }
};

1300 转变数组后最接近目标值的数组和

给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 target (最接近表示两者之差的绝对值最小)。

如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。

请注意,答案不一定是 arr 中的数字。

示例 1:

输入:arr = [4,9,3], target = 10
输出:3
解释:当选择 value 为 3 时,数组会变成 [3, 3, 3],和为 9 ,这是最接近 target 的方案。

示例 2:

输入:arr = [2,3,5], target = 10
输出:5

示例 3:

输入:arr = [60864,25176,27249,21296,20204], target = 56803
输出:11361

算法:

一、二分查找

class Solution {
public:
    int check(const vector<int>& arr, int x) {//计算value = x 的时候,数组的总和
        int ret = 0;
        for (const int& num: arr) {
            ret += (num >= x ? x : num);
        }
        return ret;
    }

    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        vector<int> prefix(n + 1);
        for (int i = 1; i <= n; ++i) {
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }//前缀和存储减少重复计算

        int l = 0, r = *max_element(arr.begin(), arr.end()), ans = -1;//r为排序后的数组的最大值
        //l为0
        //在数组中二分查找出 value = mid 时数组和最接近且不大于taget的ans = mid
        while (l <= r) {
            int mid = (l + r) / 2;//mid为中间值
            auto iter = lower_bound(arr.begin(), arr.end(), mid);//二分查找出数值为mid的第一个位置
            int cur = prefix[iter - arr.begin()] + (arr.end() - iter) * mid;//计算数组和
            if (cur <= target) {//如果数组和小于target,左边界l右移
                ans = mid;
                l = mid + 1;
            }
            else {//如果数组和大于target,右边界l左移
                r = mid - 1;
            }
        }
        int choose_small = check(arr, ans);//最接近且不大于taget
        int choose_big = check(arr, ans + 1);//最接近且不小于taget
        return abs(choose_small - target) <= abs(choose_big - target) ? ans : ans + 1;
    }
};

二、数学法

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        int size=arr.size();
        //输入异常情况
        if(size==0)
            return 0;
        //排序
        sort(arr.begin(),arr.end());
        for(int i=0;i<size;++i)
        {
            //对当前目标数target求size-i个元素的最接近平均整数
            double t=(double)target/(size-i);
            int m=t;
            //四舍五入
            if(t-m-0.5>0)
                ++m;
            //如果最小值大于当前平均值
            if(arr[i]>=m)
                return m;
            else
                //更新数据
                target-=arr[i];
        }
        return arr[size-1];
    }
}

c++二分查找函数

头文件: #include <algorithm>

二分查找的函数有 3 个: 参考:C++ lower_bound 和upper_bound

lower_bound(起始地址,结束地址,要查找的数值) 返回的是数值 第一个 出现的位置。

upper_bound(起始地址,结束地址,要查找的数值) 返回的是数值 最后一个 出现的位置。

binary_search(起始地址,结束地址,要查找的数值) 返回的是是否存在这么一个数,是一个bool值

1 函数lower_bound() 参考:有关lower_bound()函数的使用

功能:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置.

注意:如果所有元素都小于val,则返回last的位置,且last的位置是越界的!!

2 函数upper_bound()

功能:函数upper_bound()返回的在前闭后开区间查找的关键字的上界,返回大于val的第一个元素位置

注意:返回查找元素的最后一个可安插位置,也就是“元素值>查找值”的第一个元素的位置。同样,如果val大于数组中全部元素,返回的是last。(注意:数组下标越界)

PS

​ lower_bound(val):返回容器中第一个值【大于或等于】val的元素的iterator位置。

​ upper_bound(val): 返回容器中第一个值【大于】

最后修改:2020 年 07 月 13 日 07 : 28 PM
如果觉得我的文章对你有用,请随意赞赏