【筆試實戰】LeetCode題單刷題-程式設計基礎 0 到 1【二】

2023-07-04 06:00:27

1822. 陣列元素積的符號

題目連結

1822. 陣列元素積的符號

題目描述

已知函數 signFunc(x) 將會根據 x 的正負返回特定值:

  • 如果 x 是正數,返回 1 。
  • 如果 x 是負數,返回 -1 。
  • 如果 x 是等於 0 ,返回 0 。

給你一個整數陣列 nums 。令 product 為陣列 nums 中所有元素值的乘積。

返回 signFunc(product) 。

 

範例 1:

輸入:nums = [-1,-2,-3,-4,3,2,1]
輸出:1
解釋:陣列中所有值的乘積是 144 ,且 signFunc(144) = 1

範例 2:

輸入:nums = [1,5,0,2,-3]
輸出:0
解釋:陣列中所有值的乘積是 0 ,且 signFunc(0) = 0

範例 3:

輸入:nums = [-1,1,-1,1,-1]
輸出:-1
解釋:陣列中所有值的乘積是 -1 ,且 signFunc(-1) = -1

 

提示:

  • 1 <= nums.length <= 1000
  • -100 <= nums[i] <= 100

解題思路一【Java語言】

時間0 ms 擊敗 100%

記憶體41.9 MB 擊敗 20.81%

這道題是判斷給定陣列中的元素有多少個負數,根據負數的個數決定返回1還是-1。如果陣列中有0,直接返回0。

具體解題思路如下:

  1. 初始化一個變數negative用於記錄負數的個數。
  2. 遍歷給定陣列nums中的每一個元素。
  3. 如果當前元素num等於0,則直接返回0。
  4. 如果當前元素num小於0,則將負數個數negative加一。
  5. 遍歷完陣列後,判斷負數個數negative是否為奇數,如果是則返回-1,否則返回1。

這個程式用到的知識點包括:

  1. 迴圈結構:使用for迴圈遍歷陣列中的每一個元素。
  2. 分支結構:使用if語句判斷當前元素是否為0或負數。
  3. 算術運算:使用求餘運運算元判斷負數個數是否為奇數。
  4. 陣列:使用陣列來儲存給定的整數序列。
class Solution {
    public int arraySign(int[] nums) {
       int negative=0;
        for(int num:nums){
            if(num==0){
                return 0;
            }
            if(num<0){
                negative++;
            }
        }
        return negative%2==1?-1:1;
    }
}

1502. 判斷能否形成等差數列

題目連結

1502. 判斷能否形成等差數列

題目描述

給你一個數位陣列 arr 。

如果一個數列中,任意相鄰兩項的差總等於同一個常數,那麼這個數列就稱為 等差數列 。

如果可以重新排列陣列形成等差數列,請返回 true ;否則,返回 false 。

 

範例 1:

輸入:arr = [3,5,1]
輸出:true
解釋:對陣列重新排序得到 [1,3,5] 或者 [5,3,1] ,任意相鄰兩項的差分別為 2 或 -2 ,可以形成等差數列。

範例 2:

輸入:arr = [1,2,4]
輸出:false
解釋:無法通過重新排序得到等差數列。

 

提示:

  • 2 <= arr.length <= 1000
  • -10^6 <= arr[i] <= 10^6

解題思路一【Java語言】

時間1 ms 擊敗 97.94%

記憶體39.9 MB 擊敗 15.26%

這道題是判斷給定陣列arr是否能夠構成等差數列。如果能夠構成等差數列,則返回true;否則,返回false。

具體解題思路如下:

  1. 引入java.util.Arrays中的sort方法對給定陣列arr進行排序。
  2. 使用for迴圈遍歷陣列中的每一個元素arr[i],從索引1開始,並且遍歷到倒數第二個元素。
  3. 在迴圈中,判斷當前元素arr[i]與其前一個元素arr[i-1]的差是否等於當前元素arr[i+1]與arr[i]的差。如果不相等,則說明不能構成等差數列,返回false。
  4. 如果迴圈結束後仍然沒有返回false,則說明陣列arr中的每個元素都滿足等差數列的條件,返回true。

這個程式用到的知識點包括:

  1. 陣列:使用陣列來儲存給定的整數序列。
  2. 引入其他類:使用import語句引入java.util包中的ArrayList類。
  3. 資料排序:使用Arrays類中的sort方法對陣列進行排序。
  4. 迴圈結構:使用for迴圈遍歷陣列中的每一個元素。
  5. 分支結構:使用if語句判斷等差數列的條件,並根據判斷結果返回對應的布林值。
import java.util.ArrayList;
class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        for(int i=1; i<arr.length-1; i++){
            if(arr[i]-arr[i-1]!=arr[i+1]-arr[i]){
                return false;
            }
        }
        return true;
    }
}

896. 單調數列

題目連結

896. 單調數列

題目描述

如果陣列是單調遞增或單調遞減的,那麼它是 單調 

如果對於所有 i <= jnums[i] <= nums[j],那麼陣列 nums 是單調遞增的。 如果對於所有 i <= jnums[i]> = nums[j],那麼陣列 nums 是單調遞減的。

當給定的陣列 nums 是單調陣列時返回 true,否則返回 false

 

範例 1:

輸入:nums = [1,2,2,3]
輸出:true

範例 2:

輸入:nums = [6,5,4,4]
輸出:true

範例 3:

輸入:nums = [1,3,2]
輸出:false

 

提示:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105

解題思路一【Java語言】

時間1 ms 擊敗 97.87%

記憶體53.8 MB 擊敗 51.24%

這道題的解題思路是判斷給定陣列nums是否是單調的(單調遞增或單調遞減)。如果是單調的,則返回true;否則,返回false。

具體解題思路如下:

  1. 首先檢查陣列的長度。如果陣列只有一個元素,則認為是單調的,直接返回true。如果陣列為空,即長度為0,則認為不是單調的,直接返回false。
  2. 判斷陣列的單調性。如果陣列的第一個元素小於等於最後一個元素,說明是單調遞增的情況,執行遞增判斷的迴圈操作;否則,執行遞減判斷的迴圈操作。
  3. 在迴圈中,遍歷陣列中的每個元素nums[i],從索引1開始。
  4. 如果是遞增判斷,判斷當前元素nums[i]是否小於前一個元素nums[i-1],如果小於,則說明不是單調的,返回false。
  5. 如果是遞減判斷,判斷當前元素nums[i]是否大於前一個元素nums[i-1],如果大於,則說明不是單調的,返回false。
  6. 如果迴圈結束後沒有返回false,則說明陣列nums是單調的,返回true。

這個程式用到的知識點包括:

  1. 陣列:使用陣列來儲存給定的整數序列。
  2. 迴圈結構:使用for迴圈遍歷陣列中的每一個元素。
  3. 分支結構:使用條件判斷語句if來判斷陣列的單調性,並根據判斷結果返回對應的布林值。
class Solution {
     public boolean isMonotonic(int[] nums) {
        if(nums.length == 1) return true;
        if( nums.length == 0) return false;
        if( nums[0] <= nums[nums.length - 1]){
            for(int i = 1 ; i < nums.length ; i++){
                if( nums[i] < nums[i-1] )
                    return false;
            }
        }else{
            for(int i = 1 ; i < nums.length ; i++){
                if( nums[i] > nums[i-1])
                    return false;
            }
        }
        return true;
    }
}

13. 羅馬數位轉整數

題目連結

13. 羅馬數位轉整數

題目描述

羅馬數位包含以下七種字元: I, V, X, LCD 和 M

字元          數值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 羅馬數位 2 寫做 II ,即為兩個並列的 1 。12 寫做 XII ,即為 X + II 。 27 寫做  XXVII, 即為 XX + V + II 。

通常情況下,羅馬數位中小的數位在大的數位的右邊。但也存在特例,例如 4 不寫做 IIII,而是 IV。數位 1 在數位 5 的左邊,所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地,數位 9 表示為 IX。這個特殊的規則只適用於以下六種情況:

  • I 可以放在 V (5) 和 X (10) 的左邊,來表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左邊,來表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左邊,來表示 400 和 900。

給定一個羅馬數位,將其轉換成整數。

 

範例 1:

輸入: s = "III"
輸出: 3

範例 2:

輸入: s = "IV"
輸出: 4

範例 3:

輸入: s = "IX"
輸出: 9

範例 4:

輸入: s = "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.

範例 5:

輸入: s = "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

 

提示:

  • 1 <= s.length <= 15
  • s 僅含字元 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • 題目資料保證 s 是一個有效的羅馬數位,且表示整數在範圍 [1, 3999] 內
  • 題目所給測試用例皆符合羅馬數位書寫規則,不會出現跨位等情況。
  • IL 和 IM 這樣的例子並不符合題目要求,49 應該寫作 XLIX,999 應該寫作 CMXCIX 。
  • 關於羅馬數位的詳盡書寫規則,可以參考 羅馬數位 - Mathematics 

解答思路一【Java】

時間4 ms 擊敗 58.6%

記憶體42.5 MB 擊敗 40.64%

解題思路是將給定的羅馬數位字串s轉換為對應的整數值。具體解題思路如下:

  1. 首先建立一個HashMap,用於儲存羅馬數位與對應的整數關係。將每個羅馬數位字元作為鍵,對應的整數值作為值,存入HashMap中。

  2. 初始化一個變數result,用於儲存最終的整數結果。

  3. 使用for迴圈遍歷字串s中的每一個字元。

  4. 在迴圈中,獲取當前字元的對應整數值,通過map.get()方法獲取。

  5. 判斷下一個字元是否存在,並且下一個字元對應的數值是否大於當前字元對應的數值。如果滿足條件,說明需要進行減法運算,將當前字元對應的數值取反後加入result;否則,將當前字元對應的數值加入result。

  6. 遍歷完成後,返回最終的整數結果result。

這個程式用到的知識點包括:

  1. HashMap:使用雜湊對映來建立羅馬數位與整數之間的關係。
  2. 字串的遍歷:使用for迴圈遍歷字串中的每一個字元。
  3. 條件判斷:根據當前字元及其後一個字元的數值大小關係,確定是否需要進行減法運算。
  4. 字串與整數的轉換:通過map.get()方法獲取字元對應的整數值,並進行相應的運算。
class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        
        int result = 0;
        
        for (int i = 0; i < s.length(); i++) {
            int currentValue = map.get(s.charAt(i));
            
            // 如果下一個字元存在且比當前字元對應的數值大,則將當前數值取反加入result
            if (i < s.length() - 1 && map.get(s.charAt(i + 1)) > currentValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
        }
        
        return result;
    }
}

58. 最後一個單詞的長度

題目連結

58. 最後一個單詞的長度

題目描述

給你一個字串 s,由若干單片語成,單詞前後用一些空格字元隔開。返回字串中 最後一個 單詞的長度。

單詞 是指僅由字母組成、不包含任何空格字元的最大子字串。

 

範例 1:

輸入:s = "Hello World"
輸出:5
解釋:最後一個單詞是「World」,長度為5。

範例 2:

輸入:s = "   fly me   to   the moon  "
輸出:4
解釋:最後一個單詞是「moon」,長度為4。

範例 3:

輸入:s = "luffy is still joyboy"
輸出:6
解釋:最後一個單詞是長度為6的「joyboy」。

 

提示:

  • 1 <= s.length <= 104
  • s 僅有英文字母和空格 ' ' 組成
  • s 中至少存在一個單詞

解題思路一【Java】

時間0 ms 擊敗 100%

記憶體39.8 MB 擊敗 40.23%

具體解題思路如下:

  1. 使用split方法將字串s按照空格進行拆分,得到一個字串陣列temp。拆分後,陣列temp的最後一個元素就是最後一個單詞。

  2. 返回陣列temp中最後一個元素的長度,即temp[temp.length-1].length()。

這個程式用到的知識點包括:

  1. 字串的拆分:使用split方法按照指定的分隔符將字串拆分為字串陣列。
  2. 陣列的使用:通過陣列索引獲取字串陣列中的元素。
  3. 字串的長度計算:使用length()方法獲取字串的長度。
class Solution {
    public int lengthOfLastWord(String s) {
        String temp[]=s.split(" ");
        return temp[temp.length-1].length();
    }
}

709. 轉換成小寫字母

題目連結

709. 轉換成小寫字母

題目描述

給你一個字串 s ,將該字串中的大寫字母轉換成相同的小寫字母,返回新的字串。

範例 1:

輸入:s = "Hello"
輸出:"hello"

範例 2:

輸入:s = "here"
輸出:"here"

範例 3:

輸入:s = "LOVELY"
輸出:"lovely"

 

提示:

  • 1 <= s.length <= 100
  • s 由 ASCII 字元集中的可列印字元組成

解答思路一【Java】

時間0 ms 擊敗 100%

記憶體39.5 MB 擊敗 75.76%

class Solution {
    public String toLowerCase(String s) {
        return s.toLowerCase();
    }
}

工程紀錄檔

2023-07-04

  • 之前提到要繞開題目給的誤導性思路,但是一直拿不出來一個合適的方向,今天的1822. 陣列元素積的符號題目讓我有了一點方向,我願稱之為透過現象看本質
  • 這部分的題目普遍都比較簡單,迷惑性的特點佔多一些,邏輯性的要求較少,基本上只要能夠看透本質,都是能秒殺的題目