第一题: 1394. 找出数组中的幸运数

LeetCode: 1394. 找出数组中的幸运数

描述:
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。

给你一个整数数组 arr，请你从中找出并返回一个幸运数。

• 如果数组中存在多个幸运数，只需返回 最大 的那个。
• 如果数组中不含幸运数，则返回 -1 。

解题思路:

1. 首先使用一个长度为501的数组, 进行存储, 存储每一个数字出现次数.
2. 要返回对应数字出现次数相同的, 且最大的.
3. 这样可以直接考虑数组长度, 因为最大出现次数就是数组长度, 所以优先考虑数组长度.
4. 然后越来越小的进行查找是否有满足条件的.

代码实现:

class Solution {
    public int findLucky(int[] arr) {
        int[] count = new int[501];
        for(int val : arr) {
            count[val]++;
        }
        for(int i = arr.length; i>0 ;i--) {
            if(count[i] == i){
                return i;
            }
        }
        return -1;
    }
}

第二题: 1512. 好数对的数目

LeetCode: 1512. 好数对的数目

描述:
给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j，就可以认为这是一组 好数对 。

返回好数对的数目。

解题思路:

1. 首先创建一个长度为101 的数组, 用来对数字出现次数的存储.
2. 对于数字的首次出现, 不进行相加, 之后每次出现都加上出现的次数.

• 例如 1, 1, 1, 3

• 第一次出现1, res不进行相加, 此时计数1次

• 第二次出现1, res相加, res=1, 此时计数2次

• 第三次出现1, res相加, res=3, 此时计数3次

• 遍历结束 返回res

代码实现:

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int[] count = new int[101];
        int res = 0;
        for(int num : nums) {
            res += count[num];
            count[num]++;
        }
        return res;
    }
}

第三题: 面试题 10.11. 峰与谷

LeetCode: 面试题 10.11. 峰与谷

描述:
在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。

解题思路:

1. 此题意思就是一个大一个小, 交替进行.
2. 可以让数组进行排序.
3. 然后使用双指针, 一个指向头, 一个指向尾.
4. 每次放一个最大的(right–), 再放一个最小的(left++),

代码实现:

class Solution {
    public void wiggleSort(int[] nums) {
        int[] arr = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            arr[i] = nums[i];
        }
        Arrays.sort(arr);
        int left = 0;
        int right = arr.length-1;
        for(int i = 0; i < nums.length; i++) {
            if(i%2==0){
                nums[i] = arr[right--];
            }else{
                nums[i] = arr[left++];
            }
        }
    }
}

第四题: 面试题 16.26. 计算器

LeetCode: 面试题 16.26. 计算器

描述:
给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

解题思路:

1. 这里使用一个栈来存储数据.
2. 把当前的数据进行存储, 要注意, 会出现连续数字的情况
3. 首次操作的时候, 直接进行入栈, 然后记录操作符.

• 如果再次发现是加减乘除的时候, 查看前一个操作符是什么

• 如果是 -, 存入 -num

• 如果是 +, 存入 num

• 如果是 *, 存入 stack.pop() * num

• 如果是 / , 存入 stack.pop() / num

• 结束遍历之后, 栈存入就全部是数据了, 此时直接将所有的数据进行相加就是结果

代码实现:

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        // 方便第一次直接入栈
        char opt = '+';
        int num = 0;
        for(int i = 0; i < s.length(); i++) {
            if(Character.isDigit(s.charAt(i))){
                num = num * 10 + (s.charAt(i) - '0');
            }
            if((!Character.isDigit(s.charAt(i)) && s.charAt(i)!=' ') || i == s.length() - 1){
                if(opt == '+') stack.push(num);
                else if(opt == '-') stack.push(-num);
                else if(opt == '*') stack.push(stack.pop() * num);
                else stack.push(stack.pop() / num);
                num = 0;
                opt = s.charAt(i);
            }
        }
        int res = 0;
        while(!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }
}

第五题: 面试题 17.12. BiNode

LeetCode: 面试题 17.12. BiNode

描述:
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

解题思路:

1. 这里使用中序遍历的方法.
2. 首先有一个前驱节点, 用来链接起来.
3. 中序遍历, 让先驱节点进行链接(链接在右节点),并让节点的左节点置空. 再让此节点指向root.
4. 最后返回前驱节点的下一节点.

代码实现:

class Solution {
    TreeNode cur = new TreeNode(-1);
    TreeNode pre = cur;
    public TreeNode convertBiNode(TreeNode root) {
        if (root == null) return null;
        convertBiNode(root.left);
        cur.right = root;
        root.left = null;
        cur = root;
        convertBiNode(root.right);
        return pre.right;
    }
}

第六题: 面试题 17.19. 消失的两个数字

LeetCode: 面试题 17.19. 消失的两个数字

描述:
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

解题思路:

1. 这里使用的数学思想
2. 首先求得数组的全部和 total
3. 然后利用 求和公式 求得 1 ~ len(nums)+2 的和 sum.
4. 然后让这个 sum - total 求出消失两个数的和.
5. 再求得这两个数的平均数 mid
6. 再次遍历, 求小于 mid 的数字和, 1 ~ mid 中肯定有一个消失的数字.
7. 让此时的和 减去 数组里满足条件的和. 就是其中一个结果.
8. 再让两个数的和 减去其中一个结果就是另一个结果.

代码实现:

class Solution {
    public int[] missingTwo(int[] nums) {
        int total = 0;
        for(int num : nums) {
            total += num;
        }
        int sum = (nums.length+2+1)*(nums.length+2)/2 - total;
        int mid = sum/2;
        total = 0;
        for(int num : nums) {
            if(num <= mid) {
                total += num;
            }
        }
        int res = (1+mid)*mid/2 - total;
        return new int[]{res, sum-res};
    }
}