一个sql题转换心情
交换工资
题目：给定一个 salary 表，如下所示，有 m = 男性 和 f = 女性 的值。交换所有的 f 和 m 值（例如，将所有 f 值更改为 m，反之亦然）。要求只使用一个更新（Update）语句，并且没有中间的临时表。注意，您必只能写一个 Update 语句，请不要编写任何 Select 语句。
题目
如图所示，这是一个sql题，但是知识点很少见，反正我以前完全不知道，所以在这里也列了出来。
（ps：评论有人吐槽这个题应该是交换性别，23333333）
然后这个知识点就是 sql中的if，或者说case-when也可以、
函数用法其实很容易懂：其实是我更觉得mysql中的if像是三目（也叫三元）。
IF表达式
IF(expr1,expr2,expr3)
如果expr1是true，则返回expr2.否则返回expr3。
这个题也可以这么用，update salary set sex = if(sex='m','f','m')。
其实知道会了if函数这个题简单的不得了。
同样用case也可以。
CASE语法
case-when-then-else-end是一个完整的语法。
case后面的选择的结果。
when 是情况1 ，如果符合选择 then后面的结果。
如果不符合继续往下判断，可以继续when +情况2. 符合选择then后的结果。
不符合继续往下判断。 如果所有的when都不符合，最后走else。
类似于java中的if（）...else if（）...else..一样，这个when有几个可以自由定义。
而咱们这个题不是男的就是女的，所以只要 case sex when 'f' then 'm' else 'f' end.就可以了。完整语句：
update salary set sex = case sex when 'f' then 'm' else 'f' end;
这个我反正之前工作中没用过这个函数，不过遇到了也算是学会了，继续往下做吧。
三个数的最大乘积
题目：给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1:
输入: [1,2,3]
输出: 6
示例 2:
输入: [1,2,3,4]
输出: 24
注意:
给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
思路：理论上讲，只要是最大的三个数就ok了吧？如果说有负数的情况下，应该要考虑负负得正的情况，所以需要获取这个数组最大的三个值和最小的两个值（最多只有两个负数相乘，三个还是负的）。我去理理思路试图写代码。
咳咳，最偷懒的办法写出来了：
class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
return nums[0]*nums[1]*nums[nums.length-1]>=nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3]? nums[0]*nums[1]*nums[nums.length-1]:nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3];
}
}
咱们不说性能，就说思路！妥妥的，要么负负正，要么正正正。就是我这个排序，肯定是要自己实现的，至于自己怎么实现。。。我去实现了。。
很好，自己写个判断一下子超过百分之八十多的人了，就是代码有点不优雅，写的我自己都想笑，用数组是怕自己忘，一开始用的五个变量，max1，max2，max3，min1，min2这种，写着写着自己懵逼了。。：
class Solution {
public int maximumProduct(int[] nums) {
//0 1 2 存最大，第二大， 第三大值 3 4 存最小，第二小值
int[] mm = new int[5];
mm[0] = -1001;
mm[1] = -1001;
mm[2] = -1001;
for(int i : nums){
if(i>=mm[0]){
mm[2] = mm[1];
mm[1] = mm[0];
mm[0] = i;
}else if(i>=mm[1]){
mm[2] = mm[1];
mm[1] = i;
}else if(i>mm[2]){
mm[2] = i;
}
if(i<=mm[3]){
mm[4] = mm[3];
mm[3] = i;
}else if(i<mm[4]){
mm[4] = i;
}
}
return mm[1]*mm[2]>mm[3]*mm[4]?mm[1]*mm[2]*mm[0]:mm[3]*mm[4]*mm[0];
}
}
看了排行第一的代码，人家用的变量，我用的数组。但是真的变量写着我晕，所以这个不按照人家的代码写一遍了，反正意思知道了就行了，下一题吧。
平方数之和
题目：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3
输出: False
思路：这个题我感觉属于那种能做出来，但是能不能优雅的做出来才是考点，我个人想法是从他最大的平方数开始一个个算。
思路没问题，一个简单的双指针：
class Solution {
public boolean judgeSquareSum(int c) {
int x = (int)Math.sqrt(c);
int l = 0;
int r = x;
while(l<=r){
if(l*l+r*r==c){
return true;
}
if(l*l+r*r>c){
r--;
}else{
l++;
}
}
return false;
}
}
一开始我判断条件是l<r.后来测试案例是2，我才发现这个两个数都是1，所以L=R也是可以存在的，剩下的就没什么难度了。
这个代码超过百分之九十七的人，所以我就不再额外看题解了。起始做了这么久算法，递归，迭代，二分，双指针，动态规划这些算法真的养成了思维习惯。再一次感觉到了自己的进步，美滋滋~~继续刷题。
二叉树的层平均值
题目：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
题目截图
思路：讲真，看完题我觉得最骚的一点是这个题居然除出来小数了？？？那请问无法整除怎么办？本来int运算得出个整数整个题都脉络清晰，现在这样你告诉我你是考二叉树基本使用还是考不同数值类型运算呢？哎，吐完槽好好做题吧，说思路,迭代或者递归，获取每一层的数据，计算存list。我去实现了。
这个题怎么说呢，其实一波三折，中间经历了去做别的题，领导派给新任务，开会，下班被雨淋，朋友叫打游戏（还有两颗星星上王者）等等，最主要的是这种题没做过，我还有点静不下心想思路。恰好感谢写了简书，题目思路都已经写上了，我还能再一个字一个字删除了咋地？咬牙学习吧！看题解，只看思路不看代码那种，然后一次次在测试里改错，才算终于做出来了。其实我一直都在说写的文章也算是我自己的笔记记录那种，不是单纯的思路，知识点，方法，算法。我也写不出那种科普文章来，本来我自己都是小白呢。我只是记录自己的心里历程，思路，想法等等。
继续说思路吧，这道题其实复杂的只不过每一层的总和和个数的计算。所以只要会层次遍历就行了（层次遍历这个词看是看题解才知道的）。
所谓的层次遍历不就是一层一层的遍历么。这种队列（栈）肯定首选。主要是因为我看的题解是用的这种办法。说这么多直接上代码吧，其实只要了解队列的层次特性还是很简单的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<Double>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int count = queue.size();
double sum = 0.0;
for(int i = 0 ; i<count ; i++){
//只取出来，不移除
TreeNode n = queue.poll();
sum += n.val;
if(n.left!=null){
queue.add(n.left);
}
if(n.right!=null){
queue.add(n.right);
}
}
res.add(sum/count);
}
return res;
}
}
缺失的第一个正数
题目：给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
思路：首先！这是一道困难难度的题目！其次，我自己半小时多做出来的！！我要骄傲的说三遍！困难，自己，不到一小时！背景是群里聊天有人说到这个题，我手贱就点进去看了下，发现莫名其妙的眼熟，我绝对是做过类似的，而且看上去也不是那么难，所以开始研究。然后做出来了！再多次测试一次次改正下性能超过百分之九十七的人，美滋滋~~
提交记录！
其实这道题还真就不难，而且我做过类似的一道题，进阶要求就是不要用额外空间，还好我当时按照最高要求做的，反正这样的题的一个技巧：用数组下标来代替数字。
如果用map可以map的key存元素值，value没有实际意义。然后从1开始遍历map，map.get(1)如果是null则说明缺1，如果不是null则继续map.get(2)..就这样一直到缺的那个返回。其实这里的value也没有实际意义，只是判断这个key存在不存在而已。
而数组代替虽然略显操作多点，逻辑绕点，但是大大的节省了空间。
说了这么多直接上代码：
class Solution {
public int firstMissingPositive(int[] nums) {
//因为只判断正数，所以可以把所有非正数都直接换成int最大值，省的以后处理。
for(int i = 0;i<nums.length;i++){
if(nums[i]<=0) nums[i] =Integer.MAX_VALUE;
}
//所有出现的正整数如果数值在数组长度内，则该正整数改为负数、
for(int j = 0;j<nums.length;j++){
//注意因为可能判断的是被改为负数的，所以这里要用Math.abs()也就是绝对值来判断
if(Math.abs(nums[j])<=nums.length){
//这里因为下标从0开始，实际数字从1开始，所以每一个数字往前挪一下，也就是-1
//因为测试案例中有重复元素，负负得正，所以不能直接加负号，要负绝对值，保证一定是负的
nums[Math.abs(nums[j])-1] = -Math.abs(nums[Math.abs(nums[j])-1]);
}
}
//判断第一个正数的下标。加1也就是第一个没出现的正数
for(int k = 0;k<nums.length;k++){
if(nums[k]>0){
return k+1;
}
}
//有两种情况会走到这个return。一个是数组顺序正数出现，没出现的就是数组长度+1
//还有一种就是数组没元素，直接返回0+1也就是1
return nums.length+1;
}
}
这道题就到这里，我还是继续把上面那道题做完吧（刚做到一半跑来做这个的）
子数组最大平均数1
题目：给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例 1:
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
注意:
1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。
思路:这道题我觉得主要是判断连续K个数的最大值。剩下的就迎刃而解了。emmm,我用了贼暴力的方法写完了，就是遍历，不说性能起码代码很简单。
直接贴代码:
class Solution {
public double findMaxAverage(int[] nums, int k) {
double max = 0;
double sum = 0;
for(int i=0;i<k;i++){
sum += nums[i];
}
max = sum;
for(int j = k;j<nums.length; j++){
sum = sum-nums[j-k]+nums[j];
max = Math.max(max,sum);
}
return max/k;
}
}
如上文，就是累加，查看连续k的最大值，然后最后除k就ok了。
看了性能第一的代码，我也是奇了怪了，差不多一样一样的代码，人家2ms，我7ms，why？
好了，找到原因了，把Math.max()换成一个if判断就行了。一下子性能就飞上去了。真的是飞：从超过百分之二十多到超过百分之九十九。这道题不难，就是到这里了，下一个。
错误的集合
题目：集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
给定数组的长度范围是 [2, 10000]。
给定的数组是无序的。
思路：这道题和上上一道题是可以差不多思路的。注意：可以差不多，不是一定要那么多。主要是这个题目也没要求说不能使用额外空间啥的。
第一版本的代码（不使用额外空间，原数组操作）：
class Solution {
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
for(int i=0;i<nums.length;i++){
nums[Math.abs(nums[i])-1] = -nums[Math.abs(nums[i])-1];
//说明负负得正，这个是重复元素
if(nums[Math.abs(nums[i])-1]>0){
res[0] = Math.abs(nums[i]);
nums[Math.abs(nums[i])-1] = -nums[Math.abs(nums[i])-1];
}
}
for(int j=0;j<nums.length;j++){
if(nums[j]>0){
res[1] = j+1;
return res;
}
}
return null;
}
}
第二个思路就是map，第一遍遍历数组存map，如果key存在说明是重复元素。
第二遍遍历map，缺失的key就是缺的那个元素。
但是想想这个性能就可怕，不断map.containsKey()和get(key)..啧啧，太可怕，算了吧。确定能实现就行。
第三个思路，新数组，不用改变原有的：
class Solution {
public int[] findErrorNums(int[] nums) {
int[] temp = new int[nums.length];
int[] res = new int[2];
for(int i=0;i<nums.length;i++){
temp[nums[i]-1] = temp[nums[i]-1]==0?-nums[i]:-temp[nums[i]-1];
}
for(int j=0;j<temp.length;j++){
if(temp[j]==0){
res[1] = j+1;
}
if(temp[j]>0){
res[0] = j+1;
}
}
return res;
}
}
其实这种思路和第一种比，只不过少了每个元素要取绝对值一个操作，但是性能质的飞跃。超过百分百的人了。
本来这个题简单，所以不想多说的。但是手贱看了眼题解，发现新解法了：
一个特别有意思的思路:用异或操作。用1一直异或到n，在与数组异或。因为相同的数字异或是0.所以最终得出的结果就是 多的元素^差的元素的值。
当然到了这里还是要继续处理的，再用这个值异或。。
其实这个思路真正的难点我感觉就在这里，异或指 两个数二进制对应数字相同为0，不同为1.然后开始拆分判断什么的，反正我这个数学渣看的头晕眼花的，直接把大神的解释贴上，我反正看的迷迷糊糊的，这个方法耳目一新，但是等我数学基础学好了再开始用吧，真的看的晕。而且今天太晚了。
异或解题原理
今天的笔记就记到这里，然后终于把周末玩了两天欠下的题目补回来了，开心~如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
网友评论