左老师算法直播

算法直播"/>

左老师算法直播

20210905左老师直播，讲解小红书、网易、腾讯、京东和阿里巴巴算法题目

1. 小红书

[0,4,7] ： 0表示这里石头没有颜色，如果变红代价是4，如果变蓝代价是7
[1,X,X] ： 1表示这里石头已经是红，而且不能改颜色，所以后两个数X无意义
[2,X,X] ： 2表示这里石头已经是蓝，而且不能改颜色，所以后两个数X无意义
颜色只可能是0、1、2，代价一定>=0
给你一批这样的小数组，要求最后必须所有石头都有颜色，且红色和蓝色一样多，返回最小代价
如果怎么都无法做到所有石头都有颜色、且红色和蓝色一样多，返回-1

import java.util.Arrays;public class Code01_MagicStone {public static int minCost(int[][] stones) {int n = stones.length;if ((n & 1) != 0) {return -1;}Arrays.sort(stones, (a, b) -> a[0] == 0 && b[0] == 0 ? (b[1] - b[2] - a[1] + a[2]) : (a[0] - b[0]));int zero = 0;int red = 0;int blue = 0;int cost = 0;for (int i = 0; i < n; i++) {if (stones[i][0] == 0) {zero++;cost += stones[i][1];} else if (stones[i][0] == 1) {red++;} else {blue++;}}if (red > (n >> 1) || blue > (n >> 1)) {return -1;}blue = zero - ((n >> 1) - red);for (int i = 0; i < blue; i++) {cost += stones[i][2] - stones[i][1];}return cost;}public static void main(String[] args) {int[][] stones = { { 1, 5, 3 }, { 2, 7, 9 }, { 0, 6, 4 }, { 0, 7, 9 }, { 0, 2, 1 }, { 0, 5, 9 } };System.out.println(minCost(stones));}
}

2. 网易

给定一个正数数组arr，表示每个小朋友的得分
任何两个相邻的小朋友，如果得分一样，怎么分糖果无所谓，但如果得分不一样，分数大的一定要比分数少的多拿一些糖果
假设所有的小朋友坐成一个环形，返回在不破坏上一条规则的情况下，需要的最少糖果数

public class Code02_CircleCandy {public static int minCandy(int[] arr) {if (arr == null || arr.length == 0) {return 0;}if (arr.length == 1) {return 1;}int n = arr.length;int minIndex = 0;for (int i = 0; i < n; i++) {if (arr[i] <= arr[lastIndex(i, n)] && arr[i] <= arr[nextIndex(i, n)]) {minIndex = i;break;}}int[] nums = new int[n + 1];for (int i = 0; i <= n; i++, minIndex = nextIndex(minIndex, n)) {nums[i] = arr[minIndex];}int[] left = new int[n + 1];left[0] = 1;for (int i = 1; i <= n; i++) {left[i] = nums[i] > nums[i - 1] ? (left[i - 1] + 1) : 1;}int[] right = new int[n + 1];right[n] = 1;for (int i = n - 1; i >= 0; i--) {right[i] = nums[i] > nums[i + 1] ? (right[i + 1] + 1) : 1;}int ans = 0;for (int i = 0; i < n; i++) {ans += Math.max(left[i], right[i]);}return ans;}public static int nextIndex(int i, int n) {return i == n - 1 ? 0 : (i + 1);}public static int lastIndex(int i, int n) {return i == 0 ? (n - 1) : (i - 1);}public static void main(String[] args) {int[] arr = { 3, 4, 2, 3, 2 };System.out.println(minCandy(arr));}}

3. 腾讯

给定一个正数数组arr，代表每个人的体重。给定一个正数limit代表船的载重，所有船都是同样的载重量
每个人的体重都一定不大于船的载重
要求：
1, 可以1个人单独一搜船
2, 一艘船如果坐2人，两个人的体重相加需要是偶数，且总体重不能超过船的载重
3, 一艘船最多坐2人
返回如果想所有人同时坐船，船的最小数量

import java.util.Arrays;public class Code03_MinBoatEvenNumbers {public static int minBoat(int[] arr, int limit) {Arrays.sort(arr);int odd = 0;int even = 0;for (int num : arr) {if ((num & 1) == 0) {even++;} else {odd++;}}int[] odds = new int[odd];int[] evens = new int[even];for (int i = arr.length - 1; i >= 0; i--) {if ((arr[i] & 1) == 0) {evens[--even] = arr[i];} else {odds[--odd] = arr[i];}}return min(odds, limit) + min(evens, limit);}public static int min(int[] arr, int limit) {if (arr == null || arr.length == 0) {return 0;}int N = arr.length;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;int 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 = Math.max(-1, L - solved);}}int all = lessR + 1;int used = all - noUsed;int moreUnsolved = (N - all) - used;return used + ((noUsed + 1) >> 1) + moreUnsolved;}}

4. 阿里巴巴

给定一个长度len，表示一共有几位
所有字符都是小写(a~z)，可以生成长度为1，长度为2，
长度为3…长度为len的所有字符串
如果把所有字符串根据字典序排序，每个字符串都有所在的位置。
给定一个字符串str，给定len，请返回str是总序列中的第几个
比如len = 4，字典序的前几个字符串为:
a aa aaa aaaa aaab … aaaz … azzz b ba baa baaa … bzzz c …
a是这个序列中的第1个，bzzz是这个序列中的第36558个

import java.util.ArrayList;
import java.util.List;public class Code04_StringKth {// 思路：// cdb，总共长度为7，请问cdb是第几个？// 第一位c :// 以a开头，剩下长度为(0~6)的所有可能性有几个// +// 以b开头，剩下长度为(0~6)的所有可能性有几个// +// 以c开头，剩下长度为(0)的所有可能性有几个// 第二位d :// +// 以ca开头的情况下，剩下长度为(0~5)的所有可能性有几个// +// 以cb开头的情况下，剩下长度为(0~5)的所有可能性有几个// +// 以cc开头的情况下，剩下长度为(0~5)的所有可能性有几个// +// 以cd开头的情况下，剩下长度为(0)的所有可能性有几个// 第三位b// +// 以cda开头的情况下，剩下长度为(0~4)的所有可能性有几个// +// 以cdb开头的情况下，剩下长度为(0)的所有可能性有几个public static int kth(String s, int len) {if (s == null || s.length() == 0 || s.length() > len) {return -1;}char[] num = s.toCharArray();int ans = 0;for (int i = 0, rest = len - 1; i < num.length; i++, rest--) {ans += (num[i] - 'a') * f(rest) + 1;}return ans;}// 不管以什么开头，剩下长度为(0~len)的所有可能性有几个public static int f(int len) {int ans = 1;for (int i = 1, base = 26; i <= len; i++, base *= 26) {ans += base;}return ans;}// 为了测试public static List<String> all(int len) {List<String> ans = new ArrayList<>();for (int i = 1; i <= len; i++) {char[] path = new char[i];process(path, 0, ans);}return ans;}// 为了测试public static void process(char[] path, int index, List<String> ans) {if (index == path.length) {ans.add(String.valueOf(path));} else {for (char c = 'a'; c <= 'z'; c++) {path[index] = c;process(path, index + 1, ans);}}}public static void main(String[] args) {int len = 4;// 暴力方法得到所有字符串List<String> ans = all(len);// 根据字典序排序，所有字符串都在其中ans.sort((a, b) -> apareTo(b));String test = "bzzz";// 根据我们的方法算出test是第几个？// 注意我们算出的第几个，是从1开始的// 而下标是从0开始的，所以变成index，还需要-1int index = kth(test, len) - 1;// 验证System.out.println(ans.get(index));}}

5. 题目5(为了题目6的启发题目)

给定一个数组arr，和整数sum
返回累加和等于sum的子数组有多少个？

import java.util.HashMap;public class Code05_SubarraySumEqualsK {public static int subarraySum(int[] nums, int k) {if (nums == null || nums.length == 0) {return 0;}HashMap<Integer, Integer> preSumTimesMap = new HashMap<>();// 这一句非常重要，表示没有遍历之前你已经可以得到前缀和为0的情况了// 那就是，一个数也没有的时候！preSumTimesMap.put(0, 1);int all = 0;int ans = 0;for (int i = 0; i < nums.length; i++) {all += nums[i];if (preSumTimesMap.containsKey(all - k)) {ans += preSumTimesMap.get(all - k);}if (!preSumTimesMap.containsKey(all)) {preSumTimesMap.put(all, 1);} else {preSumTimesMap.put(all, preSumTimesMap.get(all) + 1);}}return ans;}}

6. 京东

把一个01字符串切成多个部分，要求每一部分的0和1比例一样，同时要求尽可能多的划分
比如 : 01010101
01 01 01 01 这是一种切法，0和1比例为 1 : 1
0101 0101 也是一种切法，0和1比例为 1 : 1
两种切法都符合要求，但是那么尽可能多的划分为第一种切法，部分数为4
比如 : 00001111
只有一种切法就是00001111整体作为一块，那么尽可能多的划分，部分数为1
给定一个01字符串str，假设长度为N，要求返回一个长度为N的数组ans
其中ans[i] = str[0…i]这个前缀串，要求每一部分的0和1比例一样，同时要求尽可能多的划分下，部分数是多少
输入: str = “010100001”
输出: ans = [1, 1, 1, 2, 1, 2, 1, 1, 3]

public class Code06_Ratio01Split {// 001010010100...public static int[] split(int[] arr) {// key : 分子// value : 属于key的分母表, 每一个分母，及其 分子/分母 这个比例，多少个前缀拥有HashMap<Integer, HashMap<Integer, Integer>> pre = new HashMap<>();int n = arr.length;int[] ans = new int[n];int zero = 0; // 0出现的次数int one = 0; // 1出现的次数for (int i = 0; i < n; i++) {if (arr[i] == 0) {zero++;} else {one++;}if (zero == 0 || one == 0) {ans[i] = i + 1;} else { // 0和1，都有数量 -> 最简分数int gcd = gcd(zero, one);int a = zero / gcd;int b = one / gcd;// a / b 比例，之前有多少前缀拥有？ 3+1 4 5+1 6if (!pre.containsKey(a)) {pre.put(a, new HashMap<>());}if (!pre.get(a).containsKey(b)) {pre.get(a).put(b, 1);} else {pre.get(a).put(b, pre.get(a).get(b) + 1);}ans[i] = pre.get(a).get(b);}}return ans;}public static int gcd(int m, int n) {return n == 0 ? m : gcd(n, m % n);}public static void main(String[] args) {int[] arr = { 0, 1, 0, 1, 0, 1, 1, 0 };int[] ans = split(arr);for (int i = 0; i < ans.length; i++) {System.out.print(ans[i] + " ");}}} 

7. 加油加油