码龙的成长之路

0%

leetcode每日一题系列

发表于 更新于
本文字数： 7.7k 阅读时长 ≈ 7 分钟

打卡leetcode每日一题

Num322 零钱兑换

image-20200308200528242

1
//回溯 未优化版本 超时
2
 int res =Integer.MAX_VALUE,count = 0;
3
    public int coinChange(int[] coins, int amount) {
4
        if(amount==0)
5
            return 0;
6
       dfs(coins,amount);
7
       return res==Integer.MAX_VALUE?-1:res;
8
    }
9
    public void dfs(int [] coins,int amount ){
10
        if(amount<0)
11
            return;
12
        if(amount==0){
13
            res = count==0?res: Math.min(res,count);
14
            return;
15
        }
16
        for(int i=0;i<coins.length;i++){
17
            count++;
18
            dfs(coins,amount-coins[i]);
19
            count--;
20
        }
21
    }
1
//记忆化搜索 回溯基础上用数组存放金额为F(S)的最少硬币数
2
public int coinChange(int[] coins, int amount) {
3
    if (amount == 0)
4
        return 0;
5
    return dfs(coins, amount, new int[amount]);
6
}
7
//自上而下
8
public int dfs(int[] coins, int amount, int[] dp) {
9
    if (amount < 0)
10
        return -1;
11
    if (amount == 0) 
12
        return 0;
13
    if (dp[amount - 1] != 0) return dp[amount - 1];//dp[amount-1]金额的最少硬币数已经记录过，直接返回
14
    int min = Integer.MAX_VALUE;
15
    for (int i = 0; i < coins.length; i++) {
16
        int res = dfs(coins, amount - coins[i], dp);//找到amount-coins[i]的最少硬币数
17
        if (res >= 0 && res < min)//小于当前最小值，改变min
18
            min = res + 1;
19
    }
20
    dp[amount - 1] = (min == Integer.MAX_VALUE ? -1 : min);//一次遍历完成后，存储当前amount的最少硬币数
21
    return dp[amount - 1];
22
}
1
//动态规划,自底而上
2
public int coinChange(int[] coins, int amount) {
3
    if(amount==0)
4
        return 0;
5
    int [] dp =new int[amount+1];//dp[i]: 构成金额为i所需的最少金币数
6
    dp[0] =0;//从0开始
7
    for(int i=1;i<=amount;i++){
8
        int min =Integer.MAX_VALUE;
9
        for(int j=0;j<coins.length;j++){
10
            if(i-coins[j]>=0&&dp[i-coins[j]]<min)//找到i-coins[j]的最少硬币数
11
                min = dp[i-coins[j]]+1;
12
        }
13
        dp[i] =min;
14
    }
15
    return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
16
}
1
//高效 DFS+贪心剪枝
2
//从最大硬币面值开始遍历，乘法加快(amount/coins[index]),再DFS+剪枝，再依次减去最大硬币数
3
int ans=Integer.MAX_VALUE;
4
public int coinChange(int[] coins, int amount) {
5
    Arrays.sort(coins);
6
    dfs(coins,coins.length-1,amount,0);
7
    return ans==Integer.MAX_VALUE?-1:ans;
8
}
9
public void dfs(int[] coins,int index,int amount,int cnt){
10
    if(index<0){
11
        return;
12
    }
13
    for(int c=amount/coins[index];c>=0;c--){
14
        int na=amount-c*coins[index];
15
        int ncnt=cnt+c;
16
        if(na==0){
17
            ans=Math.min(ans,ncnt);
18
            break;//剪枝1
19
        }
20
        if(ncnt+1>=ans){
21
            break; //剪枝2
22
        }
23
        dfs(coins,index-1,na,ncnt);
24
    }
25
}
26
//参考：https://leetcode-cn.com/problems/coin-change/solution/dfsjian-zhi-2ms-ji-bai-100bi-dphuan-kuai-by-iejepw/

Num1071 字符串最大公因子

image-20200312211729264

1
//暴力，从大到下依次判断
2
  public String gcdOfStrings(String str1, String str2) {
3
        int len1 = str1.length(),len2 =str2.length();
4
         for(int i=Math.min(len1,len2);i>0;i--){
5
            if(len1%i==0&&len2%i==0){//构成最大公因子前提1:长度符合要求
6
                String temp = str1.substring(0,i);
7
                if(func(temp,str1)&&func(temp,str2))//前提2：以len分割的长度即满足str1也满足str2
8
                        return temp;
9
            }           
10
        }
11
        return "";
12
    }
13
    public boolean func(String  res,String str){//判断res是否是str的字符串公因子
14
        int len = str.length()/res.length();
15
        String s= "";
16
        while(len>0){
17
            s+=res;
18
            len--;
19
        }
20
        return str.equals(s);
21
    }
1
//最大公约数法
2
//若x为两字符串的公因子，那么两字符串长度的最大公约数所截取的字符串长度必然也是它的公因子
3
//比如:str1="ABABABAB",str2="ABAB",gcd=4,若x="AB"，长度为4为字符串的最大公因子,而str1可以经过AB四次拼接得到，这里的AB可看作为X
4
class Solution {
5
    public String gcdOfStrings(String str1, String str2) {
6
        int len1 = str1.length(),len2 =str2.length();
7
        int g = gcd(len1,len2);
8
        if(func(str1.substring(0,g),str1)&&func(str1.substring(0,g),str2))//func同上
9
            return str1.substring(0,g);
10
        return "";
11
    }
12
    public int gcd(int a,int b){
13
        if(b!=0&&a%b==0)
14
            return b;
15
        return gcd(b,a%b);
16
    }
1
//数学方法 str1+str2==str2+str1
2
public String gcdOfStrings(String str1, String str2) {
3
    int len1 = str1.length(),len2 =str2.length();
4
    if(!(str1+str2).equals(str2+str1))
5
        return "";
6
    int g = gcd(len1,len2);
7
    return str1.substring(0,g);
8
}

Num300 最长递增子序列

1
/**输入: [10,9,2,5,3,7,101,18]
2
输出: 4 
3
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
4
**/
5
//贪心+二分查找
6
//如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
7
public int lengthOfLIS(int[] nums) {
8
    if (nums.length == 0)
9
        return 0;
10
    int[] tmp = new int[nums.length]; //tmp保证的是递增序列
11
    //[10,9,2,5,3,7,101,18]
12
    //tmp =[10],[9],[2],[2,5],[2,3],[2,3,7],[2,3,7,101],[2,3,7,18]
13
    int res = 0;
14
    //目标 找到tmp中大于当前num的值进行替换,如tmp=[10,13,14],此时num=12, tmp=[10,12,14]
15
    for (int num : nums) {
16
        int left = 0, right = res;
17
        while (left < right) {
18
            int mid = left + (right - left) / 2;
19
            if (num > tmp[mid]) left = mid + 1;//当前元素大于tmp中间的值，再往后找
20
            else right = mid;
21
        }
22
        tmp[left] = num;
23
        if (res == right)//若此时right还指向最后一个元素，说明tmp中没有大于num的元素，长度要加1
24
            res++;
25
    }
26
    return res;
27
}

Num365 水壶问题

image-20200321144522503

1
//BFS
2
public boolean canMeasureWater(int x, int y, int z) {
3
    if(z==0)
4
        return true;
5
    if(x+y<z)
6
        return false;
7
    HashSet<Integer> set =new HashSet<>();//去重，防止重复加入
8
    Queue<Integer> q = new LinkedList<>();//存放所有可能获得的水量的结果
9
    q.offer(0);
10
    while(!q.isEmpty()){
11
        Integer n = q.poll();
12
        //1加满x，在满足总水量不超过两容量水分之和的前提下添加
13
        if(n+x<=x+y&&set.add(n+x))
14
            q.offer(n+x);
15
        //2 加满y，在满足总水量不超过两容量水分之和的前提下添加
16
        if(n+y<=x+y&&set.add(n+y))
17
            q.offer(n+y);
18
        //3 倒掉x，当前总水量大于等于x时，可以选择将其倒掉x升
19
        if(n-x>=0&&set.add(n-x))
20
            q.offer(n-x);
21
        //4 倒掉y，当前总水量大于等于y时，可以选择将其倒掉y升
22
        if(n-y>=0&&set.add(n-y))
23
            q.offer(n-y);
24
        if(set.contains(z))
25
            return true;
26
    }
27
    return false;
28
}
1
//数学方法
2
//裴蜀定理：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
3
//简言之，当z能整除gcd(x,y)时，说明经x和y可以得到z升的水
4
public boolean canMeasureWater(int x, int y, int z) {
5
    if(z==0)
6
        return true;
7
    if(x+y<z)
8
        return false;
9
    return z%gcd(x,y)==0;
10
}
11
public int gcd(int x,int y){
12
    if(y==0||x%y==0)
13
        return y;
14
    return gcd(y,x%y);
15
}

Num945 使数组唯一的最小增量

image-20200322153553502

1
//排序思想，使用优先队列
2
//[3,2,1,2,1,7]==>[1,1,2,2,3,7]==>[1,2,2,2,3,7]==>[1,2,3,2,3,7]==>[1,2,3,4,3,7]==>[1,2,3,4,5,7]
3
public int minIncrementForUnique(int[] A) {
4
    if(A.length<=1)
5
        return 0;
6
    PriorityQueue<Integer> queue = new PriorityQueue<>();
7
    for(int a:A){
8
        queue.offer(a);
9
    }
10
    int pre =-1;//前一个值
11
    int cur =-1;//当前值
12
    int ans =0;
13
    while(!queue.isEmpty()){
14
        cur = queue.poll();
15
        if(pre!=-1&&cur<=pre){//如果当前值小于或者等于之前的值需要move操作
16
            ans+=(pre-cur)+1;//当前需要move的次数
17
            cur += (pre-cur)+1;//将当前值改为move后新生成的值
18
        }
19
        pre = cur;
20
    }
21
    return ans;
22
}
1
//线性探测法思想
2
class Solution {
3
    int[] pos = new int [80000];
4
    public int minIncrementForUnique(int[] A) {
5
        Arrays.fill(pos, -1); // -1表示空位
6
        int move = 0;
7
        // 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。
8
        for (int a: A) {
9
            int b = findPos(a); 
10
            move += b - a;
11
        }
12
        return move;
13
    }
14
15
    // 线性探测寻址（含路径压缩）
16
    private int findPos(int a) {
17
        int b = pos[a];
18
        // 如果a对应的位置pos[a]是空位，直接放入即可。
19
        if (b == -1) { 
20
            pos[a] = a;
21
            return a;
22
        }
23
        // 否则向后寻址
24
        // 因为pos[a]中标记了上次寻址得到的空位，因此从pos[a]+1开始寻址就行了（不需要从a+1开始）。
25
        b = findPos(b + 1); 
26
        pos[a] = b; // 寻址后的新空位要重新赋值给pos[a]哦，路径压缩就是体现在这里。
27
        return b;
28
    }
29
}
30
/**
31
作者：sweetiee
32
链接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/solution/ji-shu-onxian-xing-tan-ce-fa-onpai-xu-onlogn-yi-ya/
33
来源：力扣（LeetCode）
34
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。**/

Num16 按摩师

题目链接:https://leetcode-cn.com/problems/the-masseuse-lcci/

1
//递归，超时
2
class Solution {
3
    int res =0;
4
    public int massage(int[] nums) {
5
        dfs(nums,0,nums.length,0);
6
        return res;
7
    }
8
    public void dfs(int [] nums,int index,int len,int value){
9
        if(index>=len){
10
            res =Math.max(res,value);
11
            return ;
12
        }
13
        for(int i=index;i<len;i++)
14
            dfs(nums,i+2,len,value+nums[i]);
15
    }
16
}
1
//动态规划
2
 public int massage(int[] nums) {
3
     if(nums.length==0)
4
         return 0;
5
     if(nums.length==1)
6
         return nums[0];
7
     int [] dp = new int[nums.length];//dp[i]代表数组长度为i时的最长预约时间
8
     dp[0]=nums[0];
9
     dp[1] = Math.max(nums[0],nums[1]);
10
     for(int i=2;i<nums.length;i++){
11
         dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
12
     }
13
     return dp[nums.length-1];    
14
 }
1
//动态规划：时间O(N)，空间O(1)
2
public int massage(int[] nums) {
3
    if(nums.length==0)
4
        return 0;
5
    if(nums.length==1)
6
        return nums[0];
7
    int tmp_max=0,max=0;//tmp_max 存储dp[i-2],max存储dp[i-1]
8
    for(int i=0;i<nums.length;i++){
9
        int temp = Math.max(tmp_max+nums[i],max);//计算dp[i]
10
        tmp_max = max;//dp[i-1]成为下一个dp[i-2]
11
        max = temp;//dp[i]成为dp[i-1]
12
    }
13
    return max;           
14
}
-------------未完待续-------------