第一题: 按摩师

LeetCode 面试题 17.16. 按摩师

描述:
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

解题思路:

动态规划思路:

• 状态 F(i) : 表示当前最长预约时间
• 状态转移方程: F(i) = Max( F(i-2)+nums[i] , F(i-1) )
• 初始状态: F(0) = nums[0] ,F(1) = Max( nums[0] , nums[1] )
• 返回结果: F(len-1)

这里主要考虑的问题是, 隔着相加时的总预约时间, 可能没有不隔着时的时间长.(一般动规不能连续取, 要休息都需要考虑这种情况)
例如: [1,5,2] 这里的 1+ 2 < 5, 所以 dp数组元素为 [1,5,5]
遍历结束, dp最后一个元素,就是最长预约时间

代码实现:

class Solution {
    public int massage(int[] nums) {
    	// 这里两种特殊情况
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        // 定义dp数组
        int[] dp = new int[nums.length];
        // 初始状态
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2; i < nums.length; i++){
        	// 状态转移方程
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        // 结果
        return dp[nums.length-1];
    }
}

第二题: 主要元素

LeetCode 面试题 17.10. 主要元素

描述:
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。
请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

解题思路:

这里可以用到哈希表, 排序等方法, 但是达不到时间复杂度为 O(N) 、空间复杂度为 O(1)
 
使用摩尔投票法来做:

1. 遍历当前数组 nums, count 表示当前数字的次数, num 为当前数字
2. 当count为0的时候, 让num等于 nums[i], count++;
3. 当count不为0的时候, nums[i] 不等于 num, 就让count–; 等于就让count++;
4. 遍历结束后, 再次进行遍历, 验证当前的num次数是否大于总元素的一半

代码实现:

摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
        int num = 0;
        int count = 0;
        for(int val : nums) {
        	// 票数为0, 更换新的投票人
            if(count == 0) num = val;
            // 如果是当前投票人的票就++
            if(num == val) count++;
            // 不是当前投票人的票就--
            else count--;
        }
        count = 0;
        // 判断当前投票人的票数是否超过一半
        for(int val : nums) {
            if(val == num) {
                count++;
            }
        }
        if(count>nums.length/2) return num;
        else return -1;
    }
}

HashMap的方法

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int val : nums) {
            map.put(val,map.getOrDefault(val,0)+1);
            if(map.get(val) > nums.length/2) return val;
        }
        return -1;
    }
}

第三题: 第 k 个数

LeetCode 面试题 17.09. 第 k 个数
描述:
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

解题思路:

动态规划思路:

• 状态 F(i) : 第i+1个数是哪个因子
• 状态转移方程: F(i) = Min(dp[x3] * 3, dp[x5] * 5, dp[x7] * 7)
• 初始状态: F(0) = 1
• 返回结果: F(len-1)
   

这里的dp[x3]*3,dp[x5]*5,dp[x7]*7 相当于三个丑数数列

• dp[0]*3, dp[1]*3,dp[2]*3, … , dp[n]*3
• dp[0]*5, dp[1]*5,dp[2]*5, … , dp[n]*5
• dp[0]*7, dp[1]*7,dp[2]*7, … , dp[n]*7

通过这三个数列取最小值来合并, 来组成这个完整的丑数数列.每次取了一列的数据之后, 就让该列数据往后加1,
例如

代码实现:

class Solution {
    public int getKthMagicNumber(int k) {
    	// 初始下标都是从0开始
        int x3 = 0;
        int x5 = 0;
        int x7 = 0;
        // 定义丑数数列 dp
        int[] dp = new int[k];
        // 初始化
        dp[0] = 1;
        for(int i = 1; i < k;i++) {
            // 取得最小值
            dp[i] = Math.min(Math.min(dp[x3]*3,dp[x5]*5),dp[x7]*7);
            // 这里使用 3个if 就可以排除重复的情况
            if(dp[i] == dp[x3]*3) x3++;
            if(dp[i] == dp[x5]*5) x5++;
            if(dp[i] == dp[x7]*7) x7++;
        }
        return dp[k-1];
    }
}

第四题: 连续数列

LeetCode 面试题 16.17. 连续数列
描述:
给定一个整数数组，找出总和最大的连续数列，并返回总和。

解题思路:

动态规划思路:

• 状态 F(i) : i坐标下的最大和
• 状态转移方程: F(i) = Max( nums[i]+F(i-1),nums[i])
• 初始状态: F(0) = nums[0]
• 返回结果: Max(F(i))
   

基本的动规解法, 只需要记录下最大值即可.

代码实现:

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res=dp[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(nums[i]+dp[i-1],nums[i]);
            // 记录最大值
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

第五题: 面试题 16.15. 珠玑妙算

LeetCode 面试题 16.15. 珠玑妙算
描述:
珠玑妙算游戏（the game of master mind）的玩法如下。

计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。

给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。

解题思路:

本题意思就是说, 如果当前猜测的是对的, 猜中的就+1, 剩下不对的, 如果有颜色猜中就算伪猜中, 但不算猜中的那一个.
例如 solution="RGBY" guess="GGRR'
这里猜中了 i=1坐标下的 G, solution剩余 “RBY” guess剩余"GRR", 对应的只能算一次伪猜中

1. 先进行一次遍历, 计算猜中的次数, 然后记录没猜中的元素.
2. 再次遍历没猜中的元素, 计算当前伪猜中次数.

代码实现:

class Solution {
    public int[] masterMind(String solution, String guess) {
        int[] answer = new int[2];
        // str记录没猜中字符
        StringBuilder str = new StringBuilder();
        // s记录计算机剩余字符次数
        int[] s = new int[130];
        for(int i = 0; i < 4; i++) {
            char ch1 = solution.charAt(i);
            char ch2 = guess.charAt(i);
            if(ch1 == ch2){
            	//这里是计算猜中次数
                answer[0]++;
            }else{
                s[ch1-'A']++;
                str.append(ch2);
            }
        }
        for(int i = 0; i < str.length() ; i++){
            char ch = str.charAt(i);
            // 如果我猜的颜色, 计算机中还有剩余,就算伪猜中
            if(s[ch-'A'] != 0){
                s[ch-'A']--;
                answer[1]++;
            }
        }
        return answer;
    }
}

第六题: 部分排序

LeetCode 面试题 16.16. 部分排序
描述:
给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

解题思路:

1. 拷贝数组, 对拷贝的数组进行排序.
2. 然后找出第一次不对应的坐标 left 以及最后一次不对应的坐标 right
3. 初始定义的时候 定义 left =-1``right =-1 这样当没有不对应坐标时, 就可以返回[-1,-1]

代码实现:

class Solution {
    public int[] subSort(int[] array) {
        int[] arr = Arrays.copyOf(array,array.length);
        Arrays.sort(arr);
        int left=-1;
        int right =-1;
        for(int i = 0; i < arr.length; i++) {
            if (arr[i] != array[i]){
            	// left只记录第一次不匹配的坐标
                if(left == -1) {
                    left = i;
                }
                // right记录最后一次不匹配的坐标
                right = i;
            }
        }
        // 如果全部匹配, left right 就是 [-1,-1]
        return new int[]{left,right};
    }
}