4.29LeetCode

说一下，今天开始代码尽量准备用java写了，感觉好不习惯。。

198. House Robber

打家劫舍
比较简单的动态规划题目。
dp[i]=max(dp[i-1],dp[i-2]+nums[i])

// dp[i]表示前n户并且抢劫过第n家的max，感觉自己想复杂了。。。也可以通过。
// class Solution {
// public:
//     int rob(vector<int>& nums) {
//         if(nums.empty()) return 0;
//         if(nums.size()==1) return nums[0];
//         if(nums.size()==2) return max(nums[0],nums[1]);
//         vector<int> dp;
//         dp.resize(nums.size());
//         dp[0]=nums[0]; dp[1]=nums[1]; dp[2]=nums[0]+nums[2];
//         for(int i=3;i<nums.size();i++)
//             dp[i]=max(dp[i-2]+nums[i],dp[i-3]+nums[i]);
//         return max(dp[nums.size()-1],dp[nums.size()-2]);
//     }
// };


class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> dp;
        dp.resize(nums.size());
        dp[0]=nums[0]; dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++)
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        return dp[nums.size()-1];
    }
};

384. Shuffle an Array

打乱数组
第一次写java，感觉好难啊。。踩了好多坑，数组的深浅拷贝和伪随机函数等等.. 慢慢学吧注释的是评论区大佬的答案。

class Solution {
    int[] Arr;
    int[] Nature;
    public Solution(int[] nums) {
        Arr=nums;
        Nature= Arrays.copyOf(Arr, Arr.length);
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        for(int i=0;i<Arr.length;i++)
            Arr[i]=Nature[i];
        return Arrays.copyOf(Arr, Arr.length);
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for(int i=Arr.length-1;i>0;i--){
            Random rand=new Random();
            int t=rand.nextInt(i+1); //随机数生成范围要注意
            int temp=Arr[t];
            Arr[t]=Arr[i];
            Arr[i]=temp;
        }
        return Arr;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */


// class Solution {
//     int[] nums;

//     public Solution(int[] nums) {
//         this.nums = nums;
//     }
    
//     /** Resets the array to its original configuration and return it. */
//     public int[] reset() {
//         return nums;
//     }
    
//     /** Returns a random shuffling of the array. */
//     public int[] shuffle() {
//         int[] result = Arrays.copyOf(nums, nums.length);
//         Random rand=new Random();
//         for(int i = nums.length - 1; i > 0; i--) {
//             int n = rand.nextInt(i + 1);
//             // swap n and i 
//             int tmp = result[n];
//             result[n] = result[i];
//             result[i] = tmp;
//         }
//         return result;
//     }
// }

412. Fizz Buzz

java:

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res=new ArrayList<String>();
        for(int i=1;i<=n;i++){
            if(i%3==0&&i%5==0)
                res.add("FizzBuzz");
            else if(i%3==0&&i%5!=0) res.add("Fizz");
            else if(i%5==0&&i%3!=0) res.add("Buzz");
            else res.add(Integer.toString(i));
        }
        return res;
    }
}

204. Count Primes

计数质数
一开始的想法就是判断从1-n的每个数是否为质数，时间复杂度O(n^2)
最简单的方法当然通过不了，参考了某大佬的一篇博客进行剪枝
附连接：判断一个数是不是质数(素数)，3种方式介绍

class Solution {
    public int countPrimes(int n) {
        int res=0;
        for(int i=1;i<n;i++)
            if(isPrime(i)) res++;
        return res;
        
    }
    public static boolean isPrime(int num) {
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

}

然后根据题目下面的提示，了解了埃拉托色尼筛选法（质数问题）。唯一疑惑就是明明应该可以从i*i开始覆盖，不知道为什么总会报错说数组越界。

class Solution {
    public int countPrimes(int n) {
        if(n<3) return 0; 
        int res=0;
        int[] temp=new int[n];
        for(int i=0;i<n;i++)
            temp[i]=i;
        for(int i=2;i<n;i++){
            if(temp[i]==i){
                res++;
                for(int j=2;j*i<n;j++)
                    temp[j*i]=i;
            }
        }
        return res;
        
    }
}

326. Power of Three

递归解法很常规

class Solution {
    public boolean isPowerOfThree(int n) {
        if(n==1) return true;
        else if(n%3!=0||n==0) return false;
        else return isPowerOfThree(n/3);
    }
}

评论区大佬的两种解法：

class Solution {
    public boolean isPowerOfThree(int n) {
        String str=Integer.toString(n,3); //将n由十进制转化为3进制(java进制转换的写法，学到了)
        boolean result = str.matches("^10*$");//^表示正则开始，$表示正则结束,意思为匹配1开头中间可以无数个0的字符
        return result;
    }
}

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467%n == 0;
    }
}

13. Roman to Integer

写得太丑陋了。。不忍直视。。。有空一定重新用switch写下。。

class Solution {
    public int romanToInt(String s) {
        int res=0;
        int i=0;
        while(i<s.length()){
            if(s.charAt(i)=='M') {
                res+=1000;
                i++;
                continue;
            }
            if(s.charAt(i)=='D'){
                res+=500;
                i++;
                continue;
            }
            if(s.charAt(i)=='C'){
                if(i+1<s.length()&&s.charAt(i+1)=='D'){
                    res+=400;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='M'){
                    res+=900;
                    i+=2;
                }
                else {
                    res+=100;
                    i++;
                }
                continue;
            }
            if(s.charAt(i)=='L'){
                res+=50;
                i++;
                continue;
            }
            if(s.charAt(i)=='X'){
                if(i+1<s.length()&&s.charAt(i+1)=='L'){
                    res+=40;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='C'){
                    res+=90;
                    i+=2;
                }
                else {
                    res+=10;
                    i++;
                }   
                continue;
            }
            if(s.charAt(i)=='V'){
                res+=5;
                i++;
                continue;
            }
            if(s.charAt(i)=='I'){
                if(i+1<s.length()&&s.charAt(i+1)=='V'){
                    res+=4;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='X'){
                    res+=9;
                    i+=2;
                }
                else {
                    res+=1;
                    i++;
                }       
                continue;
            }
        }
        return res;
    }
}

191. Number of 1 Bits

为什么java里面没有unsignedint啊？？？？？？
学了了评论区大佬的解法，体会了下n=n&(n-1)的妙用(每次可以消掉一个1).

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
         int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

# C++, Java, 动态规划, 数组