每日刷题记录 (一)

  • A+
所属分类:LeetCode

第一题: 按摩师

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};
    }
}
w3cjava

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: