气球的最大数量
题目：给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。
思路：类似的题目做过很多啊，这个题的思路就是数组下标代替字母。然后判断最小字母的数量（ll和oo两个才能拼成一个。）反正不难，我先去实现了。
一次过，性能超过百分百。我直接贴代码：
class Solution {
public int maxNumberOfBalloons(String text) {
int[] d = new int[26];
for(char c : text.toCharArray()){
d[c-'a']++;
}
// balloon分别是下标1 0 11 14 13
int min = Math.min(d[1],d[0]);
min = Math.min(min,d[11]/2);
min = Math.min(min,d[14]/2);
min = Math.min(min,d[13]);
return min;
}
}
感觉这道题也没什么好讲的，直接下一题了
最小绝对差
题目：给你个整数数组 arr，其中每个元素都 不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
示例 1：
输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]
示例 2：
输入：arr = [1,3,6,10,15]
输出：[[1,3]]
示例 3：
输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]
提示：
2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6
思路：这个题的想法分三步，1.排序（这里打算用 数组下标代替数值的方式）2.找出最小绝对差 3.将符合最小绝对差的对添加到返回list中
怎么说呢，思路不错，就是没考虑实际，这个数的范围正负1000000.所以我这个想法的性能一言难尽，，，，先贴代码吧
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
int[] d = new int[2000001];
for(int i : arr){
d[i+1000000]++;
}
int min = 2000001;
int start = -1;
for(int i = 0;i<2000001;i++){
if(d[i]>0){
if(start!=-1) min = Math.min(min,i-start);
start = i;
}
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
for(int i = 0;i<2000001-min;i++){
if(d[i]>0 && d[i+min]>0){
List<Integer> list = new ArrayList<Integer>();
list.add(i-1000000);
list.add(i+min-1000000);
res.add(list);
}
}
return res;
}
}
我还是换个思路优化优化吧，好了，用了最无脑的方法性能超过百分之八十九的人：
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int min = 10000000;
List<List<Integer>> res = new ArrayList<List<Integer>>();
for(int i = 0;i<arr.length-1;i++){
int n = arr[i];
int n1 = arr[i+1];
if(n1-n<min){
min = n1-n;
res.clear();
List<Integer> list = new ArrayList<Integer>();
list.add(n);
list.add(n1);
res.add(list);
}else if(n1-n==min){
List<Integer> list = new ArrayList<Integer>();
list.add(n);
list.add(n1);
res.add(list);
}
}
return res;
}
}
看了性能排行第一的代码，差不多就是这个思路，我复制粘贴提交，性能更低了，这个题有毒吧？反正思路就这样了，下一题吧。
独一无二的出现次数
题目：给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
示例 1：
输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
示例 2：
输入：arr = [1,2]
输出：false
示例 3：
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true
提示：
1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000
思路：坚持数组下标代替数组不变，这个范围正负一千绝对可以。我去实现了。
直接贴代码，一次过的，超过百分之九十三的人：
class Solution {
public boolean uniqueOccurrences(int[] arr) {
int[] d = new int[2001];
for(int i : arr){
d[i+1000]++;
}
int sum = 0;
Set<Integer> set = new HashSet<Integer>();
for(int i : d){
if(i>0){
set.add(i);
sum++;
}
}
return set.size()==sum;
}
}
这道题比较简单，也不多说了，我直接下一题。感觉这两天要把leetcode上的简单题刷完了，有点小激动呢。
玩筹码
题目：数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
最开始的时候，同一位置上也可能放着两个或者更多的筹码。返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。
示例 1：
输入：chips = [1,2,3]
输出：1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。
示例 2：
输入：chips = [2,2,2,3,3]
输出：2
解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。
提示：
1 <= chips.length <= 100
1 <= chips[i] <= 10^9
思路：这个题的重点是数轴上，一开始怎么看也没看明白，一个字一个字读题才注意到，然后读懂题就好做多了。目前没好想法，只打算用双指针，奇偶数的判断每一个点为终点的步数，选择最少的。。我去实现了
做了才发现这个题比想的简单多了！！！因为双数移动不算次数，所以只判断奇偶的数量哪个少随便找另一个为终点就行了，我直接上代码：
class Solution {
public int minCostToMoveChips(int[] chips) {
//奇数
int j = 0;
//偶数
int o = 0;
for(int i : chips){
if((i&1)==0) {
o++;
}else{
j++;
}
}
return Math.min(j,o);
}
}
这道题其实思路明确了很容易做的，所以就这样吧，下一题下一题。
分割平衡字符串
题目：在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。返回可以通过分割得到的平衡字符串的最大数量。
示例 1：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。
示例 2：
输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。
示例 3：
输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR".
提示：
1 <= s.length <= 1000
s[i] = 'L' 或 'R'
思路：这道题怎么说呢，挺简单的，以前有一个去掉最外层括号的就类似这个思路。。这个题我想的是一个计数器。l就+，r就-。等于0就说明拆出一组。我去实现了。
class Solution {
public int balancedStringSplit(String s) {
int res = 0;
int n = 0;
for(char c : s.toCharArray()){
if(c=='R'){
n++;
if(n==0) res++;
}else{
n--;
if(n==0) res++;
}
}
return res;
}
}
一次过，性能双百，直接下一题。
缀点成线
题目:在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。
思路：这个题怎么说呢，做过类似的，一个判断平面坐标系三个点能不能组成三角形的题。当时判断的点是三点在不在一条直线。其实这个判断的是多点在不在一条直线。思路就是判断夹角。。我去实现了
额，实现是实现了，我也觉得做的没问题，，，但是性能。。。我也不知道为什么这么低啊~~先贴出来吧。
class Solution {
public boolean checkStraightLine(int[][] coordinates) {
int y = coordinates[0][1]-coordinates[1][1];
int x =coordinates[0][0] - coordinates[1][0];
for(int i = 1;i<coordinates.length-1;i++ ){
int tempy = coordinates[i][1]-coordinates[i+1][1];
int tempx = coordinates[i][0]-coordinates[i+1][0];
if(x*tempy!=y*tempx){
return false;
}
}
return true;
}
}
这里的x和y就是两个点连成的线为斜边，然后构成的两条直角边的长。根据三角形定理，直角三角形两条直角边的比例相等则夹角也会相等（这块我知道但是说不清楚，，反正就这个意思。）因为除数不能为0.所以防止报错 ，A/B = C/D 的情况可以换成 AD =BC .就这样，反正如上代码。
但是这个性能有点问题，我去看看怎么优化：
说一个很有意思的问题，一样的代码，我就改了变量名性能变成百分百了。。。不过可以理解，我才发现第一次提交只有1ms，不过性能差了好几十。。哈哈，贴个截图：
找出给定方程的正整数解
题目:给出一个函数 f(x, y) 和一个目标结果 z，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。给定函数是严格单调的，也就是说：
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
函数接口定义如下：
interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};
如果你想自定义测试，你可以输入整数 function_id 和一个目标结果 z 作为输入，其中 function_id 表示一个隐藏函数列表中的一个函数编号，题目只会告诉你列表中的 2 个函数。 你可以将满足条件的 结果数对 按任意顺序返回。
示例 1：
输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 表示 f(x, y) = x + y
示例 2：
输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 表示 f(x, y) = x * y
提示：
1 <= function_id <= 9
1 <= z <= 100
题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。
思路:这个题目说实话我是没读懂的，然后开始写代码居然蒙对了。。。我也很莫名其妙啊。。。哈哈，现在对这个题还是有点了解的。首先这个题具体函数怎么调用别管就行了。反正直接用，然后结果和给定z比较，大了小了的就调整呗。。我直接贴代码吧
/*
* // This is the custom function interface.
* // You should not implement it, or speculate about its implementation
* class CustomFunction {
* // Returns f(x, y) for any given positive integers x and y.
* // Note that f(x, y) is increasing with respect to both x and y.
* // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
* public int f(int x, int y);
* };
*/
class Solution {
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int l = 1;
int r = z;
while(l<=z && r>=1){
int n = customfunction.f(l,r);
if(n==z){
List<Integer> tmp = new ArrayList<>();
tmp.add(l);
tmp.add(r);
res.add(tmp);
l++;
r++;
}else if(n>z){
r--;
}else{
l++;
}
}
return res;
}
}
因为题目要求中f(x, y) < f(x + 1, y)。f(x, y) < f(x, y + 1)。所以可以双指针判断就ok了。这个题其实做起来简单但是题目很迷啊。下一题了。
奇数值单元格的数码
题目：给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。另有一个索引数组 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 「奇数值单元格」 的数目。
示例 1：
输入：n = 2, m = 3, indices = [[0,1],[1,1]]
输出：6
解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。
第一次增量操作后得到 [[1,2,1],[0,1,0]]。
最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。
示例 2：
输入：n = 2, m = 2, indices = [[1,1],[0,0]]
输出：0
解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。
提示：
1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m
题目截图
思路：这个题感觉复杂的是数据格式，都是数组型数组。。。题目还是不难的，就是每次加1而已，，我目前的思路就是一个个加。。最后计算奇数的个数。。先去实现了再看能不能优化。
好了，第一版本的代码完成了，性能不太好，但是随着做我开始怀疑有什么技巧了。先贴出来再说吧：
class Solution {
public int oddCells(int n, int m, int[][] indices) {
int[][] d = new int[n][m];
for(int i = 0;i<indices.length;i++){
for(int j = 0; j<d[0].length;j++){
d[indices[i][0]][j]++;
}
}
for(int i = 0;i<indices.length;i++){
for(int j = 0; j<d.length;j++){
d[j][indices[i][1]]++;
}
}
int res = 0;
for(int[] arr : d){
for(int num : arr){
if((num&1)==1) res++;
}
}
return res;
}
}
看了性能排行第一的代码，确实是有技巧的，其实每次被叠加的那个格子因为加了两次，所以不会是负的。只要判断没被叠加的就行，，我直接贴代码：
class Solution {
public int oddCells(int n, int m, int[][] indices) {
int row[] =new int[n];//行数组
int col[]=new int[m];//列数组
for(int i=0;i<indices.length;i++){
row[indices[i][0]]++;//indices是二维数组，indices[i]指的二维数组中的第几个一维数组，indices[i][0],指的是一维数组中的第一个数字，eq： indices = [[0,1],[1,1]];当i=0,indices[i]=[0,1],，indices[i][0]=0
col[indices[i][1]]++;//indices是二维数组，indices[i]指的二维数组中的第几个一维数组，indices[i][1],指的是一维数组中的第二个数字eq： indices = [[0,1],[1,1]];indices[i]=[1,1],，indices[i][0]=1
}
int count=0;
//双重循环，取每一个值进行奇数判断
for(int i=0;i<row.length;i++){
for(int j=0;j<col.length;j++){
if((row[i]+col[j])%2>0){
count++;
}
}
}
return count;
}
}
行了，这道题其实因为我自己有思路，看了别人的代码也直接能看懂，所以不浪费时间了。
思路:今天的笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！！！
