最近看看Leetcode只有swift，沒有OC的運行環(huán)境萨驶，最近時間比較富裕，出一篇OC的leetcode章節(jié)艇肴，希望救iOS于水火腔呜，或者把iOS推入水火。
#pragma --mark? 兩數(shù)之和--簡單 /**
?輸入：nums = [2,7,11,15], target = 9? ?輸出：[0,1]
?輸入：nums = [3,2,4], target = 6? 輸出：[1,2]
?輸入：nums = [3,3], target = 6? ?輸出：[0,1]
?鏈接：https://leetcode-cn.com/problems/two-sum
?*/
//O(n*n)? 暴力的一般方法
-(NSArray*)twoSum:(NSArray*)numstarget:(int)target{
? ? //篩選
? ? if(nums ==nil|| nums.count== 0){
? ? ? ? return@[];
? ? }else{
? ? ? ? intfirstIndex = 0;
? ? ? ? intlastIndex = 0;
? ? ? ? for(inti = 0 ; i< nums.count-1 ; i++){
? ? ? ? ? ? for(intj=i+1 ; j
? ? ? ? ? ? ? ? if(target == [nums[i]intValue] + [nums[j]intValue]){
? ? ? ? ? ? ? ? ? ? firstIndex = i ;
? ? ? ? ? ? ? ? ? ? lastIndex = j;
? ? ? ? ? ? ? ? ? ? break;//找到結(jié)果break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return@[@(firstIndex),@(lastIndex)];
? ? }
}
暴力解法就是直來直去再悼。
//O(n) 一般方法
-(NSArray*)twoSum1:(NSArray*)numstarget:(int)target{
? ? if(nums ==nil|| nums.count== 0){
? ? ? ? return@[];
? ? }else{
? ? ? ? intfirstIndex = 0;
? ? ? ? intlastIndex = 0;
? ? ? ? intlen = (int)nums.count;
? ? ? ? NSMutableDictionary *dict = [NSMutableDictionary dictionary];
? ? ? ? for(inti = 0 ; i< len ; i++){
? ? ? ? ? ? intanother = target - [nums[i]intValue];
? ? ? ? ? ? if([dict.allValuescontainsObject:@(another)]){
? ? ? ? ? ? ? ? NSArray*resultArray = [dictallKeysForObject:@(another)];
? ? ? ? ? ? ? ? firstIndex? = [resultArray[0]intValue];
? ? ? ? ? ? ? ? lastIndex = i;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? [dictsetObject:@(another)forKey:[NSStringstringWithFormat:@"%d",i]];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return@[@(firstIndex),@(lastIndex)];
? ? }
}
所謂的算法優(yōu)化核畴，就是犧牲空間來降低時間復(fù)雜度， 這里采用了可變字典冲九，用于做O(1)的查找谤草。?
#pragma --mark兩數(shù)相加-中等
?輸入：l1 = [2,4,3], l2 = [5,6,4] 輸出：[7,0,8]
?輸入：l1 = [0], l2 = [0]? ? 輸出：[0]
?輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]? ?輸出：[8,9,9,9,0,0,0,1]
?O(n)
?鏈接：https://leetcode-cn.com/problems/add-two-numbers
?*/
這個在擼碼之前，要在iOS端先定義好ListNode 數(shù)據(jù)結(jié)構(gòu)
//定義單鏈表
@interface ListNode : NSObject
@property (nonatomic ,assign) int val;
@property (nonatomic ,strong) ListNode * next;
-(instancetype)init;
-(instancetype)initWithVal:(int)val;
-(instancetype)initWithVal:(int)valnext:(ListNode*)next;
-(void)appendListNode:(ListNode *)node;
@end
@implementation ListNode
-(instancetype)init{
? ? self= [superinit];
? ? if(self){
? ? }
? ? return self;
}
-(instancetype)initWithVal:(int)val{
? ? self= [superinit];
? ? if(self){
? ? ? ? [self configNodeWithVal:val next:nil];
? ? }
? ? return self;
}
-(instancetype)initWithVal:(int)valnext:(ListNode*)next{
? ? self= [superinit];
? ? if(self){
? ? ? ? [selfconfigNodeWithVal:valnext:next];
? ? }
? ? return self;
}
-(void)configNodeWithVal:(int)val next:(ListNode *)next{
? ? self.val= val;
? ? self.next= next;
}
-(void)appendListNode:(ListNode *)node{
? ? self.next= node;
}
@end
-(ListNode *)addTwoNumbersWithL1:(ListNode *)l1 L2:(ListNode *)l2{
? ? ListNode *result = [[ListNode alloc]initWithVal:0 next:nil];
? ? ListNode*head = result;//temp 不能更改result指向
? ? intpreIndex = 0;
? ? while(l1 !=NULL || l2 !=NULL) {
? ? ? ? intsum? = l1.val+ l2.val+ preIndex;
? ? ? ? intshowValue = sum%10;
? ? ? ? ListNode*currentNode = [[ListNodealloc]initWithVal:showValue];
? ? ? ? preIndex = sum/10;
? ? ? ? head.next= currentNode;
? ? ? ? head = currentNode;
? ? ? ? if(l1!=NULL){
? ? ? ? ? ? l1 = l1.next;
? ? ? ? }
? ? ? ? if(l2 !=NULL){
? ? ? ? ? ? l2 = l2.next;
? ? ? ? }
? ? }
? ? returnresult.next;
}
思路：就是利用常規(guī)加法規(guī)則，設(shè)置好進(jìn)位的臨時變量咖刃，還有head變量泳炉，然后就是鏈表基本操作和遍歷
#pragma --mark? 無重復(fù)字符的最長子串? -- 中等
/**
?給定一個字符串 s ，請你找出其中不含有重復(fù)字符的?最長子串?的長度嚎杨。
?輸入: s = "abcabcbb"? ? 輸出: 3
?輸入: s = "bbbbb"? ?輸出: 1
?輸入: s = "pwwkew"? ?輸出: 3
?提示：
?0 <= s.length <= 5 * 104
?s?由英文字母花鹅、數(shù)字、符號和空格組成
?來源：力扣（LeetCode）
?鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
?*/
-(int)lengthOfLongestSubstring:(NSString *)s{
? ? if(s.length==0){
? ? ? ? return0;
? ? }else{
? ? ? ? intfast = 1;
? ? ? ? intslow = 0;
? ? ? ? intresult = 0;
? ? ? ? NSMutableArray *resultArray = [NSMutableArray array]; //用于保存結(jié)果
? ? ? ? NSString*resultstring = [s substringWithRange:NSMakeRange(0, 1)];//自增的結(jié)果串
? ? ? ? while(fast < s.length) {
? ? ? ? ? ? NSString*fastStr? = [s substringWithRange:NSMakeRange(fast, 1)];//快指針的char
? ? ? ? ? ? if([resultstring containsString:fastStr]){
? ? ? ? ? ? ? ? [resultArray addObject:resultstring];? //加入數(shù)組
? ? ? ? ? ? ? ? NSRange replaceRange = [resultstring rangeOfString:fastStr];//自增串出現(xiàn)重復(fù)的index
? ? ? ? ? ? ? ? int replaceIndex = (int)replaceRange.location;
? ? ? ? ? ? ? ? slow = slow + replaceIndex+1;
? ? ? ? ? ? ? ? resultstring = [s substringWithRange:NSMakeRange(slow, fast-slow+1)];//更新自增串? //Range (loca,len)
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? resultstring = [NSString stringWithFormat:@"%@%@",resultstring,fastStr];? ////更新自增串
? ? ? ? ? ? }
? ? ? ? ? ? fast++;
? ? ? ? }
//這里我保存了字符串結(jié)果枫浙， 這里可以直接記錄長度 刨肃，我這里采用了數(shù)組
? ? ? ? if(resultstring.length> 0){
? ? ? ? ? ? [resultArray addObject:resultstring];
? ? ? ? ? ? for(NSString*item in resultArray){
? ? ? ? ? ? ? ? result = item.length> result ? (int)item.length: result;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return result;
? ? }
}
時間負(fù)責(zé)度為0(n*n) ，我這個算法運用到快慢指針箩帚，
題目鏈接：https://leetcode-cn.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/
每日一題：
主要難點在理解題干真友，看了幾遍從三元橋想到海淀黃莊。紧帕。盔然。
1.只能操作相鄰都是相同元素，比如AAA組合的中間A是嗜。（導(dǎo)致如果AB組合被大亂掉相當(dāng)于是多余元素）愈案。
2.不能操作兩端的的元素（元素的）就是對三個以上相鄰 元素的補充。
3.輸贏問題就轉(zhuǎn)換成了鹅搪，找到A站绪，B各自三個相同排列的組合出現(xiàn)的次數(shù)，并且參與次數(shù)比較丽柿。（次數(shù)相同恢准，先手的輸，即Alice false）;
oc代碼：
-(BOOL)WhoWinsTheGame:(NSString*)gameString{
? ? BOOL flag =false;
? ? if(gameString.length<= 2){
? ? ? ? return flag;
? ? }else{
? ? ? ? intAtime = 0;//A可執(zhí)行次數(shù)
? ? ? ? intBtime = 0;//B可執(zhí)行次數(shù)
? ? ? ? //快慢指針
? ? ? ? intfast = 1;
? ? ? ? intslow = 0;
? ? ? ? while(fast < gameString.length){
? ? ? ? ? ? charfastChar = [gameString characterAtIndex:fast];
? ? ? ? ? ? charslowChar = [gameString characterAtIndex:slow];
? ? ? ? ? ? if(slowChar == fastChar){
? ? ? ? ? ? ? ? if(fast - slow >=2){//下標(biāo)標(biāo)記 如果是超過2證明有三個連續(xù)字符
? ? ? ? ? ? ? ? ? ? if(fastChar == 'A'){
? ? ? ? ? ? ? ? ? ? ? ? Atime++;
? ? ? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? ? ? Btime++;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? fast++;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? slow = fast;
? ? ? ? ? ? ? ? fast ++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(Atime > Btime){? //相等是先手的輸
? ? ? ? ? ? flag =true;
? ? ? ? }
? ? ? ? return flag;
? ? }
}
時間復(fù)雜度 O(n) , n是輸入字符串長度?
