LeetCode練習筆記 - Easy(C ++)

Komexeu
Komexeu
Nov 7 · 8 min read

題目: Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

題目解說:

此題要求寫一個 twoSum函數,尋找相加的兩個元素回傳其ID並輸出。

函數功能:
輸入vector <int>型別的 nums與 int型別的 target,target為 nums陣列中某兩個元素的和,尋找相加的兩個元素並回傳其ID。

解法:

宣告一個陣列tmp 用來儲存回傳值,利用雙迴圈搜尋所有元素,將相符的答案儲存進tmp中,迴圈結束後回傳tmp中的值。

References:

C ++ API-vector:http : //www.cplusplus.com/reference/vector/vector/
Solution of LeetCode : https://leetcode.com/articles/two-sum/

Vector : https://mropengate.blogspot.com/2015/07/cc-vector-stl.html


題目: Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

題目解說:

此題要求輸入32bits整數型別的 x,將x內容反轉後回傳輸出。

函數功能:
輸入int32型別的 x,回傳反轉後的 x。

解法:

利用 x>INT_MAX||x<INT_MIN 判斷x是否會溢位。

INT_MAX為 2147483647(2³²-1=> 7bytes)
INT_MIN為 -2147483648(2³² => 8bytes)

tmp_int用來儲存每位的數值,將x取餘數儲存進陣列tmp_int中,逐次將x/10直到下次x/10為0。
(若x/10之後為0,表示x總共有i+1位)

reverse_int為最終結果,由最高位元開始檢查是否會溢位,若達成溢位條件則return 0 結束迴圈。

References:

資料類型範圍 : https://docs.microsoft.com/zh-tw/cpp/cpp/data-type-ranges?view=vs-2019


題目:Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

題目解說:

此題要判斷回文,若為負數則直接輸出False。

函數功能:
輸入int型別的 x,判斷是否回文後回傳True or False。

解法:

事先去除負數值,利用num儲存每位的數值,利用(num的長度+1)/2當num ID的中值。

使用(num的長度+1)/2當中值,無論x有奇數個位元或偶數個位元都不影響後面的算式。

比對num[第一個元素ID+i]與num[最後一個元素ID-i]是否相同,最終比對次數約為num.size()的一半,其中若有不同則表示x不是回文,直接中斷迴圈。


題目:Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

範例:

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

題目解說:

此題要求將羅馬數字轉換為阿拉伯數字。

函數功能:
輸入string型別的羅馬數字,轉換為阿拉伯數字後回傳。

解法:

根據羅馬數字拼寫規則,判斷s[i+1]是否小於s[i],就可以得出是否使用"左減"的拼寫規則。

若為”左減”的拼寫規則 :
需先查表將s[i+1]-s[i]得出真正的數值後才能加進roman_int。

若為”右加”的拼寫規則 :
查表後直接加進roman_int。

References:

羅馬數字- 維基百科: https://zh.wikipedia.org/wiki/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97

C++-Map : https://mropengate.blogspot.com/2015/12/cc-map-stl.html

Komexeu

Written by

Komexeu

利用Blog記錄學習歷程,喜歡白天睡覺

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade