小辣鸡的leetcode简单题刷题400600

400-500

404、左叶子之和

(https://leetcode-cn.com/problems/sum-of-left-leaves/)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        int res = 0; // 计算其和
        // 判断是否为左叶子
        if(root.left != null && root.left.left == null && root.left.right == null){
            res += root.left.val;
        }
        // 递归遍历
        return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right)+res;
    }
}

409、最长回文串

(https://leetcode-cn.com/problems/longest-palindrome/)

class Solution {
    public int longestPalindrome(String s) {
        int[] num = new int[58]; // 计算每个字符的个数
        if(s.length()==1) return 1;
        char[] ch = s.toCharArray();
        for(char c : ch){ // 遍历计数
            num[c-'A']++;
        }
        int cnt = 0;
        for(int i = 0; i < num.length; i++){ // 计算两个一对的字符个数
            cnt += num[i]/2;
        } 
        if(2*cnt == s.length()){ // 如果字符刚好能全部成对
            return 2*cnt;
        }
        else return 2*cnt+1; // 如果不能全部成对
    }
}

412、Fizz Buzz

(https://leetcode-cn.com/problems/fizz-buzz/)

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        for(int i=1; i <= n; i++){ // 一次遍历即可完成
            if( i % 3==0 && i % 5==0){
                list.add("FizzBuzz");
             }
            else if ( i % 3 == 0 && i % 5 != 0){
                list.add("Fizz");
            }
            else if ( i % 3 !=0 && i %5 == 0){
                list.add("Buzz");
            } else{
                list.add(""+i);
            }
        }
        return list;
    }
}

414、第三大的数

(https://leetcode-cn.com/problems/third-maximum-number/)

class Solution {
    public int thirdMax(int[] nums) { 
        // 不要用Integer.MIN_VALUE
        Integer first = null ;
        Integer second = null ;
        Integer third = null ;
        for (int i=0; i < nums.length; i++){
            Integer cur = nums[i];
            // 如果当前数等于其中一个数，那么则不进行更新操作
            if(cur.equals(first)||cur.equals(second)|| cur.equals(third)) continue;
            if(first == null || cur > first){ // 当前数大于三个数，全部更新
                third =second;
                second = first;
                first = cur;
            }
            else if(second == null || cur > second){ // 当前数只比第二个数大，更新后两个数
                third = second;
                second = cur;
            } else if(third == null || cur > third){ // 当前数之比第三个数大，只更新第三个数
                third = cur;
            }
        }
        // 如果没有第三大的数，则返回最大的数
        return third == null ? first:third;
    }
}

415. 字符串相加

(https://leetcode-cn.com/problems/add-strings/)

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1; 
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        while(i >= 0 || j >= 0 || carry != 0){ // 从右边依次相加
            if(i >= 0) carry += num1.charAt(i--) - '0'; // 标记进位数与对应数相加
            if(j >= 0) carry += num2.charAt(j--) - '0';
            sb.append(carry % 10); // 相加之后的余数
            carry /= 10; // 进位的数字
        }
        return sb.reverse().toString();
    }
}

434 、字符串中的单词数

(https://leetcode-cn.com/problems/number-of-segments-in-a-string/)

class Solution {
    public int countSegments(String s) {
        if(s.length() == 0) return 0; // 直接返回
        String[] s1 = s.split(" "); // 进行单词拆分
        int cnt = 0;
        for(String str: s1){ // 判断是否有连续的空格，计算非空格的单词数
            System.out.print(str+"->");
            if(!str.equals("") && !str.equals(" ")){
                cnt++;
            }
        }
        return cnt;
    }
}

441、排列硬币

(https://leetcode-cn.com/problems/arranging-coins/)

class Solution {
    public int arrangeCoins(int n) {
        int level = 1;
        while(n >= level){
            n -= level; // 减去填满的层数
            level++; // 每次所处的层数
        }
        return level -1;
    }
}

448、找到所有数组中消失的数字

(https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/)

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        int idx = 1;
        // 一次遍历将出现的数字的作为下标，修改下标对应的数字为负数
        for(int i =0; i< nums.length; i++){
            if(nums[Math.abs(nums[i])-1] > 0){
                nums[Math.abs(nums[i])-1] = -nums[Math.abs(nums[i])-1];
            }
        }
        for(int i = 0; i< nums.length; i++){
            if(nums[i]>0){
                list.add(i+1);
            }
        }
        return list;
    }
}

453. 最小操作次数使数组元素相等

(https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/)

class Solution {
    public int minMoves(int[] nums) {
        // 要是所有元素都相等，需要每次对n-1个数进行加一操作,就相当于每次对一个元素进行减一的操作
        // 要减到所有的数都相同，就拿每个数减去最小数，将将其差加起来就是最小的操作次数
        int min = nums[0];
        for(int i : nums){
            if(i < min){
                min = i;
            }
        }
        int sum = 0;
        for(int i : nums){
            sum += i - min;
        }
        return sum;
    }

}

455. 分发饼干

(https://leetcode-cn.com/problems/assign-cookies/)

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0; // g 的位置
        int j = 0; // 计算s的位置
        int num = 0;
        while(i < g.length && j < s.length){
            if(g[i++] <= s[j++]){
              	 num++;
            }
            else{
                j++;
            }
        }
        return num;
    }
}

459. 重复的子字符串

(KMP应用，有点难，还没做呢)

(https://leetcode-cn.com/problems/repeated-substring-pattern/)

461. 汉明距离

(https://leetcode-cn.com/problems/hamming-distance/)

class Solution {
    public int hammingDistance(int x, int y) {
        int res = x ^ y; // 异或求出其含有不同位的二进制串
        int cnt = 0; // 计算不同位的个数
        while(res > 0){
            if(res % 2 == 1) cnt ++; // 计算二进制串中1的个数
            res = res >> 1; // 向右移一位
            // res /= 2;  // 与上述操作一样
        }
        return cnt;
    }
}

476. 数字的补数

(https://leetcode-cn.com/problems/number-complement/)

class Solution {
    public int findComplement(int num) {
        int cnt = 0; //
        int temp = num; // temp临时用来移位
        while(temp > 0){
            temp = temp >> 1; //计算num有多少位数
            cnt = (cnt << 1) + 1; // 每次都向左移一位
        }
        return num ^ cnt; // 与num二进制位数相同的全1二进制串cnt进行异或
        // 返回结果
    }
}

482. 密钥格式化

(https://leetcode-cn.com/problems/license-key-formatting/)

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        int length =0;
        StringBuffer sb = new StringBuffer();
        // 计算除开'-'的字符串长度
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i)!= '-' ){
               length++;
                sb.append(s.charAt(i));
            }
        }
        // 由于每次insert操作会增加sb长度，也会改变相对位置，所以从后往前遍历
        for(int i = length - k; i > 0; i -= k){
            sb.insert(i, '-');
        }
        return sb.toString().toUpperCase();
    }
}

485. 最大连续 1 的个数

(https://leetcode-cn.com/problems/max-consecutive-ones/)

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0; // 计算最大连续个数
        int count = 0; // 临时计算
        for (int i = 0; i < nums.length; i++){
            if(nums[i]==1){
                count++; // 每次累计+1
                if(count > max){ // 次数大于max,则更新max
                    max = count;
                }
            }
            if(nums[i] != 1){ // 否则，重新计数
                count = 0;
            }
        }
        return max;
    }
}

492. 构造矩形

(https://leetcode-cn.com/problems/construct-the-rectangle/)

class Solution {
    public int[] constructRectangle(int area) {
        if(area <= 0) return new int[]{0,0};
        int weight = (int) Math.sqrt(area); // 最小的差值，肯定是正方形的时候
        
        // 方法一：进行遍历
        // int length = weight;
        // while(weight <= length){
        //     if(weight*length == area){
        //         return new int[]{length, weight};
        //     }
        //     else if(weight * length > area){
        //         weight --;
        //     } else{
        //         length++;
        //     }
        // }
        // return new int[]{length , weight};

        // 方法二： 还是基于正方形差最小的原则，每次进行weight-1，直到能整除
        while(area % weight != 0){
            weight--;
        }
        return new int[]{area /weight, weight};
    }
}

495. 提莫攻击

(https://leetcode-cn.com/problems/teemo-attacking/)

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int num = 0;
        if(timeSeries.length < 1) return 0; // 直接返回的结果
        if(timeSeries.length == 1) return  duration; // 只有一次攻击，则直接返回一次眩晕时间
        for (int i =1; i < timeSeries.length; i++){ // 遍历每次攻击的时间
            if((timeSeries[i]- timeSeries[i-1]) > duration){ // 时间间隔大于duration，则直接计数
                num += duration;
            }
            else { // 否则，计算两次攻击的间隔时间
                num += timeSeries[i]-timeSeries[i-1];
            }
            
        }
        return num + duration; // 结果加上最后一次攻击的眩晕时间
    }
}

496. 下一个更大元素 I

(https://leetcode-cn.com/problems/next-greater-element-i/)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        int k = 0;
        for(int i = 0; i < nums1.length; i++){
            int index = findIndex(nums2, nums1[i]); // 找到的nums2中对应相等的位置下标
            res[k++] = find(nums2, index);
        }
        return res;
    }

    // 寻找nums2中对应相等元素的位置
    public int findIndex(int[] nums, int num){
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == num){
                return i;
            }
        }
        return -1;
    }

    // 寻找比index位置的数大的右边第一个数
    public int find(int[] nums, int index){
        int res = -1;
        for(int j = (index+1); j < nums.length; j++){
            if(nums[j] > nums[index]){
                 return res = nums[j]; // 找到右边第一个比nums[index]大的数，则返回
            }
        }
        return res;
    }
}

500-600

500. 键盘行

(https://leetcode-cn.com/problems/keyboard-row/)

class Solution {
    public String[] findWords(String[] words) {
        // 记录每行的字符
        String s1 = "qwertyuiopQWERTYUIOP";
        String s2 = "asdfghjklASDFGHJKL";
        String s3 = "zxcvbnmZXCVBNM";
        List<String> list = new ArrayList<>(); // 返回数组
        for (int i = 0; i < words.length; i++){
            if(s1.indexOf(words[i].charAt(0)) >= 0){ // 查找第一个字符的匹配位置
                String s11 = find(words[i], s1);
                if(s11 != "") list.add(s11);
                
            }
            else if (s2.indexOf(words[i].charAt(0)) >= 0){
                String s12 = find(words[i], s2);
                if(s12 != "") list.add(s12);
            }else{
                String s13 = find(words[i], s3);
                if(s13 !=  "") list.add(s13);
            }
        }
        return list.toArray(new String[list.size()]);
    }
    // 查找该字符串是否能全部由同一行表示出来
    public String find(String str, String s){
        for(int i = 0; i < str.length(); i++){
            if(s.indexOf(str.charAt(i)) < 0){ // 如果有不是同一行的，直接返回空
                return "";
            }
        }
        return str;
    }
}

504. 七进制数

(https://leetcode-cn.com/problems/base-7/)

class Solution {
    public String convertToBase7(int num) {
        StringBuilder sb = new StringBuilder();
        int temp = num;
        if(num == 0) return "0"; // 如果为0 ，直接返回
        if(num < 0) { // 如果为负数，则先转换为正数计算
            temp = Math.abs(num);
        }
        while(temp > 0){ // 一次计算
            sb.append(temp % 7);
            temp /= 7;
        }
        if(num < 0) { // 小于0的数，要在前面加上负号
            sb = sb.reverse(); // 输出顺序是反着的， 要先进行反转字符串
            sb = sb.insert(0, '-');
            return sb.toString();
        }
        return sb.reverse().toString();
    }
}

506. 相对名次

(https://leetcode-cn.com/problems/relative-ranks/)

class Solution {
    public String[] findRelativeRanks(int[] score) {
        Map<Integer, Integer> map =new HashMap<>();
        for(int i = 0; i < score.length; i++){ // 将每个字符及其位置进行存储
            if(!map.containsKey(score[i])){
                map.put(score[i], i);
            }
        }
        Arrays.sort(score); // 升排序
        String[] res = new String[score.length]; // 返回的字符串数组
        int length = score.length;
        for(int i = 0; i < length; i++){ // 依次遍历其每个得分在原数组的位置
            int value = map.get(score[i]);
            if(length > 2){ // 如果人数大于3， 则以后的排名用数字表示
                res[value] = length - i +"";
            } 
            // 依次排出前三名
            if(i == length - 3) res[value] = "Bronze Medal";
            if(i == length - 2) res[value] = "Silver Medal";
            if(i == length -1) res[value] = "Gold Medal";
        }
        return res;
    }
}

507. 完美数

(https://leetcode-cn.com/problems/perfect-number/)

class Solution {
    public boolean checkPerfectNumber(int num) {
        int cnt = 0; // 计算相加结果
        for (int i = 1; i <= num/2; i++){ // 依次查找其正因子
            if(num % i == 0){
                cnt += i; // 相加
            }
        }
        if(cnt == num) return true;
        return false;
    }
}

509. 斐波那契数

(https://leetcode-cn.com/problems/fibonacci-number/)

class Solution {
    public int fib(int n) {
        // 方法一
        // if(n == 0) return 0;
        // if(n == 1) return 1;
        // return fib(n-1)+fib(n-2);
        

        // 方法二，dp
        if(n <= 1) return n;
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i<= n; i++){
            int sum = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
}

520. 检测大写字母

(https://leetcode-cn.com/problems/detect-capital/)

class Solution {
    public boolean detectCapitalUse(String word) {
        if(word.length() < 0) return false;
        int low = 0; // 记录大写的字符
        int upper = 0; // 记录小写的字符
        for(int i = 0; i < word.length(); i++){ // 遍历字符串中的大小写字符的个数
            if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z'){
                low++;
            } else {
                upper++;
            }
        }
        if(low == word.length()) return true; // 如果全为小写或大写返回true
        if(upper == word.length()) return true;
        // 如果第一个为大写，后面全为小写也返回true
        if(word.charAt(0) >= 'A' && word.charAt(0) <= 'Z' && low == word.length() -1){
            return true;
        }
        return false;
        
    }
}

521. 最长特殊序列 Ⅰ

(https://leetcode-cn.com/problems/longest-uncommon-subsequence-i/)

class Solution {
    public int findLUSlength(String a, String b) {
        return a.equals(b) ? -1: Math.max(a.length(), b.length());
    }
}

541. 反转字符串 II

(https://leetcode-cn.com/problems/reverse-string-ii/)

class Solution {
    public String reverseStr(String s, int k) {
        char[] str = s.toCharArray();
        int index = 0; // 标记该数每轮的位置是否小于k
        StringBuilder sb = new StringBuilder(); // 返回字符串
        int turn = 0; // 每次遍历的轮次
        for (int i = 0; i < str.length; i++){
            if(index < k ){
                sb.insert(turn*k*2, str[i]); // 标记需要反转的位置
                index++;
            }
            else{
                sb.append(str[i]); // 不需要反转的字符直接append
                index++;
                if(index == 2 * k) { // 如果遍历到2 * k 则重置每轮的index
                    index = 0;
                    turn ++; // 轮次+1
                }
            }
        }
        return sb.toString();
    }
}

551. 学生出勤记录 I

(https://leetcode-cn.com/problems/student-attendance-record-i/)

class Solution {
    public boolean checkRecord(String s) {
        int cntA = 0;// 记录A的次数
        int cntL = 0; // 记录L的次数
        for(int i = 0; i< s.length(); i++){
            if(s.charAt(i) == 'A'){
                cntA++; // 缺席超过两次，直接返回
                if(cntA >= 2) return false;
                cntL = 0; // 不是连续的L，则重置L
            }
            else if(s.charAt(i) == 'P'){ // 不是L，则重置L
                cntL = 0;
            } else{
                cntL++;
                if(cntL >= 3){ // 如果连续缺席超过3次，返回false
                    return false;
                }
            }
        }
        return true;
    }
}

557. 反转字符串中的单词 III

(https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/)

class Solution {
    public String reverseWords(String s) {
        String[] str = s.split(" "); // 以空格分割单词
        StringBuilder sb = new StringBuilder(); // 返回字符串
        for(int i = 0; i < str.length; i++){ // 依次反转字符串
            sb.append(reverse(str[i]));
            if(i != str.length-1){
                sb.append(" ");
            }
        }
        return sb.toString();
    }
    // 反转字符串
    public String reverse(String s){
        StringBuilder sb = new StringBuilder();
        for(int i = s.length()-1; i >=0 ; i--){
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

561. 数组拆分 I

(https://leetcode-cn.com/problems/array-partition-i/)

class Solution {
    public int arrayPairSum(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums); // 先对数组进行排序
        int res = 0;
        int i = 0; // 计算奇数位置的和
        while(i < length){
            res += nums[i];
            i += 2;
        }
        return res;
    }
}

563. 二叉树的坡度

(https://leetcode-cn.com/problems/binary-tree-tilt/)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findTilt(TreeNode root) {
        if(root == null) return 0;
        // 左子树-右子树的绝对值，作为该节点的坡度
        return Math.abs(slope(root.left) - slope(root.right)) 
        + findTilt(root.left) + findTilt(root.right);

    }


    // 求出以该节点为根的树的左右子树和
    public int slope(TreeNode root){
        if(root== null) return 0;
        return root.val + slope(root.left) + slope(root.right);
    }
}

566. 重塑矩阵

(https://leetcode-cn.com/problems/reshape-the-matrix/)

class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat[0].length; // 求出mat的行和列
        int n = mat.length;
        int size =m * n;	
        int col = 0; // 行——新数组的
        int row = 0; // 列
        int[][] res = new int[r][c];
        if(r * c != size) return mat;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                res[col][row++] = mat[i][j];
                if(row == c){ // 换行
                    row = 0;
                    col ++;
                }
            }
        }
        return res;
    }
}

575. 分糖果

(https://leetcode-cn.com/problems/distribute-candies/)

class Solution {
    public int distributeCandies(int[] candyType) {
        /** 方法1：先排序后遍历法
        int num = candyType.length / 2;
        Arrays.sort(candyType);
        int n = 1;
        for(int i = 1; i < num * 2; i++){
            if(candyType[i] != candyType[i-1]){
                n++;
            }
        }
        return n <= num? n : num;
        */

        // 方法2 用set
        Set<Integer> set = new HashSet<>(); // 利用set元素不重复的原则
        for(int i : candyType) set.add(i);
        return Math.min(set.size(), candyType.length /2);
    }
}

594. 最长和谐子序列

(https://leetcode-cn.com/problems/longest-harmonious-subsequence/)

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums); // 排序
        int max = 0;
        int left = 0;
        int begin = 0;
        for(left = 0; left < nums.length; left++){ // 开始遍历
            while(nums[left] - nums[begin] > 1){ // 该位置到与其相差大于1的数的位置
                begin++;
            }
            if(nums[left] - nums[begin] == 1){ // 求出距离差
                max = Math.max(max, left - begin+1); 
            }
        }
        return max;
    }
}

598. 范围求和 II

(https://leetcode-cn.com/problems/range-addition-ii/)

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        if(ops.length == 0) return m *n ;
        int col = ops[0][0]; // 表示第一个数组的行
        int row = ops[0][1]; // 表示第一个数组的列
        for(int i = 0; i < ops.length; i++){
            col = Math.min(col, ops[i][0]); // 求出行最小
            row = Math.min(row, ops[i][1]); // 求出列最小
        }
        return col * row;
    }
}

599. 两个列表的最小索引总和

(https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/)

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> map = new HashMap<>(); // 存储字符串和下标
        for(int i = 0; i < list1.length; i++){
            if(!map.containsKey(list1[i])){
                map.put(list1[i], i);
            }
        }
        int value;
        int min = list2.length + list1.length; // 最大索引
        List<String> list = new ArrayList<>(); // 记录返回数组
        for(int i = 0; i < list2.length; i++){
            if(map.containsKey(list2[i])){ // 包含该相同字符串
                value = map.get(list2[i]); // 计算器list1中的下标
                if (value + i < min){ // 如果下标比min小，则重新添加字符串
                    list.clear();
                    list.add(list2[i]);
                    min = value + i;
                }
                else if(value + i == min){ // 下标相同则直接添加
                    list.add(list2[i]);
                }
                    
            }
        }

        String[] result = new String[list.size()];
        int j = 0;
        for(String s : list){
            result[j++] = s;
        }
        return result;
    }
}

小辣鸡的leetcode简单题刷题400600

400-500

404、左叶子之和

409、最长回文串

412、Fizz Buzz

414、第三大的数

415. 字符串相加

434 、字符串中的单词数

441、 排列硬币

448、找到所有数组中消失的数字

453. 最小操作次数使数组元素相等

455. 分发饼干

459. 重复的子字符串

461. 汉明距离

476. 数字的补数

482. 密钥格式化

485. 最大连续 1 的个数

492. 构造矩形

495. 提莫攻击

496. 下一个更大元素 I

500-600

500. 键盘行

504. 七进制数

506. 相对名次

507. 完美数

509. 斐波那契数

520. 检测大写字母

521. 最长特殊序列 Ⅰ

541. 反转字符串 II

551. 学生出勤记录 I

557. 反转字符串中的单词 III

561. 数组拆分 I

563. 二叉树的坡度

566. 重塑矩阵

575. 分糖果

594. 最长和谐子序列

598. 范围求和 II

599. 两个列表的最小索引总和

441、排列硬币