LeetCode——每日一题
记录自己刷过的leetCode，作为菜鸡肯定是从简单开始啦。附上Github地址——LeetCodeRecord
1.两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<nums.count{
for j in i+1..<nums.count{
if (target - nums[i] == nums[j]) {
return [i, j]
}
}
}
return [Int]()
}
7.反转整数
给定一个 32 位有符号整数，将整数中的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
func reverse(_ x: Int) -> Int {
var x = x
var rev = 0
while x != 0 {
let p = x % 10
x /= 10
if (rev > Int32.max/10 || (rev == Int32.max/10 && p > 7)){
return 0
}
if (rev < Int32.min/10 || (rev == Int32.min/10 && p < -8)){
return 0
}
rev = rev * 10 + p
}
return rev
}
9.回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
func isPalindrome(_ p: Int) -> Bool {
if p < 0 || (p % 10 == 0 && p != 0){
return false
}
var x = p
var rev = 0
while x > rev {
rev = rev * 10 + x % 10
x /= 10
}
return x == rev || x == rev/10
}
13.罗马数字转整数
func romanToInt(_ s: String) -> Int {
var res = 0
var dic:[String:Int] = ["I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000]
var arr = [String]()
for str in s {
arr.append(String.init(str))
}
for i in 0..<arr.count {
/// 肯定有值，强转就好
let val = dic[arr[i]]!
if i == arr.count - 1 || (dic[arr[i+1]]! <= dic[arr[i]]!){
res += val
}else{
res -= val
}
}
return res
}
14.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
func longestCommonPrefix(_ strs: [String]) -> String {
if strs.count == 0 { return "" }
var prefix = strs[0]
for i in 0..<strs.count {
while !strs[i].hasPrefix(prefix){
prefix.removeLast()
if prefix.isEmpty { return "" }
}
}
return prefix
}
20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
func isValid(_ s: String) -> Bool {
var arr = Array<String>()
for i in s{
if i == "(" || i == "[" || i == "{" {
arr.append(String(i))
}else{
if arr.count == 0{
return false
}
let f = arr.last!
if i == ")"{
if f != "("{
return false
}
}
if i == "]"{
if f != "["{
return false
}
}
if i == "}"{
if f != "{"{
return false
}
}
arr.removeLast()
}
}
return arr.count == 0
}
21.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
递归
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
guard let l1 = l1 else {
return l2
}
guard let l2 = l2 else {
return l1
}
if l1.val >= l2.val {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}else{
l1.next = mergeTwoLists(l1.next, l2)
return l1
}
}
迭代
func mergeTwoLists2(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1 = l1
var l2 = l2
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
let res:ListNode = ListNode.init(0)
var cur:ListNode? = res
while l1 != nil && l2 != nil {
/*
输出结果要求从小到大排序
如果l1的值小，把l1加入新的链表 并把l1的链表头去掉，再循环
*/
if l1!.val <= l2!.val {
cur?.next = l1
l1 = l1?.next
}else{
cur?.next = l2
l2 = l2?.next
}
/*
cur拷贝了res的next属性地址，所以每次修改cur.nextd值，res.next也会改变
同时cur = cur?.next，所以执行cur = cur?.next时 cur的指针指向了下一个
*/
cur = cur?.next
}
cur?.next = l1 == nil ? l2 : l1
return res.next
}
