听说刷 LeetCode 的都是大神，那我也来试试！
先从最简单的开始！
这周终于过完啦O(∩_∩)O哈哈开心！这周充实了一些！另外说一下，下周视工作情况而定由每天三道改为至少一道 LeetCode，工作很重要的嘛！
算法题
1. 输入有序数组
题目
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
- 返回的下标值（index1 和 index2）不是从零开始的。
- 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
题解
我的解
我想的过于简单了，没有用上有序的条件，两个循环就完事了，虽然也能实现，但不是最优。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int result[] = new int[2];
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = i + 1; j < numbers.length ; j++) {
if (numbers[i] + numbers [j] == target) {
result[0] = i + 1;
result[1] = j + 1;
}
}
}
return result;
}
}
官方解一：二分法
在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; ++i) {
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return new int[]{-1, -1};
}
}
复杂度分析
-
时间复杂度：O(nlogn)，其中 nn 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)，寻找第二个数使用二分查找，时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。
-
空间复杂度：O(1)。
官方解二：双指针
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int low = 0, high = numbers.length - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[]{low + 1, high + 1};
} else if (sum < target) {
++low;
} else {
--high;
}
}
return new int[]{-1, -1};
}
}
复杂度分析
-
时间复杂度：O(n)，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
-
空间复杂度：O(1)。
总结
不要只想着解决问题，要想着用最优的方式解决问题。格局要大，眼光要长远。
2. 一比特与二比特字符
题目
有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。
现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。
示例 1:
输入:
bits = [1, 0, 0]
输出: True
解释:
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:
输入:
bits = [1, 1, 1, 0]
输出: False
解释:
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
- 1 <= len(bits) <= 1000.
- bits[i] 总是0 或 1.
题解
我的解
我不想用遍历了，想用简便一点的方法，这个数的是结尾只能是0，然后再往前算，想法很好但是没写出来。
没事，不要灰心，看看答案怎么写的。
官方解一：线性扫描
我们可以对 bits 数组从左到右扫描来判断最后一位是否为一比特字符。当扫描到第 i 位时，如果 bits[i]=1，那么说明这是一个两比特字符，将 i 的值增加 2。如果 bits[i]=0，那么说明这是一个一比特字符，将 i 的值增加 1。
如果 i 最终落在了 bits.length−1 的位置，那么说明最后一位一定是一比特字符。
class Solution {
public boolean isOneBitCharacter(int[] bits) {
int i = 0;
while (i < bits.length - 1) {
i += bits[i] + 1;
}
return i == bits.length - 1;
}
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是 bits 数组的长度。
- 空间复杂度：O(1)。
官方解二：贪心
三种字符分别为 0，10 和 11，那么 bits 数组中出现的所有 0 都表示一个字符的结束位置（无论其为一比特还是两比特）。因此最后一位是否为一比特字符，只和他左侧出现的连续的 1 的个数（即它与倒数第二个 0 出现的位置之间的 1 的个数，如果 bits 数组中只有 1 个 0，那么就是整个数组的长度减一）有关。如果 1 的个数为偶数个，那么最后一位是一比特字符，如果 1 的个数为奇数个，那么最后一位不是一比特字符。
class Solution {
public boolean isOneBitCharacter(int[] bits) {
int i = bits.length - 2;
while (i >= 0 && bits[i] > 0) i--;
return (bits.length - i) % 2 == 0;
}
}
复杂度分析
- 时间复杂度：O(n)，其中 N 是 bits 数组的长度。
- 空间复杂度：O(1)。
总结
我太菜了！没看懂官方解。。。
想了一会，发现我是真他丫的菜呀，题目都没看对，能想出来才怪。
明确两个点：
- 题目的要求，只是判断最后是一比特字符还是两比特字符
- 这个数只能以 1 开头（这是个正常的数）， 0 结尾（题目说的）
关于官方解法一：
- 从左边第一位 1 开始，如果是 1，必定二比特，所以往后数 + 2，如果是 0，必定一比特，所以往后数 ＋ 1，以此类推，最后如果推到倒数第二个数 即 length - 1，那么最后剩的一个数肯定是一比特，否则为二比特，解法中写的极为巧妙！
关于官方解法二：
- 最后一位一定是 0，那么只需要确定倒数第二个 0 和 最后这个 0 之间 1 的个数即可，如果偶数正好能自给自足，以 11 方式分配完，即最后的 0 是一比特，如果是奇数 1，会剩下一个 1 和最后的 0 组成二比特。
- 另外，如果倒数第二个 0 和 最后这个 0 之间没有 1，最后的 0 必定是一比特。
- 解法中的
int i = bits.length - 2;把 i 确定到 倒数第二个数，并且 最后返回值中的差值是中间 1 的个数，很巧妙。
3. 二进制求和
题目
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
- 每个字符串仅由字符 '0' 或 '1' 组成。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" ，就都不含前导零。
题解
我的解
我想的是 for 循环，用 if 判断是 00 01 11 的那种情况进行判断，但是没有考虑到 字符串最后进位会改变长度，最后也没写出来，还是菜呀。
官方解一：运用自带方法
class Solution {
public String addBinary(String a, String b) {
return Integer.toBinaryString(
Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
);
}
}
官方解二：模拟
思路和算法
我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。
具体的，我们可以取 n=max{∣a∣,∣b∣}，循环 n 次，从最低位开始遍历。我们使用一个变量 carry 表示上一个位置的进位，初始值为 0。记当前位置对其的两个位为 ai 和 bi，则每一位的答案为 (carry+ai+bi)mod2，下一位的进位为 |(carry+ai+bi)/2|。重复上述步骤，直到数字 a 和 b 的每一位计算完毕。最后如果 carry 的最高位不为 0，则将最高位添加到计算结果的末尾。
注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。当然你也可以直接把 a 和 b 中短的那一个补 0 直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。
代码
class Solution {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer();
int n = Math.max(a.length(), b.length()), carry = 0;
for (int i = 0; i < n; ++i) {
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
ans.append((char) (carry % 2 + '0'));
carry /= 2;
}
if (carry > 0) {
ans.append('1');
}
ans.reverse();
return ans.toString();
}
}
复杂度分析
假设 n=max{∣a∣,∣b∣}。
- 时间复杂度：O(n)，这里的时间复杂度来源于顺序遍历 a 和 b。
- 空间复杂度：O(1)，除去答案所占用的空间，这里使用了常数个临时变量。
总结
感觉这次就在完成的边缘，怎么也完成不了，很难受。
关于官方解法一
- 思想要灵活~~
关于官方解法二
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;- 上边这两句话的意思是，两个二进制字符串长度不同，当长度小的字符串到头的时候就用 0 代替。并且两个
+=说明 carry 值是两个字符串同一位相加的结果。 - 总之就很巧妙，就很厉害，我是真的写不出来。
4. 各位相加
题目
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
题解
我的解
终于自己做出来一个了！！！（虽然很简单）
class Solution {
public int addDigits(int num) {
if (num >= 10){
num = addDigits(num / 10 + num % 10);
}
return num;
}
}
官方解一：递归 or 循环
Ps：怎么回事，感觉官方高赞的递归还不如我写的好啊，我是不是膨胀了
递归
public int addDigits(int num) {
if (num < 10) {
return num;
}
int next = 0;
while (num != 0) {
next = next + num % 10;
num /= 10;
}
return addDigits(next);
}
循环
public int addDigits(int num) {
while (num >= 10) {
int next = 0;
while (num != 0) {
next = next + num % 10;
num /= 10;
}
num = next;
}
return num;
}
官方解二：数学（不懂）
恕我直言，我看不懂！
思路
-
除个位外，每一位上的值都是通过(9+1)进位的过程得到的，想一下拨算盘进位
-
把整数n看成n样物品，原本是以10个1份打包的，现在从这些10个1份打包好的里面，拿出1个，让它们以9个为1份打包。
-
这样就出现了两部分的东西：
- 原本10个现在9个1份的，打包好的物品，这些，我们不用管
- 零散的物品，它们还可以分成：
- 从原来打包的里面拿出来的物品，它们的总和 =》 原来打包好的份数 =》 10进制进位的次数 =》 10进制下，除个位外其他位上的值的总和
- 以10个为1份打包时，打不进去的零散物品 =》 10进制个位上的值
-
如上零散物品的总数，就是第一次处理num后得到的累加值
-
如果这个累加值>9，那么如题就还需要将各个位上的值再相加，直到结果为个位数为止。也就意味着还需要来一遍如上的过程。
-
那么按照如上的思路，似乎可以通过n % 9得到最后的值
-
但是有1个关键的问题，如果num是9的倍数，那么就不适用上述逻辑。原本我是想得到n被打包成10个1份的份数+打不进10个1份的散落个数的和。通过与9取模，去获得那个不能整除的1，作为计算份数的方式，但是如果可以被9整除，我就无法得到那个1，也得不到个位上的数。
-
所以需要做一下特殊处理，(num - 1) % 9 + 1
-
可以这么做的原因：原本可以被完美分成9个为一份的n样物品，我故意去掉一个，那么就又可以回到上述逻辑中去得到我要的n被打包成10个一份的份数+打不进10个一份的散落个数的和。而这个减去的1就相当于从，在10个1份打包的时候散落的个数中借走的，本来就不影响原来10个1份打包的份数，先拿走再放回来，都只影响散落的个数，所以没有关系。
class Solution {
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
}
总结
挺开心的，终于自己写出一个比较像样的解答了。
但是这个进阶解法实在是看不懂呀。以后有时间再回来看吧~
5. 字符串相加
题目
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意：
- num1 和num2 的长度都小于 5100.
- num1 和num2 都只包含数字 0-9.
- num1 和num2 都不包含任何前导零。
- 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
题解
我的解
虽然不让用类型转换的方法，但是我想不到别的方法啊，所以我还是用了转换的方法，事实证明，数小的时候可以用，数大的时候转换不了（因为我用的 Integer，没用 BigInteger）。
class Solution {
public String addStrings(String num1, String num2) {
int i = Integer.parseInt(num1) + Integer.parseInt(num2);
return String.valueOf(i);
}
}
官方解：双指针
算法流程： 设定 i，j 两指针分别指向 num1，num2 尾部，模拟人工加法；
- 计算进位： 计算 carry = tmp // 10，代表当前位相加是否产生进位；
- 添加当前位： 计算 tmp = n1 + n2 + carry，并将当前位 tmp % 10 添加至 res 头部；
- 索引溢出处理： 当指针 i或j 走过数字首部后，给 n1，n2 赋值为 0，相当于给 num1，num2 中长度较短的数字前面填 0，以便后续计算。
- 当遍历完 num1，num2 后跳出循环，并根据 carry 值决定是否在头部添加进位 11，最终返回 res 即可。
代码：
class Solution {
public String addStrings(String num1, String num2) {
// 创建一个可变数组 用于存放结果
StringBuilder res = new StringBuilder();
// 确定加法的位置是从后往前 进位为 carry
int i = num1.length() - 1,j = num2.length() - 1,carry = 0;
while (i >= 0 || j >= 0){
// 两个字符串长度可能不等 当其中一个字符串长度不够时用 0 代替
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
// 模拟加法操作 进位也要算在里面
int num = n1 + n2 + carry;
// 把加法结果 取出个位添加到 可变数组中
res.append(num % 10);
// 算出进位 （只能是 0 或者 1）
carry = num / 10;
// 两个字符串同时前移一位 继续运算
i--;j--;
}
// 如果首位加法运算后 有进位 则额外累加上 1
if (carry == 1){
res.append("1");
}
// 翻转可变数组 得到真实结果
return res.reverse().toString();
}
}
复杂度分析：
- 时间复杂度 O(max(M,N))：其中 M，N 为 2 数字长度，按位遍历一遍数字（以较长的数字为准）；
- 空间复杂度 O(1)：指针与变量使用常数大小空间。
总结
- 看了答案之后，发现双指针真的是有点东西啊，在做加法的时候有奇效（上边的二进制加法也用了这种思想），可惜我完全没想到......
- 下次遇到加法时，可以优先考虑双指针了！
- 以后题解要写注释！
6. 数组形式的整数加法
题目
示例 1：
输入：A = [1,2,0,0], K = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234
示例 2：
输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455
示例 3：
输入：A = [2,1,5], K = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021
示例 4：
输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
输出：[1,0,0,0,0,0,0,0,0,0,0]
解释：9999999999 + 1 = 10000000000
提示：
- 1 <= A.length <= 10000
- 0 <= A[i] <= 9
- 0 <= K <= 10000
- 如果 A.length > 1，那么 A[0] != 0
题解
我的解
吼吼，通过上题的总结写出来了哦~~~开心！
说明总结还是特别有效的！
我的思路是加法优先考虑双指针，然后发现双指针确实能解决~
- 我把整型 转成 字符串再进逐位加法，不知道是不是绕路了
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
List<Integer> result = new ArrayList<>();
String num2 = String.valueOf(K);
int i = A.length - 1,j = num2.length() - 1,carry = 0;
while (i >= 0 || j >= 0){
int n1 = i >= 0 ? A[i] : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int num = n1 + n2 + carry;
result.add(num % 10);
carry = num / 10;
i--;j--;
}
if (carry == 1){
result.add(1);
}
Collections.reverse(result);
return result;
}
}
官方解
思路
让我们逐位将数字加在一起。举一个例子，如果要计算 123 与 912 的和。我们顺次计算 3+2、2+1、1+9。任何时候，当加法的结果大于等于 10，我们要将进位的 1 加入下一位的计算中去，所以最终结果等于 1035。
算法
我们可以对以上的想法做一个小变化，让它实现起来更容易 —— 我们将整个加数加入数组表示的数的最低位。
继续之前的例子 123+912，我们把它表示成 [1, 2, 3+912] 。然后，我们计算 3+912 = 915。5 留在当前这一位，将 910/10=91 以进位的形式加入下一位。
然后，我们再重复这个过程，计算 [1,2+91,5]。我们得到 9393，33 留在当前位，将 90/10=9 以进位的形式加入下一位。继而又得到 [1+9,3,5]，重复这个过程之后，最终得到结果 [1,0,3,5]。
代码：
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
LinkedList<Integer> res = new LinkedList<>();
for(int i = A.length-1 ; i >= 0 || K > 0 ; i--){
// 如果数组下标没有到头，直接整个数 + 数组最后一位
if(i >= 0) {
K += A[i];
}
// 取出相加后的 个位
// 如果没有上一步的相加，直接取出 K 的个位（此时数组到头了）
res.addFirst(K % 10);
// 把处理后的 k 去掉最后一位
K = K/10;
}
return res;
}
}
总结
事实证明我确实绕弯路了~~~
- 确实不需要转换，而且官方的思想是我没想到的，数字不用额外的处理，直接加数组的后边就好了，然后每次加之后，只需要把数字去掉最后一位（用÷10实现），接着往前处理就好了！。
另外，关于性能上也可以优化~~~
- ArrayList换成LinkedList
- res.add(K % 10);改为 res.addFirst(K % 10); 这样可以省去 Collections.reverse(res);
7. 一维数组的动态和
题目
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。
示例 1：
输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：
输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：
输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]
提示：
- 1 <= nums.length <= 1000
- -106 <= nums[i] <= 106
题解
我的解
今天有工作任务，我的解就算了，直接上答案！
官方解：单层循环
我不得不说这个解太秀了，不需要双层循环的暴力破解，更不需要令人头大的动态规划。
在这用到了递归的思想！只需要一层循环！
class Solution {
public int[] runningSum(int[] nums) {
for(int i=1 ; i<nums.length; ++i){
nums[i] +=nums[i-1];
}
return nums;
}
}
总结
敲了一天代码确实有点累呀~
8. 好数对的数目
题目
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对
示例 3：
输入：nums = [1,2,3]
输出：0
提示：
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
题解
我的解
这个也不写了，明天看看有空不。
官方解一：暴力统计
思路与算法
对于每个 a_i，枚举所有的 a_j(j>i)，检查是否满足 a_i = a_j，如果是就计入答案。
代码
class Solution {
public int numIdenticalPairs(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (nums[i] == nums[j]) {
++ans;
}
}
}
return ans;
}
}
复杂度分析
- 时间复杂度：O(n^2)。
- 空间复杂度：O(1)。
官方解二：组合计数
思路与算法
用哈希表统计每个数在序列中出现的次数，假设数字 k 在序列中出现的次数为 v，那么满足题目中所说的 nums[i]=nums[j]=k(i<j) 的 (i,j) 的数量就是v(v−1)/2，即 k 这个数值对答案的贡献是 v(v−1)/2。我们只需要把所有数值的贡献相加，即可得到答案。
代码
class Solution {
public int numIdenticalPairs(int[] nums) {
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int num : nums) {
m.put(num, m.getOrDefault(num, 0) + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
int v = entry.getValue();
ans += v * (v - 1) / 2;
}
return ans;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)，即哈希表使用到的辅助空间的空间代价。
总结
今天用脑有点过度，回去要来一罐“六个核桃”！
9. 拥有最多糖果的孩子
题目
给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。
示例 1：
输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true]
解释：
孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
示例 2：
输入：candies = [4,2,1,1,2], extraCandies = 1
输出：[true,false,false,false,false]
解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。
示例 3：
输入：candies = [12,1,12], extraCandies = 10
输出：[true,false,true]
提示：
- 2 <= candies.length <= 100
- 1 <= candies[i] <= 100
- 1 <= extraCandies <= 50
题解
我的解
我的思路是对的，但是能力制约了我。
我真的是太菜了，求最大值都不会写了，难受。。。
官方解：先求最大值再比较
解题思路
首先比较出原有糖果数组的最大值，然后分别拿数组对应元素加额外糖果之后的结果和最大值比较
代码
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
List list = new ArrayList<Boolean>(candies.length);
int max = 0;
for (int i = 0; i < candies.length; i++) {
if (candies[i] > max) {
max = candies[i];
}
}
for (int j = 0; j < candies.length; j++) {
if (candies[j] + extraCandies >= max) {
list.add(true);
} else {
list.add(false);
}
}
return list;
}
}
总结
好多基础的东西忘了呀！
10. 重新排列数组
题目
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。
示例 1：
输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7]
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]
示例 2：
输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]
示例 3：
输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]
提示：
1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3
题解
我的解
我的想法是找规律，会发现偶数的数直接是 i+i 的规律，奇数的数每次递减 1。
虽然很 low，但是做出来了哈哈，就很开心~~~
class Solution {
public int[] shuffle(int[] nums, int n) {
int result[] = new int[nums.length];
result[0] = nums[0];
int cut = nums.length/2 - 1;
for (int i = 1; i < nums.length; i++) {
if (i < nums.length/2){
result[i+i] = nums[i];
}else {
result[i-cut] = nums[i];
cut--;
}
}
return result;
}
}
官方解：双指针
很容易想到的方法就是将给定的数组nums拆分为2个数组，分别存放x和y，这样在从0遍历一次n，依次将拆分的2个数组存放到新数组中，由此可以想到我们可以将拆分2个数组的过程改为通过双指针的方式进行解决：
解决思路为定义2个指针位置，分别指向第i个和第i+n个，这样通过移动双指针的位置只需要遍历一次数组就能够获取到想要的数组数据。
class Solution {
public int[] shuffle(int[] nums, int n) {
int temp[] = new int[nums.length];
int index = 0;
for(int i = 0;i < n;i++){
temp[index++] = nums[i];
temp[index++] = nums[i+n];
}
return temp;
}
}
总结
官方解得方法显然比我的想法舒服的多，双指针还是强啊！
通过两个 index++ 实现了新数组的分别赋值，通过 i 和 i+n 实现了 x 值、y值的确定，属实巧妙啊。
数据库题
1. 大的国家
题目
这里有张 World 表
|name |continent |area |population |gdp |
|-------|-------|-------|-------|-------|
| Afghanistan | Asia | 652230 | 25500100 | 20343000 |
| Albania | Europe | 28748 | 2831741 | 12960000 |
| Algeria | Africa | 2381741 | 37100000 | 188681000 |
| Andorra | Europe | 468 | 78115 | 3712000 |
| Angola | Africa | 1246700 | 20609294 | 100990000 |
如果一个国家的面积超过300万平方公里，或者人口超过2500万，那么这个国家就是大国家。
编写一个SQL查询，输出表中所有大国家的名称、人口和面积。
例如，根据上表，我们应该输出:
| name | population | area |
|---|---|---|
| Afghanistan | 25500100 | 652230 |
| Algeria | 37100000 | 2381741 |
题解
我的解
select name,population,area from World where population > 25000000 or area > 3000000
官方解一：使用 WHERE 和 OR
使用 WHERE 子句过滤所有记录，获得满足条件的国家。
SELECT
name, population, area
FROM
world
WHERE
area > 3000000 OR population > 25000000
;
官方解二：使用 WHERE 和 UNION
SELECT
name, population, area
FROM
world
WHERE
area > 3000000
UNION
SELECT
name, population, area
FROM
world
WHERE
population > 25000000
;
注：方法二 比 方法一 运行速度更快，但是它们没有太大差别。
总结
- 使用 or 会使索引会失效，在数据量较大的时候查找效率较低，通常建议使用 union 代替 or。
- 这个题目属实有点简单。
2. 超过5名学生的课
题目
有一个courses 表 ，有: student (学生) 和 class (课程)。
请列出所有超过或等于5名学生的课。
例如,表:
| student | class |
|---|---|
| A | Math |
| B | English |
| C | Math |
| D | Biology |
| E | Math |
| F | Computer |
| G | Math |
| H | Math |
| I | Math |
应该输出:
| class |
|---|
| Math |
Note:
学生在每个课中不应被重复计算。
题解
我的解
我的解不对，来看看官方怎么处理的吧
select class from courses where count(class) > 5
官方解一：使用 GROUP BY 和子查询
思路
先统计每门课程的学生数量，再从中选择超过 5 名学生的课程。
算法
使用 GROUP BY 和 COUNT 获得每门课程的学生数量。
SELECT
class, COUNT(DISTINCT student)
FROM
courses
GROUP BY class
;
注：使用 DISTINCT 防止在同一门课中学生被重复计算（可能A选Math这种数据有多条）。
| class | COUNT(student) |
|---|---|
| Biology | 1 |
| Computer | 1 |
| English | 1 |
| Math | 6 |
使用上面查询结果的临时表进行子查询，筛选学生数量超过 5 的课程。
SELECT
class
FROM
(SELECT
class, COUNT(DISTINCT student) AS num
FROM
courses
GROUP BY class) AS temp_table
WHERE
num >= 5
;
注：COUNT(student) 不能直接在 WHERE 子句中使用，这里将其重命名为 num。
官方解二：使用 GROUP BY 和 HAVING 条件
算法
在 GROUP BY 子句后使用 HAVING 条件是实现子查询的一种更加简单直接的方法。
SELECT
class
FROM
courses
GROUP BY class
HAVING COUNT(DISTINCT student) >= 5
总结
遇到查询数据中某一类的数量时，分组啊！！！
对于 sql 还是不能自信呀，毕竟不是自己的专长。好吧我还是太菜了。加油ヾ(◍°∇°◍)ﾉﾞ
3. 组合两个表
题目
表1: Person
| 列名 | 类型 |
|---|---|
| PersonId | int |
| FirstName | varchar |
| LastName | varchar |
PersonId 是上表主键
表2: Address
| 列名 | 类型 |
|---|---|
| AddressId | int |
| PersonId | int |
| City | varchar |
| State | varchar |
AddressId 是上表主键
编写一个 SQL 查询，满足条件：无论 person 是否有地址信息，都需要基于上述两表提供 person 的以下信息：
FirstName, LastName, City, State
题解
我的解
我的解不对，不知道 null 怎么实现，看看答案怎么说。
select FirstName, LastName, City, State from Person p,Address a where p.PersonId = a.PersonId
官方解：使用 outer join
算法
因为表 Address 中的 personId 是表 Person 的外关键字，所以我们可以连接这两个表来获取一个人的地址信息。
考虑到可能不是每个人都有地址信息，我们应该使用 outer join（外连接） 而不是默认的 inner join。
select FirstName, LastName, City, State
from Person left join Address
on Person.PersonId = Address.PersonId
;
注意：如果没有某个人的地址信息，使用 where 子句过滤记录将失败（我就是 where 失败了。。。），因为它不会显示姓名信息。
总结
-
这个题的关键就在于 Address 表可能没有 Person 表中相应的 人 的数据，所以不能用 where，用左连接正好，依靠 Person 表的数据 是否能匹配到 Adress 表中的数据，匹配到显示，匹配不到则为 null，符合题目条件。
-
我的 sql 还是太菜了，需要加强
4. 从不订购的客户
题目
某网站包含两个表，Customers 表和 Orders 表。编写一个 SQL 查询，找出所有从不订购任何东西的客户。
Customers 表：
| Id | Name |
|---|---|
| 1 | Joe |
| 2 | Henry |
| 3 | Sam |
| 4 | Max |
Orders 表：
| Id | CustomerId |
|---|---|
| 1 | 3 |
| 2 | 1 |
例如给定上述表格，你的查询应返回：
| Customers |
|---|
| Henry |
| Max |
题解
我的解
我想的是求出来买过产品的顾客，去除掉不就是没买过产品的顾客了嘛
思想很好，可惜语法不会，下面是我的解，但是不对。
select Name Customers from Customers
where not exists
(select Name from Customers c,Orders o where c.id = o.CustomerId )
官方解：not in
如果我们有一份曾经订购过的客户名单，就很容易知道谁从未订购过。
我们可以使用下面的代码来获得这样的列表。
select customerid from orders;
然后，我们可以使用 NOT IN 查询不在此列表中的客户。
select customers.name as 'Customers'
from customers
where customers.id not in
(
select customerid from orders
);
总结
-
逻辑上想的有点复杂了，直接找 Orders 表的 customerid 就可以了，不需要作什么比较
-
还有一个大问题，sql写的太烂了，咳咳，继续加油。
5. 查找重复的电子邮箱
题目
编写一个 SQL 查询，查找 Person 表中所有重复的电子邮箱。
示例：
| Id | |
|---|---|
| 1 | a@b.com |
| 2 | c@d.com |
| 3 | a@b.com |
根据以上输入，你的查询应返回以下结果：
| a@b.com |
说明：所有电子邮箱都是小写字母。
题解
我的解
我的解不对。
select Email from Person group by Id having count(Email)>1
官方解一：使用 GROUP BY 和临时表
重复的电子邮箱存在多次。要计算每封电子邮件的存在次数，我们可以使用以下代码。
select Email, count(Email) as num
from Person
group by Email;
| num | |
|---|---|
| a@b.com | 2 |
| c@d.com | 1 |
以此作为临时表，我们可以得到下面的解决方案。
select Email from
(
select Email, count(Email) as num
from Person
group by Email
) as statistic
where num > 1
;
官方解二：使用 GROUP BY 和 HAVING 条件
向 GROUP BY 添加条件的一种更常用的方法是使用 HAVING 子句，该子句更为简单高效。
所以我们可以将上面的解决方案重写为：
select Email
from Person
group by Email
having count(Email) > 1;
总结
差一点啊！就很难受，分组分错了！难受住。