【100天演算法入門 - 每日三題 - Day16】第三大的數、字串中的單詞數、排列硬幣

大連棒棰島

演算法是進階架構師的基礎，基礎不牢，地動山搖，2021-8-14起開始刷題，目標100天，300道LeetCode演算法題，分享是學習的最好方式，加油，嗨起來，

1、LeetCode 414.第三大的數

題目

給你一個非空陣列，回傳此陣列中 第三大的數 ，如果不存在，則回傳陣列中最大的數，

小編思路

1、先進行去重，然后按從小到大排序

2、如果只有一個或兩個數，則取最小的那個

3、如果有兩個以上的數字，則取第三大的數字

小編菜解

public static int thirdMax(int[] nums) {
    if (nums == null || nums.length == 0){
        return -1;
    }
    Set<Integer> set = new HashSet<>();
    //先進行去重、大小排序
    Arrays.sort(nums);
    for (int num : nums) {
        set.add(num);
    }
    //再放入list中
    List<Integer> list = new ArrayList<>(set);
    //如果只有一個或兩個數，則取最小的那個
    if (list.size() < 3){
        return list.get(list.size()-1);
    }else{
        //如果有兩個以上的數字，則取第三大的數字
        return list.get(list.size()-3);
    }
}

不對嗎？

大佬指點江山

public int thirdMax(int[] nums) {
    int len  = nums.length;

    // 長度小于等于 2 時，取最大值即可
    if (len <= 2) {
        return Math.max(nums[0], nums[len - 1]);
    }

    long first, second, third;
    first = second = third = Long.MIN_VALUE;

    for (int i = 0; i < nums.length; i++) {

        int cur = nums[i];

        // 由于第幾大都是不能重復的，也就是說當前元素 cur 如果等于 first, second 時，忽略即可
        if (cur == first || cur == second) {
            // 忽略當前元素
            continue;
        }
        if (cur > first) {
            third = second;
            second = first;
            first = cur;
            continue;
        }
        if (cur > second) {
            third = second;
            second = cur;
            continue;
        }

        if (cur > third) {
            third = cur;
        }
    }

    return third == Long.MIN_VALUE ? (int)first : (int)third;
}

思路上都差不多，可我的不對啊，所以還是有差距的，

2、LeetCode 434.字串中的單詞數

題目

統計字串中的單詞個數，這里的單詞指的是連續的不是空格的字符，

請注意，你可以假定字串里不包括任何不可列印的字符，

小編菜解

public static int countSegments(String s) {
    if (s.length()==0){
        return 0;
    }
    return s.split(" ").length;
}

這題是不是有點侮辱人了？這么簡單，也叫演算法？

但是，提交失敗，事情往往沒有想象中的那么簡單！

輸入", , , , a, eaefa"會報錯，

哦，也對，如果多個連續的空格，就有問題了，

大佬指點江山

public int countSegments(String s) {
    String temp = s.trim();
    if (temp.length()==0){
        return 0;
    }
    return temp.split("\\s+").length;
}

連續的空格用正則運算式分隔就可以了，

3、LeetCode 441.排列硬幣

題目

你總共有 n 枚硬幣，你需要將它們擺成一個階梯形狀，第 k 行就必須正好有 k 枚硬幣，

給定一個數字 n，找出可形成完整階梯行的總行數，

n 是一個非負整數，并且在32位有符號整型的范圍內，

小編菜解

public static int arrangeCoins(int n) {
    //第一行是1，第二行是2，第三行是3，第四行是4.，，
    int line = 1;
    int sum = 0;
    //為倒數第二行的行號
    int last = 0;
    while (sum < n){
        last = sum;
        sum += line;
        line++;
    }
    //如果n - last = 最后一行的行號，也就是說最后一行是滿行，否則不是
    if(n - last == line-1){
        return line-1;
    }else{
        return line - 2;
    }
}

思路及演算法

每一行的合計（從第一行合計到當前行）

第一行是1，第二行是2，和為3，第三行是3，和為6，第四行是4，和為10.，，

1*(1+1)/2=1
2*(2+1)/2=3
3*(3+1)/2=6
4*(4+1)/2=10
n*(n+1)/2

大佬指點江山

public static int arrangeCoins(int n) {
    //第一行是1，第二行是2，和為3，第三行是3，和為6，第四行是4，和為10.，，
    int line = 1;
    int left = 1;
    int right = n;
    while (left<=right){
        //二分查找
        int middle = left+(right-left)/2;
        //按照規律計算總數和
        long total = (long)middle * (middle + 1)/2;
        if (total > n){
            right = middle - 1;
        }else{//如果total小于n，則表示累加還在繼續，直到left<=right,獲取最后一個line
            left = middle + 1;
            line = middle;
        }
    }
    return line;
}