Hint: The questions are all fromForce link (LeetCode)
Given an array of integers and a target value, find two numbers in the array that are neutral to the target value. You can assume that each input corresponds to only one answer, and that the same elements cannot be reused.
Example:
Given array NSArray *arr = @[2,7,11,15,20]; NSInteger target = 9; Because arr[0] + arr[1] = 9; So return [0,1]Copy the codeSolution:
Arr [I] = arr[I] = arr[I] = arr[I] = arr[I] 3, arr[I]+arr[j] if equal to target, output the subscript and element.Copy the codeOC sample code
NSInteger target = 11; NSArray *arr = @[@(2),@(11),@(7),@(9),@(0),@(3),@(6),@(1),@(8),@(5),@(4),@(111)]; for (int i = 0; i < arr.count; i++) { for (int j = i+1; j < arr.count; j++) { if ([arr[i] integerValue] + [arr[j] integerValue] == target) { NSLog(@"%@(%d) + %@(%d) = %ld\n",arr[i],i,arr[j],j,(long)target); }}}Copy the codeOutput result:
2 (0) + 9 (3) = 11 11 (1) + 0 11 (4) = 7 (2) + 4 = 11 (10) 3 (5) + 8 = 11 (8) 6 (6) + 5 = 11 (9)Copy the codeGiven two non-empty lists, representing two non-negative integers, the digits are stored in reverse order, and each of their nodes stores only a single number. Add the two numbers together and return a new list. You can assume that neither of these numbers will start with zero, except for the number 0.
Example:
NSArray *firstArr = @[@(2),@(4),@(3)]; NSArray *lastArr = @[@(5),@(6),@(4)]; Output,0,8 [7]Copy the codeSolution:
Create an array (NSInteger); create an array (NSInteger); create an array (NSInteger); create an array (NSInteger); Using the while loop, the remainder is added to array 6, the output arrayCopy the codeOC sample code
NSArray *starArr = @[@(2),@(4),@(3)];
NSArray *endArr = @[@(5),@(6),@(4)];
NSMutableArray *resArr = [NSMutableArray array];
NSInteger starInt = 0;
NSInteger endInt = 0;
NSInteger result = 0;
for (NSInteger i = starArr.count-1; i >= 0; i--) {
starInt = starInt*10+[starArr[i] integerValue];
}
for (NSInteger i = endArr.count-1; i >= 0; i--) {
endInt = endInt*10+[endArr[i] integerValue];
}
result = starInt+endInt;
while (result>9) {
[resArr addObject:@(result%10)];
result = (result-(result%10))/10;
}
[resArr addObject:@(result)];
if ([resArr[0] integerValue] == 0) {
[resArr removeObjectAtIndex:0];
}
Copy the codeThe output
342 + 465 = 807
(7,0,8)
Copy the codeGiven a 32-bit signed integer x, return the result of reversing the numeric portion of x. If the inverted integer exceeds the range of 32-bit signed integers [−231, 231 − 1], 0 is returned. Assume that the environment does not allow storage of 64-bit integers (signed or unsigned).
solution
1, first, data conversion, because not sure is 2, then positive or negative integers from the converted integer value from the back, assign a new value, can guarantee a flashback 3, each time assignment based quality original 10 and then add new value, ensure that the new value always in single digits add 4, after the flashback, determine the initial value is a negative integer or positive integer, Add the symbol 5 to determine whether the limit is exceeded. If so, return 0 directlyCopy the codeSwift sample code:
class Solution { func reverse(_ x: Int) -> Int { var res:Int = 0; var tmp = abs(x); while tmp > 0 { res = res*10 + tmp%10; tmp = tmp/10 } if x < 0 { res = 0 - res; } if ((-1<<31 <= res) && (res <= (1<<31-1))) { return res; }else{ return 0; }}}Copy the codeOutput result:
- 321.Copy the codeGiven an integer x, return true if x is a palindrome integer. Otherwise, return false. Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.
Solution:
If the value is a negative integer, return false. If the value is a negative integer, return false. If the value is a negative integer, return false. Ensure that the new value is always incremented by 5 in the ones digit, then check whether it is in the running range, if not directly return false 6, check whether it is equalCopy the codeSample Swift code:
class Solution { func isPalindrome(_ x: Int) -> Bool { if x < 0 { return false; } var res:Int = 0; var tmp = abs(x); while tmp > 0 { res = res*10 + tmp%10; tmp = tmp/10 } if ((-1<<31 <= res) && (res <= (1<<31-1))) { return res == x; }else{ return false; }}}Copy the code5. Roman numerals contain the following seven characters: I, V, X, L, C, D and M.
Character values I 1 V 5 X 10 L 50 C 100 D 500 M 1000Copy the codeFor example, the Roman numeral 2 is written as II, which is two ones side by side. Write XII as X + II. Write XXVII as XX + V + II. Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example, 4 is not written as IIII, it’s written as IV. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Similarly, the number 9 represents IX. This particular rule applies only to the following six situations:
I can be put to the left of V (5) and X (10) to represent 4 and 9.
X can be placed to the left of L (50) and C (100) to represent 40 and 90.
C can be put to the left of D (500) and M (1000) to represent 400 and 900.
Given a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999.
Solution:
1. Firstly, cut the given string into a single character and add it to the array. 2Copy the codeSample Swift code:
class Solution { func romanToInt(_ s: String) -> Int { let arr:NSMutableArray = NSMutableArray(); for tmp:Character in s { let str = String.init(tmp) var currValue = 0; if str.elementsEqual("I") { currValue = 1; }else if str.elementsEqual("V") { currValue = 5; }else if str.elementsEqual("X") { currValue = 10; }else if str.elementsEqual("L") { currValue = 50; }else if str.elementsEqual("C") { currValue = 100; }else if str.elementsEqual("D") { currValue = 500; }else if str.elementsEqual("M") { currValue = 1000; } if arr.count > 0 { let leftvalue:Int = arr[arr.count-1] as! Int; if leftvalue < currValue { arr.removeLastObject(); arr.add((currValue-leftvalue)) }else{ arr.add(currValue) } }else{ arr.add(currValue) } } var res = 0; for index in 0.. <arr.count { let leftvalue:Int = arr[index] as! Int res += leftvalue } return res } }Copy the codeWrite a function to find the longest public prefix in an array of strings. Returns the empty string “” if no public prefix exists.
Solution:
1. Calculate the minimum string length first. 2Copy the codeSwift sample code:
class Solution { func longestCommonPrefix(_ strs: [String]) -> String { var minStr:Int = 200 for str in strs { if str.lengthOfBytes(using: String.Encoding.utf8) < minStr { minStr = str.lengthOfBytes(using: String.Encoding.utf8) } } var res = "" for index in 0.. <minStr { var tmpRes = "" var count = 0 for str in strs { if tmpRes == "" { tmpRes = String.init(str[String.Index(encodedOffset: index)]) } if String.init(str[String.Index(encodedOffset: index)]) ! = tmpRes { count += 1 } } if (tmpRes ! = "" && count == 0) { res += tmpRes }else{ return res } } return res } }Copy the codeSeven, given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective. A valid string must meet the following requirements:
1. Open parentheses must be closed with close parentheses of the same type.
2. The left parentheses must be closed in the correct order.
solution
1, the incoming string is valid is whether the brackets, so creating an array, the string traversal from scratch, encounter parentheses is added, to determine whether the array is empty before time, if is empty added directly, if not null to judge whether the last and current corresponding 2, if the array brackets last brackets, corresponding to the current Then delete array the last value, current value add 3 operation, don't do is have left parenthesis is added to the array, met right parenthesis, he took the last value arrays, and see if the corresponding, if the corresponding solution, if not, continue to add 4, and finally determine whether array is empty to determine whether to conform to, empty saidCopy the codeSwift sample code
class Solution { func isValid(_ s: String) -> Bool { let arr:NSMutableArray = NSMutableArray() for char in s { if arr.count > 0 { if String(char) == foundValidValue(arr.lastObject as! String) { arr.removeLastObject() }else{ arr.add(String(char)) } }else{ arr.add(String(char)) } } return arr.count==0 } func foundValidValue(_ s:String) -> String { if s == "(" { return ")" }else if s == "[" { return "]" }else if s == "{" { return "}" }else{ return "" } } }Copy the codeMerge two ascending lists into a new ascending list and return. A new list is formed by concatenating all the nodes of a given two lists.
solution
2. Perform recursion to judge whether the value of the left list is large or the value of the right list is large. Assign the smaller value to the current node of the new list, and recurse the next valueCopy the codeSwift sample code
public class ListNode { public var val:Int public var next:ListNode? public init() { self.val = 0; self.next = nil; } public init(_ val:Int){ self.val = val; self.next = nil; } public init(_ val:Int,_ next:ListNode?) { self.val = val; self.next = next; } } class Solution { func mergeTwoLists(_ l1: ListNode? , _ l2: ListNode?) -> ListNode? { let list = ListNode.init() if l1 == nil && l2 ! = nil { return l2 } if l2 == nil && l1 ! = nil{ return l1 } if l1 == nil && l2 == nil { return nil } if l1! .val > l2! .val { list.val = l2! .val if l2? .next == nil { list.next = l1 }else{ list.next = mergeTwoLists(l1, l2? .next) } }else{ list.val = l1! .val if l1? .next == nil { list.next = l2 }else{ list.next = mergeTwoLists(l1? .next, l2) } } return list } func compareTwoLists(_ arr:NSMutableArray) -> ListNode? { let list = ListNode.init() if arr.count > 0 { list.val = arr.firstObject as! Int; arr.remove(arr.firstObject as Any) if arr.count > 0 { list.next = compareTwoLists(arr) } return list }else{ return nil } }}Copy the code9, give you an ordered array nums, ask you to delete the repeated elements, so that each element appears only once, return the deleted array after the new length. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.
# # # # :
Why is the return value an integer, but the output answer is an array?
Note that the input array is passed “by reference,” which means that modifying the input array in a function is visible to the caller.
You can imagine the internal operation as follows:
// Nums is passed by reference. That is, it does not make any copies of the arguments int len = removeDuplicates(nums); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the codesolution
If the array is not empty, there must be at least one element that does not repeat itself. 3. Since the array is an ordered array, we only need to check whether the adjacent elements are the same. Use a value to count the number of elements moved. 4. The resulting number of elements moved is the new array lengthCopy the codeSwift sample code
class Solution { func removeDuplicates(_ nums: inout [Int]) -> Int { if nums.count == 0 { return 0 } var fast = 1 var slow = 1 while fast < nums.count { if nums[fast] ! = nums[fast-1] { nums[slow] = nums[fast] slow += 1 } fast += 1 } return slow } }Copy the codeGiven an array nums and a value val, you remove all elements with a value equal to val and return the new length of the array. Instead of using extra array space, you must only use O(1) extra space and modify the input array in place. The order of elements can be changed. You don’t need to worry about the element after the new length in the array. #### Explanation: Why is the return value an integer, but the output answer is an array?
Note that the input array is passed “by reference,” which means that modifying the input array in a function is visible to the caller.
You can imagine the internal operation as follows:
// Nums is passed by reference. Int len = removeElement(nums, val); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the codesolution
1, first of all determine whether array is empty, empty directly returns 0 2, for a given the need to remove the element, so you just need to iterate through group and find the same element to be removed, but if use a for loop, traverse the array length in the process of change easy to skip over the adjacent elements, so using a while loop, the use of external value, When the element to be deleted is found, the subscript pointer is subtracted to prevent skipping the element check. 3. The array obtained at the end of the last traversal is the new array after removing the given elementCopy the codeSwift sample code
class Solution {
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
if nums.count == 0 {
return 0
}
var fast = 0
while fast < nums.count {
if nums[fast] == val {
nums.remove(at: fast)
fast -= 1
}
fast += 1
}
return nums.count
}
}
Copy the codeImplement strStr(). Given two strings haystack and needle, find the first place in the haystack string where needle appears (the subscript starts at 0). If none exists, -1 is returned. #### description: What value should we return when needle is an empty string? This is a good question to ask in an interview.
For this case, we should return 0 when needle is an empty string. This is consistent with the C language STRSTR () and the Java definition of indexOf().
solution
1, first read the question, whether in the search string containing a string 2, when there is the part where the beginning of the first appeared string subscript 3, if the specified string is empty, returns 0. 4, if you need to target a string is empty, returns 1 5, two string length should not exceed 50000 6, according to the above results, 7, in the string search, the fastest way to move the pointer from the beginning of the string, according to the pointer offset and the length of the search string, cut the string to compare whether it is equal, if equal directly return the pointer corresponding to the subscriptCopy the codeSwift sample code
class Solution { func strStr(_ haystack: String, _ needle: String) -> Int { if needle.lengthOfBytes(using: String.Encoding.utf8) == 0 { return 0 } if haystack.lengthOfBytes(using: String.Encoding.utf8) == 0 { return -1 } if haystack.lengthOfBytes(using: String.Encoding.utf8) > 5*10000 { return -1 } if needle.lengthOfBytes(using: String.Encoding.utf8) > 5*10000 { return -1 } if needle.lengthOfBytes(using: String.Encoding.utf8) == haystack.lengthOfBytes(using: String.Encoding.utf8) { if needle == haystack { return 0 }else{ return -1 } } var fast = 0 while fast < haystack.lengthOfBytes(using: String.Encoding.utf8) { if (fast + needle.lengthOfBytes(using: String.Encoding.utf8)) <= haystack.lengthOfBytes(using: String.Encoding.utf8) { let starIndex = haystack.index(haystack.startIndex,offsetBy: fast) let endIndex = haystack.index(haystack.startIndex,offsetBy: fast+needle.lengthOfBytes(using: String.Encoding.utf8)-1) let str = haystack[starIndex...endIndex] if str == needle { return fast } } fast += 1 } return 1}}Copy the codeGiven a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order. You can assume that there are no duplicate elements in the array.
solution
1, first determine the array is through sorting, so only need to traverse a can determine if there is any, if no should be in which position 2, when we traversal, to determine whether equal, to determine whether to include, and then determine whether traversal whether the current value is greater than the given value, if more than, that does not contain a given value in the array, If the array is not found, the given value is larger than any other value in the array, so we add it to the end of the array with the subscript being the length of the arrayCopy the codeSwift sample code
class Solution {
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
if nums.count == 0 {
return 0
}
var fast = 0
while fast < nums.count {
if nums[fast] == target {
return fast
}
if nums[fast] > target {
return fast
}
fast += 1
}
return nums.count
}
}
Copy the codeGiven a positive integer n, print the NTH term of the appearance sequence. An “appearance sequence” is a sequence of integers, starting with the number 1, and each item in the sequence is a description of the previous item. You can think of it as a sequence of numeric strings defined by a recursive formula:
CountAndSay (1) = "1" countAndSay(n) is a description of countAndSay(n-1), which is then converted to another numeric string.Copy the codeThe first five are as follows:
1. 1, 2. 11, 3. 21, 4. 1211, 5. 111221 The first term is the number 1 that describes the previous term, and this number is 1, "one 1", which is called "11", which describes the previous term, and this number is 11, which is called "21", which describes the previous term, So this number right here is 21 which is "one 2 + one 1", let's call it "1211" to describe the previous term, this number right here is 1211 which is" one 1 + one 2 + two 1s ", let's call it "111221".Copy the codeTo describe a numeric string, you first split the string into a minimum number of groups, each consisting of at most consecutive identical characters. Then for each group, the number of characters is described first, and then the characters are described, forming a description group. To convert the description to a numeric string, replace the number of characters in each group with a number, and then concatenate all the description groups.
For example, the numeric string “3322251” is described as follows:
solution
1, first of all to understand the question, according to the incoming integer, do look queue, namely (integer control cycles, each cycle a string description of starting from 1) 2, understand the question, in the outer loop, the loop with the given integer control 3, inner loop using a string of record every cycle after the end of the description, 4. Cycle until the boundary is reachedCopy the codeSwift sample code
class Solution { func countAndSay(_ n: Int) -> String { if n == 1 { return "1" } if n == 0 { return "" } var val = 1; var str = "1"; while val < n { let tmp = str var tmpRes = "" var count = 0 var ch:Character = "A" for char in tmp { if ch == "A" { ch = char } if char == ch { count += 1 }else{ tmpRes += String(count)+String(ch) ch = char count = 1 } } tmpRes += String(count)+String(ch) str = tmpRes val += 1 } return String(str) } }Copy the codeGiven an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
solution
1, the array is not ordered, and there are positive and negative integers, there is no limit to the length of the array 2, first filter whether the elements meet the condition 3, by moving the Pointers on both sides of the array, then add the elements in the range, take the maximum outputCopy the codeSwift sample code
class Solution { func maxSubArray(_ nums: [Int]) -> Int { if nums.count == 1 { return nums[0] } if nums.count == 0 { return 0 } if nums.count > 30000 { return 0 } var sum = -100000 for i in 0.. <nums.count { if nums[i] > 100000 || nums[i] < -100000 { return 0 } var j = nums.count-1 var tmpSum = 0 while j >= i { for index in i... j { tmpSum += nums[index] if tmpSum > sum { sum = tmpSum } j -= 1 } } } return sum } }Copy the codeYou are given a string s consisting of several words separated by Spaces. Returns the length of the last word in the string. If the last word does not exist, return 0. A word is the largest substring that consists only of letters and does not contain any space characters.
solution
1, according to the question, a string containing only Spaces as well as the English letters, so don't need to filter 2, to determine whether a string is empty, if null returns 0 3, directly determine whether the string all Spaces, if it is, returns 0. 4, the string with a space for cutting, legal string into an array, the array contains at least one element, Get the last element and return its lengthCopy the codeSwift sample code
class Solution {
func lengthOfLastWord(_ s: String) -> Int {
let arr = s.split(separator: " ")
if arr.count == 1 {
return arr[0].lengthOfBytes(using: String.Encoding.utf8)
}
if arr.count == 0 {
return 0
}
if s.lengthOfBytes(using: String.Encoding.utf8) > 10000 {
return 0
}
return arr[arr.count-1].lengthOfBytes(using: String.Encoding.utf8)
}
}
Copy the code16. Given a non-negative integer represented by a non-empty array of integers, add one to the number. The highest digit is stored at the beginning of an array, where each element stores only a single digit. You can assume that this integer does not start with zero, except for the integer 0.
solution
2. Array represents a complete integer. 3Copy the codeSwift sample code
class Solution { func plusOne(_ digits: [Int]) -> [Int] { if digits.count > 100 { return [] } var sum = "" for index in 0.. <digits.count { if digits[index] > 10 { return [] } sum += String(digits[index]) } var last = sum.removeLast() var addStr = "" while Int(String(last))! == 9 { addStr += "0" if sum.lengthOfBytes(using: String.Encoding.utf8) > 0 { last = sum.removeLast() }else{ last = "0" } } sum += String(Int(String(last))! +1) + addStr let arr:NSMutableArray = NSMutableArray() last = sum.removeFirst() while sum.lengthOfBytes(using: String.Encoding.utf8) > 0 { arr.add(Int(String(last))!) last = sum.removeFirst() } arr.add(Int(String(last))!) return arr as! [Int] } }Copy the codeGiven two binary strings, return their sum (in binary). The input is a non-empty string containing only the digits 1 and 0.
solution
1, because the given is a binary string, there will be no 0 at the beginning of the string, and it is a non-empty string, so we only need to determine the longest string 2, according to the longest string, determine whether to advance 1Copy the codeSwift sample code
class Solution { func addBinary(_ a: String, _ b: String) -> String { if a.lengthOfBytes(using: String.Encoding.utf8) > 10000 || b.lengthOfBytes(using: String.Encoding.utf8) > 10000 { return "" } if a.lengthOfBytes(using: String.Encoding.utf8) == 0 { return b } if b.lengthOfBytes(using: String.Encoding.utf8) == 0 { return a } var leftVal = a var rightVal = b var isAdd = false var res = "" var count = 0 if rightVal.lengthOfBytes(using: String.Encoding.utf8) > leftVal.lengthOfBytes(using: String.Encoding.utf8) { while (count < b.lengthOfBytes(using: String.Encoding.utf8)) { if leftVal.lengthOfBytes(using: String.Encoding.utf8) > 0 { let tmp = Int(String(rightVal.removeLast()))! +Int(String(leftVal.removeLast()))! var needAdd = tmp > 1 ? Zero: tmp if tmp > 1 { if isAdd { needAdd += 1 } isAdd = true }else{ if isAdd { needAdd += 1 } isAdd = needAdd > 1 } res = String(needAdd > 1 ? 0 : needAdd) + res }else{ let tmp = Int(String(rightVal.removeLast()))! var needAdd = tmp > 1 ? Zero: tmp if tmp > 1 { if isAdd { needAdd += 1 } isAdd = true }else{ if isAdd { needAdd += 1 } isAdd = needAdd > 1 } res = String(needAdd > 1 ? 0 : needAdd) + res } count += 1 } }else{ while (count < a.lengthOfBytes(using: String.Encoding.utf8)) { if rightVal.lengthOfBytes(using: String.Encoding.utf8) > 0 { let tmp = Int(String(rightVal.removeLast()))! +Int(String(leftVal.removeLast()))! var needAdd = tmp > 1 ? Zero: tmp if tmp > 1 { if isAdd { needAdd += 1 } isAdd = true }else{ if isAdd { needAdd += 1 } isAdd = needAdd > 1 } res = String(needAdd > 1 ? 0 : needAdd) + res }else{ let tmp = Int(String(leftVal.removeLast()))! var needAdd = tmp > 1 ? Zero: tmp if tmp > 1 { if isAdd { needAdd += 1 } isAdd = true }else{ if isAdd { needAdd += 1 } isAdd = needAdd > 1 } res = String(needAdd > 1 ? 0 : needAdd) + res } count += 1 } } if isAdd { res = "1" + res } return res } }Copy the codeInt SQRT (int x) Calculates and returns the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.
solution
1, realize manual square root, need to understand the general principle of square root, the first thought is binary search, followed by backstepping method, etc. 2, using a binary search, first determine the minimum and maximum values, because is negative, so the minimum value is 0, the maximum value is the square root of 3 number within itself, through continuous circulation modify the minimum and maximum values, narrow range, Reduced search scopeCopy the codeSwift sample code
class Solution {
func mySqrt(_ x: Int) -> Int {
var l = 0
var r = x
var ans = -1
while l <= r {
let mid = l + (r - l)/2
if mid*mid <= x {
ans = mid
l = mid + 1
}else{
r = mid - 1
}
}
return ans
}
}
Copy the code19. Suppose you are climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? Note: given n is a positive integer.
solution
1. Use dynamic programming to calculate how many ways to arrive at each step. 2. When calculating how many ways to take the current step, it is necessary to determine the way to take the first step and the first two stepsCopy the codeSwift sample code
class Solution { func climbStairs(_ n: Int) -> Int { var p = 0,q = 0,r = 1 for _ in 0.. <n { p = q q = r r = p + q } return r } }Copy the codeDelete all duplicate elements so that each element appears only once. Returns a linked list of results, also in ascending order.
solution
1. Because the linked list is sorted, only the same adjacent nodes need to be deleted. 2. Every time you enter the linked list, check whether there is a child node firstCopy the codeSwift sample code
public class ListNode { public var val:Int public var next:ListNode? public init(){ self.val = 0 self.next = nil } public init(_ val:Int){ self.val = val self.next = nil } public init(_ val:Int, _ next:ListNode?) { self.val = val self.next = next } } class Solution { func deleteDuplicates(_ head: ListNode?) -> ListNode? { if head == nil { return nil } if head? .next == nil { return head } var node = head if node? .val == node? .next? .val { node = deleteDuplicates(node? .next) }else{ node? .next = deleteDuplicates(node? .next) } return node } func createListNode(_ arr:[Int]) -> ListNode { let node = ListNode() if arr.count == 1 { node.val = arr[0] } if arr.count > 1 { var tmpArr = arr node.val = arr[0] tmpArr.remove(at: 0) node.next = createListNode(tmpArr) } return node } }Copy the codeMerge nums2 into nums1 to make nums1 an ordered array. Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.
solution
1, first of all to determine two arrays is ordered, so we only need to take data from the second array head start, insert the first array, the corresponding position, and then insert the contrast from the last insert position next time a began to compare 2, after the last longer every time insert data will lead to an array, so from an array to remove the lastCopy the codeSwift sample code
class Solution { func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) { if m+n ! = nums1.count { return } if nums2.count ! = n { return } if m == 0 { nums1 = nums2 return } var allVal = m var index = 0 for item in nums2 { for i in index.. <nums1.count { if item <= nums1[i] { nums1.insert(item, at: i) index = i + 1 allVal += 1 break }else{ if item >= nums1[i] && nums1[i] == 0 { if i >= allVal { nums1.insert(item, at: i) index = i + 1 allVal += 1 break } } } } if nums1.count > m + n { nums1.removeLast() } } } }Copy the codeSparse array search. Given an sorted array of strings scattered with empty strings, write a method to find the position of a given string.
solution
If an array is an array, check whether the specified element exists in the arrayCopy the codeSwift sample code
class Solution { func findString(_ words: [String], _ s: String) -> Int { if words.count == 0 { return -1 } if words.count > 1000000 { return -1 } for i in 0.. <words.count { if words[i] == s { return i } } return -1 } }Copy the codeDesign an algorithm to calculate how many trailing zeros n factorial has.
solution
1, through multiplication concludes with 0, is 0, (2 * 5) will be 2, because the factorial starting from 1 multiplicative, so eliminate 0, then only 2 and 5 0 3, so we only need to determine whether a given number is multiples of 5, a few times, can be divided exactly by 5 can determine how many letters are there in the mantissa 0Copy the codeSwift sample code
class Solution {
func trailingZeroes(_ n: Int) -> Int {
if n == 0 {
return 0
}
var val:Int = n
var cnt = 0
while val > 0 {
val /= 5
cnt += val
}
return cnt
}
}
Copy the codeWrite a method to find the largest of two numbers A and b. If-else or other comparison operators must not be used.
solution
2. If you move 63 places to the right, you will get the sign place. Note that the negative sign remains unchanged, so if you move 63 places to the right of a positive number, you will get 0, and if you move 63 places to the right of a negative number, you will get -1 3. K = 0, that is, a > b, so our calculation formula is 1 * a-b * 0 = a, when res < 0, k = -1, that is, b > a, so our calculation formula is 0 * a-b * (-1) = bCopy the codeSwift sample code
class Solution {
func maximum(_ a: Int, _ b: Int) -> Int {
let res = a - b
let k = res >> 63
return (1+k)*a - b*k
}
}
Copy the codeYou are building a diving board out of a pile of wooden boards. There are two types of boards, with shorter boards and longer boards. You have to use exactly k boards. Write a method that generates all possible lengths for a diving board. The returned length needs to be sorted from smallest to largest.
solution
1. Because the number of boards required is fixed, it is only necessary to determine how many short boards there are in each long board. 2Copy the codeSwift sample code
class Solution {
func divingBoard(_ shorter: Int, _ longer: Int, _ k: Int) -> [Int] {
if k <= 0 || k > 100000 {
return []
}
if shorter <= 0 || shorter > longer {
return []
}
if longer <= 0 || longer < shorter {
return []
}
if shorter == longer {
return [k*shorter]
}
let arr:NSMutableArray = NSMutableArray()
var val:Int = 0
while val<=k {
arr.add(val*longer+(k-val)*shorter)
val += 1
}
return arr as! [Int]
}
}
Copy the codeThe game of Master Mind is played as follows. The computer has four slots, each containing a ball, which may be red (R), yellow (Y), green (G), or blue (B). For example, a computer might have four RGGBS (slot 1 is red, slot 2 and 3 are green, and slot 4 is blue). As a user, you’re trying to guess the color combination. For example, you might guess YRGB. If one guesses the color of a slot correctly, it counts as a “guess”; If you guessed only the colors correctly but got the slot wrong, it was a “false guess.” Note that “correct guess” does not count as “false guess”. Given a color combination solution and a guess, write a method to return answer of the number of guesses and false guesses, where answer[0] is the number of guesses and answer[1] is the number of false guesses.
solution
1, first of all, to several, guess the only card slot and color are all the same, so use a for loop, take the value of the same position, if the same is right, count plus one 2, judgment, pseudo guess the number of times, the first to use two loops, the outer loop is the right value, the inner loop is the user's guess, If the user guesses correctly in each cycle, the guessing value will be deleted and the number of false guesses will be increased by one until the cycle is completed. 3. Since the second step of false guesses contains the number of correct guesses, the number of false guesses can be obtained directly by subtraction operationCopy the codeSwift sample code
class Solution { func masterMind(_ solution: String, _ guess: String) -> [Int] { if solution.lengthOfBytes(using: String.Encoding.utf8) ! = guess.lengthOfBytes(using: String.Encoding.utf8) { return [] } var right = 0 var allow = 0 var s = solution var g = guess for _ in 0.. <s.lengthOfBytes(using: String.Encoding.utf8) { let tmpS = s.removeFirst() let tmpG = g.removeFirst() if String(tmpS) == String(tmpG) { right += 1 } } s = solution g = guess for item in s { var cnt = 0 for char in g { if String(item) == String(char) { allow += 1 let star = g.index(g.startIndex, offsetBy: cnt) g.remove(at: star) break } cnt += 1 } } return [right,allow-right] } }Copy the code27. A student is learning fractions. He needs to reduce a continued fraction to the simplest fraction. Can you help him?
A continued fraction is a fraction of the form shown above. In this case, all coefficients are integers greater than or equal to 0. The input cont represents the coefficient of the continued fraction (cont[0] represents A0 in the figure above, and so on). Return an array of length 2 [n, m] such that the continued fraction is equal to n/m, and the greatest common divisor of n and m is 1.
solution
1, the simplest fraction, every time there is a rule, the NTH calculation is the NTH +1 calculation of the denominator multiplied by n+ numerator, as the denominator, the denominator as the numerator 2, evaluate the numerator each time according to the above rule, and then set the last calculation of the denominatorCopy the codeC Sample code
int* fraction(int* cont, int contSize, int* returnSize){ *returnSize = 2; int temp,m=1,n = cont[contSize-1]; for(int i = contSize-1; i>0; i--){ temp = m; m = n; n=temp; n = cont[i-1]*m+n; } int* ret = (int *)malloc(sizeof(int) * 2); ret[0]=n; ret[1]=m; return ret; }Copy the codeGiven two sorted arrays A and B, the end of A has enough buffer space to hold B. Write A method that merges B into A and sorts. Initialize A and B with m and N elements, respectively.
solution
1, because it is already sorted two arrays, so only need to get the first value from the second array, and then in the first array insert, insert, when need to decide the position of the insert 0, whether it is valid, if they are valid values, move the cursor back, if not directly replace 2, judgment, in turn, Insert the value from the second array into the first array. Each time you determine the position in the first array, you only need to start judging by the position of the last index inserted plus oneCopy the codeSwift sample code
class Solution { func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) { if m+n ! = nums1.count { return } if nums2.count ! = n { return } if m == 0 { nums1 = nums2 return } var allVal = m var index = 0 for item in nums2 { for i in index.. <nums1.count { if item <= nums1[i] { nums1.insert(item, at: i) index = i + 1 allVal += 1 break }else{ if item >= nums1[i] && nums1[i] == 0 { if i >= allVal { nums1.insert(item, at: i) index = i + 1 allVal += 1 break } } } } if nums1.count > m + n { nums1.removeLast() } } } }Copy the code29. There are n stacks of coins on the table. The amount of each stack is stored in the array Coins. We can choose any pile at a time, take one or two of the coins, and find the minimum number of times to use up the strong deduction.
solution
1, because is the minimum number of times, so every time we according to the maximum values to take, you can get at least 2 times, no matter how much a pile with every time we get two, if after the heap value greater than 0, and can also get, until not greater than zero, representative after we take 2, this pile of just take over or less than two, After taking less than 0 3, every time as long as meet the pile of force deduction coin is greater than 0, then the number of times plus 1, and then the number minus 2Copy the codeSwift sample code
class Solution {
func minCount(_ coins: [Int]) -> Int {
var cnt = 0;
for item in coins {
var tmp = item
while tmp > 0 {
cnt += 1;
tmp -= 2
}
}
return cnt
}
}
Copy the codeSmall button found a quick calculation robot in the autumn market. The shopkeeper says two numbers to the robot (x and Y) and asks xiaokou to say the calculation instructions:
1, “A” operation: make x = 2 * x + y;
2, “B” operation: make y = 2 * y + x.
In this game, the numbers spoken by the shopkeeper are X = 1 and Y = 0, and the calculation instructions spoken by xiaokou are recorded as the string S composed of only capital letters A and B. The order of characters in the string indicates the calculation order. Please return the final sum of X and Y.
solution
1, because the string needs to be evaluated from beginning to end, we need to iterate over each string to evaluate. 2, because when A or B, the calculation formula is fixed, so we only need to evaluate the specified formula according to the characterCopy the codeSwift sample code
class Solution {
func calculate(_ s: String) -> Int {
var x = 1;
var y = 0;
var tmpS = s
while tmpS.lengthOfBytes(using: String.Encoding.utf8) > 0 {
if String(tmpS.removeFirst()) == "A" {
x = 2 * x + y
}else{
y = 2 * y + x
}
}
return x + y
}
}
Copy the code