# LeetCode 讀書會第一次 2020/04/21
## 1. Two sums
### 暴力解
#### JS
```javascript=
numss [2,7,11,15], target = 9, Answer: [0, 1]
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] === target){
return [i,j]
}
}
}
};
```
>Runtime: **168 ms**, faster than 14.97% of JavaScript online submissions for Two Sum.
Memory Usage:** 34.8 MB**, less than 41.32% of JavaScript online submissions for Two Sum.
```javascript=
var twoSum = function(nums, target) {
for(let i = 0; i< nums.length; i++ ){
let index = nums.indexOf(target - nums[i])
if(index !== -1 && i !== index){
return [i, index]
}
}
}
```
> Runtime: **152 ms**, faster than 19.36% of JavaScript online submissions for Two Sum.
Memory Usage: **33.9 MB**, less than 97.93% of JavaScript online submissions for Two Sum.
#### PHP
`array_search` 也是跑 loop, 故也是暴力解。
```php=
function twoSum($nums, $target) {
$i=0;
while(true){
$x = $target - $nums[$i];
unset($nums[$i]); // 0~n -> 1~n
$k = array_search($x,$nums); // O(n)
if(gettype($k) == 'integer'){
return [$i, $k];
}
$i++;
}
}
```
> Runtime: **124** ms, faster than 61.24% of PHP online submissions for Two Sum.
Memory Usage: **16 MB**, less than 19.35% of PHP online submissions for Two Sum.
#### swift
```swift=
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<(nums.count-1) {
for j in (i+1)..<nums.count {
if nums[i] + nums[j] == target {
return [i, j]
}
}
}
return []
}
}
```
>Runtime: 492 ms, faster than 14.87% of Swift online submissions for Two Sum.
Memory Usage: 21.2 MB, less than 5.88% of Swift online submissions for Two Sum.
#### C++
> Runtime: **8** ms, 95%
Memory Usage: **42.2 MB**, 5%
- **解題方向**
1. 先 sort 陣列
- 根據 [std::sort](https://en.cppreference.com/w/cpp/algorithm/sort) 裡頭講的，這部分花了 `nlogn` 的時間
2. 把 target 減去陣列元素，並且用 binary search 去找出是否還存在另一個元素
- [geek - binary search](https://www.geeksforgeeks.org/binary-search/) 裡頭有說明這個演算法，時間是 `nlogn`
- **說明**
因為有 sort 過，但是回傳時又需要回傳原本值的 index，所以就想說乾脆犧牲記憶體，直接複製一個一樣的陣列，並且使用 `struct data` 這樣的結構去紀錄原本的 index 以及原本的值。
也可以不複製一個 vector，在抓到兩個 operand 出來之後，再回去原本的 vector 做查找，但這樣會使時間變慢，多花 `O(n)` 的時間。
```c=1
struct data{
int value;
int index;
};
```
- **程式碼**
- [1.cpp](https://github.com/Jonec76/LTcode/blob/master/1.cpp)
### 解法 2: 快查法
```javascript=
numss [2,7,11,15], target = 9, Answer: [0, 1]
var twoSum = function(nums, target) {
const comp = {};
for(let i=0; i<nums.length; i++){
let currentNum = nums[i];
if(comp[currentNum]>=0){
return [ comp[nums[i] ] , i]
}
let relativeNum = target-currentNum
comp[relativeNum] = i
}
}
first run -> curNum = 2, comp[2] not exist so set comp[9-2] = 0
second run -> curNum = 7, comp[7] is exist so return [comp[7],i]
```
> Runtime: **52 ms**, faster than 92.48% of JavaScript online submissions for Two Sum.
Memory Usage: **34.6 MB**, less than 77.69% of JavaScript online submissions for Two Sum.
```javascript=
var twoSum = function(nums, target) {
const map = new Map();
let result;
nums.forEach( (item, index) => {
let indexValue = target - item;
if (map.has(indexValue)) {
result = [map.get(indexValue), index];
}
map.set(item, index);
})
return result;
};
```
#### swift
```swift=
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict = [Int: Int]()
for i in 0...nums.count {
let difference = target - nums[i]
if dict[difference] != nil {
return [i, dict[difference]!]
}
dict[nums[i]] = i
}
return []
}
}
```
>Runtime: **28 ms**, faster than 99.54% of Swift online submissions for Two Sum.
Memory Usage: 21.2 MB, less than 5.88% of Swift online submissions for Two Sum.
### 先排序，在查找
複雜度 nlogn
nums [2,7,11,15], target = 9, Answer: [0, 1]
先 sort nums -> [2,7,11,15]
first run
頭尾 2 + 15 = 17 , 比 target 大，下次大的往右移
second rum
2 + 11 ...
## 7. Reverse Interger
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
Input: 2147483648
Output: 0
### Library 解法
```javascript=
const reverse = x => {
const limit = 2147483648; // 0xf7777777
const k = x < 0 ? -1 : 1;
const n = Number(String(Math.abs(x)).split('').reverse().join(''));
return n > limit ? 0 : n * k;
};
```
```java=
public int reverse(int x) {
long res = 0;
while (x != 0) {
res = res * 10 + x % 10; // 取個位數
x = x / 10; // x: 100 -> 10
}
if (res < Integer.MIN_VALUE || res > Integer.MAX_VALUE) {
return 0;
} else {
return (int)res;
}
}
```
#### C++
> Runtime: **4** ms, 50%
Memory Usage: **6.4 MB**, 100%
- **解題方向**
1. 用 `%` 的方法，把每個 digit 都抓出來並且存進 `vector`
2. 要處理 `overflow` 的問題，這裡蠻棘手的
- overflow 簡單來講，就是當值超過某個範圍時就無法正常儲存，以 32bit `int` 來講，其數值範圍是 [ $−2^{31}$ , $2^{31}$ − 1]. 。以大於 $2^{31}$ − 1 來講，當超過此數值時會由正轉負（詳細細節請再另外找資料），所以這邊的處理方法是使用 bitwise 的方式，檢查相加前後的 sign bit 是否相同。
但是少思考一點，當超過的值只超過一些，此時會是負數，但超過太多時又會是正數，以 `1534236462` 為例，其反過來會是 `-1648642945`，但以 `1534236469` 為例，其相反卻是 `1056389759`。==此部分的處理應該有更好的方法==，但這邊使用最粗糙的檢查法去檢查。
- **程式碼**
- [7.cpp](https://github.com/Jonec76/LTcode/blob/master/7.cpp)
Sign in with Wallet
Connect another wallet