最近看看Leetcode只有swift，没有OC的运行环境，最近时间比较富裕，出一篇OC的leetcode章节，希望救iOS于水火，或者把iOS推入水火。
#pragma --mark 两数之和--简单 /**
输入：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;//找到结果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)];
}
}
所谓的算法优化，就是牺牲空间来降低时间复杂度， 这里采用了可变字典，用于做O(1)的查找。
#pragma --mark两数相加-中等
输入：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 数据结构
//定义单链表
@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;
}
思路：就是利用常规加法规则，设置好进位的临时变量，还有head变量，然后就是链表基本操作和遍历
#pragma --mark 无重复字符的最长子串 -- 中等
/**
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb" 输出: 3
输入: s = "bbbbb" 输出: 1
输入: s = "pwwkew" 输出: 3
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源：力扣（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]; //用于保存结果
NSString*resultstring = [s substringWithRange:NSMakeRange(0, 1)];//自增的结果串
while(fast < s.length) {
NSString*fastStr = [s substringWithRange:NSMakeRange(fast, 1)];//快指针的char
if([resultstring containsString:fastStr]){
[resultArray addObject:resultstring]; //加入数组
NSRange replaceRange = [resultstring rangeOfString:fastStr];//自增串出现重复的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++;
}
//这里我保存了字符串结果， 这里可以直接记录长度 ，我这里采用了数组
if(resultstring.length> 0){
[resultArray addObject:resultstring];
for(NSString*item in resultArray){
result = item.length> result ? (int)item.length: result;
}
}
return result;
}
}
时间负责度为0(n*n) ，我这个算法运用到快慢指针，
题目链接：https://leetcode-cn.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/
每日一题：
主要难点在理解题干，看了几遍从三元桥想到海淀黄庄。。。
1.只能操作相邻都是相同元素，比如AAA组合的中间A。（导致如果AB组合被大乱掉相当于是多余元素）。
2.不能操作两端的的元素（元素的）就是对三个以上相邻 元素的补充。
3.输赢问题就转换成了，找到A，B各自三个相同排列的组合出现的次数，并且参与次数比较。（次数相同，先手的输，即Alice false）;
oc代码：
-(BOOL)WhoWinsTheGame:(NSString*)gameString{
BOOL flag =false;
if(gameString.length<= 2){
return flag;
}else{
intAtime = 0;//A可执行次数
intBtime = 0;//B可执行次数
//快慢指针
intfast = 1;
intslow = 0;
while(fast < gameString.length){
charfastChar = [gameString characterAtIndex:fast];
charslowChar = [gameString characterAtIndex:slow];
if(slowChar == fastChar){
if(fast - slow >=2){//下标标记 如果是超过2证明有三个连续字符
if(fastChar == 'A'){
Atime++;
}else{
Btime++;
}
}
fast++;
}else{
slow = fast;
fast ++;
}
}
if(Atime > Btime){ //相等是先手的输
flag =true;
}
return flag;
}
}
时间复杂度 O(n) , n是输入字符串长度
