刷题随笔02

---

01 绳子覆盖最多的节点

题目：

给定一个有序数组arr，代表坐落在X轴上的点，给定一个正数K，代表绳子的长度，返回绳子最多压中几个点？
即使绳子边缘处盖住点也算盖住

例如，arr = [1, 3, 4, 7, 13, 16, 17], target = 4, 子数组[3, 4, 7]满足所有节点被覆盖

解析：

1. 普通解

利用贪心，每一个点向前推，记录每个节点前target距离内覆盖个数最大值，一次遍历

小优化：数组有序，每个点向前找符合条件的节点个数，二分搜索优化，复杂度O(Nlog(N))

2. 最优解

双指针，L和起始位置指向0，arr[R] - arr[L] <= target, R++向右移动；arr[R] - arr[L] > target, L++向左移动。绳子起始边缘为L的最大覆盖节点个数，依次遍历。复杂度O(N)

//法一：贪心+二分搜索
int maxPoint1(vector<int>& arr, int target) {
    int res = 1;
    for (int i = 0; i < arr.size(); i++) {
        int nearest = nearestIndex(arr, i, arr[i] - target);
        res = max(res, i - nearest + 1);
    }
    return res;
}
//二分搜索函数
int nearestIndex(vector<int>& arr, int R, int value) {
    int L = 0;
    int index = R;
    while (L < R) {
        int mid = L + (R- L) / 2;
        if (arr[mid] >= value) {
            index = mid;
            R = mid - 1;
        } else {
            L = mid + 1
        }
    }
    return index;
}
//法二：贪心+双指针，滑动窗口
int maxPoint1(vector<int>& arr, int target) {
    int left = 0, right = 0;
    int n = arr.size();
    int count = 0;
    while (left < n) {
        while (right < n && arr[right] - arr[left] <= target) {
            right++;
        }
        count = max(count, right - left);
        left++;
    }
    return count;
}

02 两种字符最少交换次数

题目：

一个数组中只有两种字符’G’和’B’，可以让所有的G都放在左侧，所有的B都放在右侧
或者可以让所有的G都放在右侧，所有的B都放在左侧，但是只能在相邻字符之间进行交换操作，返回至少需要交换几次

解析：

贪心，遍历遇到第一个G，移到0位置，遇到第二个G，移到位置1……，双指针

int minStep(string s) {
    if (s.size() == 0) return 0;
    int step1 = 0;
    int gi = 0;
    //G在左边，B在右边
    for (int i = 0; i< s.size(); i++) {
        if (s[i] == 'G') {
            step1 += i - gi;
            gi++;
        }
    }
    int step2 = 0;
    int bi = 0;
    //G在右边，B在左边
    for (int i = 0; i< s.size(); i++) {
        if (s[i] == 'B') {
            step2 += i - bi;
            bi++;
        }
    }
    return min(step1,step2);
}

03 数组目标和为target的所有排列个数

题目：

给定一个数组arr，你可以在每个数字之前决定+或者-但是必须所有数字都参与，再给定一个数target
请问最后算出target的方法数

leetcode：494

解析：

1. 递归暴力求解

//递归暴力解
int findTargetSumWays1 (vector<int>& arr, int target) {
    return process(arr, 0, target);
}

//递归函数，可以自由使用arr[index...]所有的数字
//能够得出target这个数，方法数是多少，返回
int process1(vector<int>& arr, int index,int target) {
    if (index == arr.size()) { //base case
        return target ==0 ? 1 : 0;
    }
    return process1(arr, index + 1, target - arr[index]) + process1(arr, index + 1, target + arr[index]);
}

2. 动态规划，记忆化搜索

• 假设将arr变为非负数组，前面进行加减不影响
• 非负arr累加和为sum，target > sum 则不存在
• target与sum的奇偶性不一致，不存在
• 取正集合和为P，取负集合和为N，P - N = target, p + N = sum, ==> p = (sum + target) / 2,转化为取正集合和为P的组合有多少个
• 二维动态规划的空间压缩

int findTargetSumWays2 (vector<int>& arr, int target) {
    int sum = 0;
    for (int  n : arr) {
        sum += n;
    }
    if (sum < target || ((sum & 1) ^ (target & 1)) != 0) {
        return 0;
    }
    return subset(arr, (sum + target) / 2);
}

int subset(vector<int>& arr, int target) {
    vector<int> dp(target + 1);
    dp[0] = 1;
    for (int n : arr) {
        for (int i = target; i >= n; i--) {
            dp[i] += dp[i - n];
        }
    }
    return dp[target];
}

04 总体最多收入分配

题目：

现有司机N*2人，调度中心会将所有司机平分给A、B两区域，i号司机去A可得收入为income[i][0]，去B可得收入为income[i][1], 返回能使所有司机总收入最高的方案是多少钱?

解析：

1. 递归暴力 O(N^2)

//  income -> N * 2 的矩阵 N是偶数！
// 0 [9, 13]
// 1 [45,60]
int maxMoney1(vector<vector<int>>& income) {
    int N = income.size();
    if (N < 2 || (N & 1) != 0) {
        return 0; //N为奇数返回0
    }
    int M = N >> 1; //M = N / 2, 去A地区
    return process1(income, 0, M);
}
// index.....所有的司机，往A和B区域分配！
// A区域还有rest个名额!
// 返回把index...司机，分配完，并且最终A和B区域同样多的情况下，index...这些司机，整体收入最大是多少！
int process1(vector<vector<int>>& income, int index, int rest) {
    if (index == income.size()) return 0; 
    // 还剩下司机！
    if (income.size() - index == rest) { //B区域满了
        return income[index][0] + process1(income, index + 1, rest - 1);
    }
    if (rest == 0) {	//A区域满了
        return income[index][1] + process1(income, index + 1, rest);
    }
    // 当前司机，可以去A，或者去B
    int p1 = income[index][0] + process1(income, index + 1, rest - 1);
    int p2 = income[index][1] + process1(income, index + 1, rest);
    return max(p1, p2);
}

2. 动态规划

int maxMoney2(vector<vector<int>>& income) {
    int N = income.length;
    int M = N >> 1;
    vector<vector<int>> dp(N + 1, vector<int>(M + 1));
    for (int i = N - 1; i >= 0 ; i--) {
        for (int j = 0; j <= M; j++) {
            if (N - i == j) {
                dp[i][j] = income[i][0] + dp[i + 1][j - 1];
            } else if (j == 0) {
                dp[i][j] = income[i][1] + dp[i + 1][j];
            } else {
                int p1 = income[i][0] + dp[i + 1][j - 1];
                int p2 = income[i][1] + dp[i + 1][j];
                dp[i][j] = max(p1, p2);
            }
        }
    }
    return dp[0][M];
}

05 含有SetAll功能的哈希表

题目：

设计有setAll功能的哈希表，put、get、setAll方法，时间复杂度O(1)

setAll(num), 将所有的key对应的value值改为num

解析：

加入时间戳，记录加入的时间，key -> int, value -> (int, long)

setAlltime默认无穷大，调用setAll(num)后，时间戳早于当前值的进行更新，setAlltime更新为当前时间

public static class MyValue<V> {
		public V value;
		public long time;

		public MyValue(V v, long t) {
			value = v;
			time = t;
		}
	}

public static class MyHashMap<K, V> {
    private HashMap<K, MyValue<V>> map;
    private long time;
    private MyValue<V> setAll;

    public MyHashMap() {
        map = new HashMap<>();
        time = 0;
        setAll = new MyValue<V>(null, -1);
    }

    public void put(K key, V value) {
        map.put(key, new MyValue<V>(value, time++));
    }

    public void setAll(V value) {
        setAll = new MyValue<V>(value, time++);
    }

    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        if (map.get(key).time > setAll.time) {
            return map.get(key).value;
        } else {
            return setAll.value;
        }
    }
}

06 最长无重复字串的子串长度

题目：

求一个字符串中，最长无重复字符子串长度

解析：

子串子数组问题，想每个i结尾时，满足条件的情况，无重复的子串长度dp[i]

从第i个位置向前推影响因素：某个位置与i位置的字符相同，或者i-1位置向左推的距离

可以滑动窗口

也可动态规划：

int lengthOfLongestSubstring(string s) {
    if (s.size() == 0) return 0;
    //acsii取值范围0~255
    vector<int> map(256);
    //map存放上次出现的位置
    for (int i = 0; i < 256; i++) {
        map[i] = -1; //初始默认出现在-1位置
    }
    map[s[0]] = 0;
    int n = s.size();
    int ans = 1;
    int pre = 1;//上一个位置，向左推了多长
    for (int i = 1; i < n; i++) {
        pre = min(i - map[s[i]], pre + 1);
        ans = max(ans, pre);
        map[s[i]] = i;
    }
    return ans;
}

07 差值为k的数对的最大组数

题目描述：

给定一个数组arr，代表每个人的能力值。再给定一个非负数k，如果两个人能力差值正好为k，那么可以凑在一起比赛
一局比赛只有两个人，返回最多可以同时有多少场比赛

解析：

数组arr排序后，滑动窗口求解+贪心

暴力解：全排列寻找

//暴力解
int maxPairNUm1(vector<int>& arr, int k) {
    if (k < 0) return -1;
    return process1(arr, 0, k);
}
//暴力递归函数
int process1(vector<int>& arr, int index, int k) {
    int ans = 0;
    if (index == arr.size()) {	//全排列
        for (int i = 1; i < arr.size(); i += 2) {
            if (arr[i] - arr[i - 1] == k) {
                ans++;
            }
        }
    } else {
        for (int r = index; r < arr.size(); r++) {
            swap(arr[index], arr[r]);
            ans = max(ans, process1(arr, index + 1, k));
            swap(arr[index], arr[r]);
        }
    }
    return ans;
}

// 时间复杂度O(N*logN)
int maxPairNum2(vector<int>& arr, int k) {
    if (k < 0 || arr.size() < 2) return 0;
    sort(arr.begin(), arr.end());//排序，满足单调性，先满足小值的情况
    int ans = 0;
    int N = arr.size();
    int L = 0, R = 0;//双指针窗口
    vector<bool> usedR(N, 0);
    while (L < N && R < N) {
        if (usedR[L]) {
            L++;
        } else if (L >= R) {
            R++;
        } else { // 不止一个数，而且都没用过！
            int dis = arr[R] - arr[L];
            if (dis == k) {
                ans++;
                usedR[R++] = true;
                L++;
            } else if (dis < k) {
                R++;
            } else {
                L++;
            }
        }
    }
    return ans;
}

08 最多载两个人的船同时过河问题

题目描述：

给定一个正数数组arr，代表若干人的体重，再给定一个正数limit，表示所有船共同拥有的载重量，每艘船最多坐两人，且不能超过载重
想让所有的人同时过河，并且用最好的分配方法让船尽量少，返回最少的船数
Leetcode链接 : https://leetcode.com/problems/boats-to-save-people/

解析：

先排序，如果arr中某个值大于limit，返回无穷大不合题意。

寻找>=limit/2的右边界，边界右侧的值大于limit/2，两个指针指向边界左侧和右侧

相加和大于limit，左指针左移

一侧先耗尽，左侧未满足条件的数量除以2（向上取整），加上满足条件的数量，加上右侧剩余未满足条件的数量

//法一：
int numRescueBoats1(vector<int>& arr, int limit) {
    if (arr.size() == 0) return 0;
    int N = arr.size();
    sort(arr.begin(), arr.end());
    if (arr[N-1] > limit) return -1;
    int lessR = -1;
    for (int i = N -1; i >= 0; i--) {
        if (arr[i] <= limit / 2) {
            lessR = i;
            break;
        }
    }
    if (lessR == -1) return N;
    int L = lessR, R = lessR + 1;
    int noUsed = 0;
    while (L >= 0) {
        int solved = 0;
        while (R < N && arr[L] + arr[R] <= limit) {
            R++;
            solved++;
        }
        if (solved == 0) {
            noUsed++;
            L--;
        } else {
            L = max(-1, L - solved);
        }
    }
    int all = lessR + 1;
    int used = all - noUsed;
    int moreUnsolved = (N - all) - used;
    return used + ((noUsed + 1) >> 1) + moreUnsolved;
}
//法二：首尾双指针
int numRescueBoats2(vector<int>& arr, int limit) {
    sort(arr.begin(), arr.end());
    int ans = 0;
    int L = 0;
    int R = arr.size() - 1;
    int sum = 0;
    while (L <= R) {
        sum = L == R ? arr[L] : arr[L] + arr[R];
        if (sum > limit) {
            R--;
        } else {
            L++;
            R--;
        }
        ans++;
    }
    return ans;
}

09 子数组的最大累加和

题目描述：

返回一个数组arr中，子数组最大累加和

解析：

子数组以arr[i]结尾的最大累加和，求其最大值

dp[i] = max(dp[i - 1] + arr[i], arr[i])

int maxSubArray(vector<int>& arr) {
    if (arr.size() == 0) return 0;
    // 上一步，dp的值
    // dp[0]
    int pre = arr[0];
    int ans = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        pre = max(pre + arr[i], arr[i]);
        ans = max(pre, ans);
    }
    return ans;
}

10 分糖果问题

题目描述：

老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，返回老师至少需要准备多少颗糖果
进阶：在原来要求的基础上，增加一个要求，相邻的孩子间如果分数一样，分的糖果数必须一样，返回至少需要准备多少颗糖果

解析：
从左遍历，坡度值加一，从右遍历，坡度值加一，二者取最大值，以坡度大的为准

int candy(vector<int>& arr) {
    if (arr.size() == 0) {
        return 0;
    }
    int n = arr.size();
    vector<int> left(n);
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }
    vector<int> right(n);
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += max(left[i], right[i]);
    }
    return ans + n;
}

补充规则：相邻孩子分数一样则分的糖果数一样

解析：比左边大++，和左边相等不变，比左边小置1，右侧遍历同理

11 字符串交错组成问题

题目描述：

给定三个字符串s1、s2、s3，请你帮忙验证s3是否是由s1和s2交错组成的

Leetcode题目：https://leetcode.com/problems/interleaving-string/

解析：

长度s1.size() + s2.size() != s3.size()，不成立

动态规划，dp[i][j]长度为i的s1与长度为j的s2，能否组成长度i + j的s3

s1长度i，下标0 ~ i-1;

s2长度j，下标0 ~ j-1;

s3长度i + j, 下标0 ~ i + j - 1

每个位置最后一个字符可能来着s1或s2

bool isInterLeave(string s1, string s2, string s3) {
    int m = s1.size(), n = s2.size();
    if (s3.size() != m + n) return false;
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
    dp[0][0] = true;
    for (int i = 1; i <= m; i++) {
        if (s1[i - 1] != s3[i - 1]) {
            break;
        }
        dp[i][0] = true;
    }
    for (int j = 1; j <= n; j++) {
        if (s2[j - 1] != s3[j - 1]) {
            break;
        }
        dp[0][j] = true;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if ((s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1])) {
                dp[i][j] = true;
            }
        }
    }
    return dp[m][n];
}

12 求相等子树的数量

题目描述：

如果一个节点X，它左树结构和右树结构完全一样，那么我们说以X为头的树是相等树，给定一棵二叉树的头节点head，返回head整棵树上有多少棵相等子树

解析：
递归，head左子树的相等子树+head右子树的相等子树+head是否为相等子树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
// 时间复杂度O(N * logN)
int sameNumber1(TreeNode* head) {
    if (head == nullptr) return 0;
    return sameNumber1(head -> left) + sameNumber1(head -> right) + (same(head->left, head -> right) ? 1 : 0);
}

bool same(TreeNode* h1, TreeNode* h2) {
    if (h1 == nullptr ^ h2 == nullptr) return false;
    if (h1 == nullptr && h2 == nullptr) return true;
    //两个都不为空
    return h1 -> val == h2 -> val && same(h1 -> left, h2 -> left) && same(h1 -> right, h2 -> right);
}