- 11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
- 12. 矩陣中的路徑
- 13. 機(jī)器人的運(yùn)動(dòng)范圍
- 14. 剪繩子
- 15. 二進(jìn)制中 1 的個(gè)數(shù)
- 16. 數(shù)值的整數(shù)次方
- 17. 打印從 1 到最大的 n 位數(shù)
- 18.1 在 O(1) 時(shí)間內(nèi)刪除鏈表節(jié)點(diǎn)
- 18.2 刪除鏈表中重復(fù)的結(jié)點(diǎn)
- 19. 正則表達(dá)式匹配
- 20. 表示數(shù)值的字符串
閱前需知
1.本文部分內(nèi)容參考劍指 offer 題解，如有侵權(quán)，請告知。其他內(nèi)容均屬原創(chuàng)，轉(zhuǎn)載請告知。
2.本文示例代碼中給一些類增加了一些類擴(kuò)展，因篇幅原因，未在文中寫出，詳情見項(xiàng)目源碼，地址文末有提供。
3.閱讀本文之前需要先了解節(jié)點(diǎn),鏈表,棧,二叉樹的實(shí)現(xiàn)。詳情見如下文章連接。
4.因?yàn)?OC 中沒有棧，鏈表節(jié)點(diǎn)，鏈表的概念，所以本項(xiàng)目自定義了棧，鏈表節(jié)點(diǎn)，鏈表類。
5.因技術(shù)水平有限，如有錯(cuò)誤，歡迎指正。
以下是通過 OC 語法實(shí)現(xiàn)
11.旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。
例如數(shù)組 {3, 4, 5, 1, 2} 為 {1, 2, 3, 4, 5} 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為 1。
解題思路
在一個(gè)有序數(shù)組中查找一個(gè)元素可以用二分查找，二分查找也稱為折半查找，每次都能將查找區(qū)間減半，這種折半特性的算法時(shí)間復(fù)雜度都為 O(logN)。
本題可以修改二分查找算法進(jìn)行求解：
- 當(dāng) nums[m] <= nums[h] 的情況下，說明解在 [l, m] 之間，此時(shí)令 h = m；
- 否則解在 [m + 1, h] 之間，令 l = m + 1。
詳細(xì)代碼如下
/** 折半查找最小值 */
+ (int)minNumberInRotateArray:(NSArray *)nums {
if (nums.count == 0) {
return 0;
}
int l = 0, h = (int)nums.count - 1;
while (l < h) {
int m = l + (h - l) / 2; // 中間值
if ([nums[m] intValue] <= [nums[h] intValue]) {
h = m;
} else {
l = m + 1;
}
}
return [nums[l] intValue];
}
測試案例代碼
// 11.1 折半查詢
- (void)minNumberInRotateArray {
int number = [MinNumberInRotateArray minNumberInRotateArray:@[@1,@4,@8,@11,@20]];
NSLog(@"number = %d",number);
}
運(yùn)行結(jié)果
11.1折半查找.png
11.2 重復(fù)數(shù)字
如果數(shù)組元素允許重復(fù)的話，那么就會(huì)出現(xiàn)一個(gè)特殊的情況：nums[l] == nums[m] == nums[h]，那么此時(shí)無法確定解在哪個(gè)區(qū)間，需要切換到順序查找。例如對于數(shù)組 {1,1,1,0,1}，l、m 和 h 指向的數(shù)都為 1，此時(shí)無法知道最小數(shù)字 0 在哪個(gè)區(qū)間。
詳細(xì)代碼如下
+ (int)minNumberInRotateArray2:(NSArray *)nums {
if (nums.count == 0) {
return 0;
}
int l = 0, h = (int)nums.count - 1;
while (l < h) {
int m = l + (h - l) / 2; // 中間值
if (nums[l] == nums[m] && nums[m] == nums[h]) { // 三者相等
return [self minNumber:nums l:l h:h];
} else if ([nums[m] intValue] <= [nums[h] intValue]) {
h = m;
} else {
l = m + 1;
}
}
return [nums[l] intValue];
}
+ (int)minNumber:(NSArray *)nums l:(int)l h:(int)h {
for (int i = l; i < h; i++) {
if ([nums[i] intValue] > [nums[i + 1] intValue]) {
return [nums[i + 1] intValue];
}
}
return [nums[l] intValue];
}
測試案例代碼
// 11.2 折半查詢
- (void)minNumberInRotateArray2 {
int number = [MinNumberInRotateArray minNumberInRotateArray2:@[@3,@4,@2,@1,@3]];
NSLog(@"number = %d",number);
}
運(yùn)行結(jié)果
image.png
12.矩陣中的路徑
題目描述
請?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過了矩陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子。
例如下面的矩陣包含了一條 bfce 路徑。
路徑圖.png
詳細(xì)代碼如下
- MatrixHasPath.h
/**
矩陣中的路徑
*/
@interface MatrixHasPath : NSObject
- (BOOL)hasPath:(NSString *)oriStr rows:(int)rows cols:(int)cols str:(NSString *)str;
@end
- MatrixHasPath.m
@implementation MatrixHasPath {
NSArray *_next;
int _rows;
int _cols;
}
- (instancetype)init {
self = [super init];
if (self) {
// 上 下 左 右 四個(gè)方向
_next = @[@[@0,@(-1)],@[@0,@1],@[@(-1),@0],@[@1,@0]];
}
return self;
}
- (BOOL)hasPath:(NSString *)oriStr rows:(int)rows cols:(int)cols str:(NSString *)str {
if (rows == 0 || cols == 0) {
return NO;
}
_rows = rows;
_cols = cols;
// 1.先構(gòu)造一個(gè)二維數(shù)組,數(shù)值都填充為0,表示沒有遍歷過
NSMutableArray *marked = [NSMutableArray array];
for (int i = 0; i < _rows; i++) {
NSMutableArray *firstArrM = [NSMutableArray array];
for (int j = 0; j < _cols; j++) {
[firstArrM addObject:@0];
}
[marked addObject:firstArrM];
}
// 2.構(gòu)造一個(gè)矩陣 array-完整路徑的數(shù)組,即a,b,t,g,c...h,并且是一個(gè) rows * cols 的矩陣
NSMutableArray *oriStrs = [NSMutableArray array];
for (int i = 0; i < oriStr.length; i++) {
[oriStrs addObject:[oriStr substringWithRange:NSMakeRange(i, 1)]];
}
NSMutableArray *matrix = [self buildMatrix:oriStrs.copy];
// 一條完整路徑的數(shù)組
NSMutableArray *strs = [NSMutableArray array];
for (int i = 0; i < str.length; i++) {
[strs addObject:[str substringWithRange:NSMakeRange(i, 1)]];
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if ([self backetracking:matrix strs:strs marked:marked pathLen:0 r:i c:j]) {
return YES;
}
}
}
return NO;
}
- (bool)backetracking:(NSArray *)matrix strs:(NSArray *)strs marked:(NSArray *)marked pathLen:(int)pathLen r:(int)r c:(int)c {
// 0.即路徑長度和字符串長度相等
if (pathLen == strs.count) {
NSLog(@"marked = %@",marked);
return YES;
}
// r < 0 || r >= _rows || c < 0 || c >= _cols || ![oriPathStr isEqualToString:tarPathStr] || marked[r][c]
if (r < 0 || r >= _rows || c < 0 || c >= _cols || matrix[r][c] != strs[pathLen] || [marked[r][c] intValue]) {
// 原路徑
return NO;
}
marked[r][c] = @1;
for (NSArray *next in _next) {
int next0 = [(NSNumber *)(next[0]) intValue];
int next1 = [(NSNumber *)(next[1]) intValue];
if ([self backetracking:matrix strs:strs marked:marked pathLen:pathLen + 1 r:(r + next0) c:(c + next1)]) {
return YES;
}
}
marked[r][c] = @0;
return NO;
}
/**
構(gòu)造一個(gè)矩陣 array-完整路徑的數(shù)組,即a,b,t,g,c...h,并且是一個(gè) rows * cols 的矩陣
a b t g
c f c s
j d e h
*/
- (NSMutableArray *)buildMatrix:(NSArray *)array {
// 0.判斷是否有值
if (_rows == 0 || _cols == 0) {
return nil;
}
if (array.count < _rows * _cols) {
return nil;
}
// 1.先構(gòu)造一個(gè)二維數(shù)組
NSMutableArray *secondArrM = [NSMutableArray array];
for (int i = 0; i < _rows; i++) {
NSMutableArray *firstArrM = [NSMutableArray array];
for (int j = 0; j < _cols; j++) {
[firstArrM addObject:@""];
}
[secondArrM addObject:firstArrM];
}
// 2.依次將值填充進(jìn)數(shù)組中
int idx = 0;
for (int i = 0; i < _rows; i++) {
for (int j = 0; j < _cols; j++) {
secondArrM[i][j] = array[idx++];
}
}
return secondArrM;
}
@end
測試案例代碼
// 12.矩陣中的路徑
- (void)matrixHasPath {
MatrixHasPath *hasPath = [[MatrixHasPath alloc] init];
NSString *pathStr = @"abtgcfcsjdeh";
NSMutableArray *tagPaths = [NSMutableArray array];
[tagPaths addObject:@"bfce"];
[tagPaths addObject:@"bfceh"];
[tagPaths addObject:@"acfde"];
[tagPaths addObject:@"bcjd"];
[tagPaths addObject:@"abfceh"];
[tagPaths addObject:@"abtch"];
[tagPaths addObject:@"abtsh"];
for (int i = 0; i < tagPaths.count; i++) {
NSString *tagPath = [tagPaths objectAtIndex:i];
bool result = [hasPath hasPath:pathStr rows:3 cols:4 str:tagPath];
NSLog(@"i = %d, path = %@, result = %d",i,tagPath, result);
NSLog(@"----------------------------------------");
}
}
運(yùn)行結(jié)果
12.路徑覆蓋圖.png
13.機(jī)器人的運(yùn)動(dòng)范圍
題目描述
地上有一個(gè) m 行和 n 列的方格。一個(gè)機(jī)器人從坐標(biāo) (0, 0) 的格子開始移動(dòng)，每一次只能向左右上下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于 k 的格子。
例如，當(dāng) k 為 18 時(shí)，機(jī)器人能夠進(jìn)入方格 (35,37)，因?yàn)?3+5+3+7=18。但是，它不能進(jìn)入方格 (35,37)，因?yàn)?3+5+3+8=19。請問該機(jī)器人能夠達(dá)到多少個(gè)格子？
解題思路
參考12題解思路
詳細(xì)代碼如下
- MovingCount_13.h
@interface MovingCount_13 : NSObject
- (int)movintCount:(int)threshold rows:(int)rows cols:(int)cols;
@end
- MovingCount_13.m
@implementation MovingCount_13 {
NSArray *_next;
int _count;
int _rows;
int _cols;
int _threshold; // 行坐標(biāo)和列坐標(biāo)的數(shù)位之和小于等于于_threshold
NSMutableArray *_digitSum;
}
- (instancetype)init {
self = [super init];
if (self) {
_next = @[@[@0,@(-1)],@[@0,@1],@[@(-1),@0],@[@1,@0]];
}
return self;
}
- (int)movintCount:(int)threshold rows:(int)rows cols:(int)cols {
_rows = rows;
_cols = cols;
_threshold = threshold;
[self initDigitSum];
NSMutableArray *marked = [NSMutableArray array];
for (int i = 0; i < _rows; i++) {
NSMutableArray *firstArrM = [NSMutableArray array];
for (int j = 0; j < _cols; j++) {
[firstArrM addObject:@0];
}
[marked addObject:firstArrM];
}
[self dfs:marked r:0 c:0];
return _count;
}
- (void)dfs:(NSMutableArray *)marked r:(int)r c:(int)c {
if (r < 0 || r >= _rows || c < 0 || c >= _cols || [marked[r][c] intValue]) {
return;
}
marked[r][c] = @1;
if ([_digitSum[r][c] intValue] > _threshold) {
return;
}
_count++;
for (NSArray *next in _next) {
int next0 = [(NSNumber *)(next[0]) intValue];
int next1 = [(NSNumber *)(next[1]) intValue];
[self dfs:marked r:r + next0 c:c + next1];
}
}
- (void)initDigitSum {
int maxNumber = MAX(_rows, _cols);
NSMutableArray *numbers = [NSMutableArray array];
for (int i = 0; i < maxNumber; i++) {
[numbers addObject:@0];
}
for (int i = 0; i < numbers.count; i++) {
int n = i;
while (n > 0) {
numbers[i] = @([numbers[i] intValue] + n % 10);
n /= 10;
}
}
// 初始化原始數(shù)組
if (_digitSum == nil) {
_digitSum = [NSMutableArray array];
for (int i = 0; i < _rows; i++) {
NSMutableArray *firstArrM = [NSMutableArray array];
for (int j = 0; j < _cols; j++) {
[firstArrM addObject:@0];
}
[_digitSum addObject:firstArrM];
}
}
// 賦值
for (int i = 0; i < _rows; i++) {
for (int j = 0; j < _cols; j++) {
_digitSum[i][j] = @([numbers[i] intValue] + [numbers[j] intValue]);
}
}
}
@end
測試案例代碼
// 13.機(jī)器人的運(yùn)動(dòng)范圍
- (void)movingCount {
MovingCount_13 *movingCount = [[MovingCount_13 alloc] init];
int count = [movingCount movintCount:18 rows:10 cols:10];
NSLog(@"count = %d",count);
}
運(yùn)行結(jié)果
13.機(jī)器人的運(yùn)動(dòng)范圍.png
15.二進(jìn)制中 1 的個(gè)數(shù)
題目描述
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。
解題思路
n&(n-1)
該位運(yùn)算去除 n 的位級表示中最低的那一位。
n : 10110100
n-1 : 10110011
n&(n-1) : 10110000
詳細(xì)代碼如下
/** 輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。*/
+ (int)numberOfOne:(int)number {
int cnt = 0;
while (number != 0) {
cnt++;
number &= (number - 1);
}
return cnt;
}
測試案例代碼
// 15.二進(jìn)制中 1 的個(gè)數(shù)
- (void)numberOfOne {
for (int i = 0; i < 20; i++) {
NSLog(@"i = %d, decimal = %@, count = %d",i,[[NSString stringWithFormat:@"%d",i] convertBinarySystemFromDecimalSystem],[NumberOfOne_15 numberOfOne:i]);
}
}
- 十進(jìn)制數(shù)轉(zhuǎn)二進(jìn)制數(shù) (將其寫到NSString 的分類中)
/** 十進(jìn)制數(shù)轉(zhuǎn)二進(jìn)制數(shù) */
- (NSString *)convertBinarySystemFromDecimalSystem {
NSInteger num = [self intValue];
NSInteger remainder = 0; //余數(shù)
NSInteger divisor = 0; //除數(shù)
NSString * prepare = @"";
while (true){
remainder = num % 2;
divisor = num / 2;
num = divisor;
prepare = [prepare stringByAppendingFormat:@"%ld",remainder];
if (divisor == 0){
break;
}
}
NSString * result = @"";
for (NSInteger i = prepare.length - 1; i >= 0; i --){
result = [result stringByAppendingFormat:@"%@",[prepare substringWithRange:NSMakeRange(i , 1)]];
}
// 補(bǔ)齊8位顯示
while (result.length < 8) {
result = [NSString stringWithFormat:@"0%@",result];
}
return result;
}
運(yùn)行結(jié)果
15.二進(jìn)制中1的個(gè)數(shù).png
16.數(shù)值的整數(shù)次方
題目描述
給定一個(gè) double 類型的浮點(diǎn)數(shù) base 和 int 類型的整數(shù) exponent，求 base 的 exponent 次方。
解題思路
下面的討論中 x 代表 base，n 代表 exponent。
image.png
因?yàn)?(x*x)n/2 可以通過遞歸求解，并且每次遞歸 n 都減小一半，因此整個(gè)算法的時(shí)間復(fù)雜度為 O(logN)。
詳細(xì)代碼如下
/** 數(shù)值的整數(shù)次方 */
+ (double)power:(double)base exponent:(int)exponent {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
bool isNegative = NO;
if (exponent < 0) {
exponent -= exponent;
isNegative = YES;
}
double pow = [self power:base * base exponent:exponent / 2];
if (exponent % 2 != 0) {
pow = pow * base;
}
return isNegative ? 1 / pow : pow;
}
測試案例代碼
// 16.數(shù)值的整數(shù)次方
- (void)power {
for (int i = 0; i < 10; i++) {
NSLog(@"base = 2, exponent = %d, result = %f",i,[power_16 power:2 exponent:i]);
}
}
運(yùn)行結(jié)果
16.數(shù)值的整數(shù)次方.png
18.在 O(1) 時(shí)間內(nèi)刪除鏈表節(jié)點(diǎn)
- iOS - 節(jié)點(diǎn),鏈表的實(shí)現(xiàn) - 本題用到該數(shù)據(jù)類型
題目描述
刪除鏈表節(jié)點(diǎn)
解題思路
1.如果該節(jié)點(diǎn)不是尾節(jié)點(diǎn)，那么可以直接將下一個(gè)節(jié)點(diǎn)的值賦給該節(jié)點(diǎn)，然后令該節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn)，再刪除下一個(gè)節(jié)點(diǎn)，時(shí)間復(fù)雜度為 O(1)。
image.png
2.否則，就需要先遍歷鏈表，找到節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，然后讓前一個(gè)節(jié)點(diǎn)指向 null，時(shí)間復(fù)雜度為 O(N)。
image.png
綜上，如果進(jìn)行 N 次操作，那么大約需要操作節(jié)點(diǎn)的次數(shù)為 N-1+N=2N-1，其中 N-1 表示 N-1 個(gè)不是尾節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)以 O(1) 的時(shí)間復(fù)雜度操作節(jié)點(diǎn)的總次數(shù)，N 表示 1 個(gè)尾節(jié)點(diǎn)以 O(N) 的時(shí)間復(fù)雜度操作節(jié)點(diǎn)的總次數(shù)。(2N-1)/N ~ 2，因此該算法的平均時(shí)間復(fù)雜度為 O(1)。
詳細(xì)代碼如下
/** 刪除節(jié)點(diǎn) */
- (void)deleteNode {
NSMutableArray *numbers = [NSMutableArray array];
for (int i = 0; i < 10; i++) {
[numbers addObject:@(i)];
}
LinkedArray *linkArray = [[LinkedArray alloc] initLiknedArrayWithNunbers:numbers];
ListNode *headNode = [linkArray getFirstListNode];
ListNode *lastDelNode = [linkArray getLastListNode];
NSLog(@"---------------原始鏈表數(shù)據(jù)---------------");
[headNode printAllListNode];
ListNode *newHeadNode = [self deleteNode:headNode tagDelNode:lastDelNode];
NSLog(@"---------------刪除后鏈表數(shù)據(jù)---------------");
[newHeadNode printAllListNode];
}
- (ListNode *)deleteNode:(ListNode *)headNode tagDelNode:(ListNode *)tagDelNode {
// 頭節(jié)點(diǎn)和要?jiǎng)h除的節(jié)點(diǎn)為空
if (headNode == nil || tagDelNode == nil) {
return nil;
}
if (tagDelNode.next != nil) { // 要?jiǎng)h除的節(jié)點(diǎn)不是尾節(jié)點(diǎn)
ListNode *next = tagDelNode.next;
tagDelNode.content = next.content;
tagDelNode.next = next.next;
} else {
ListNode *cur = headNode;
while (cur.next != tagDelNode) {
cur = cur.next;
}
cur.next = nil;
}
return headNode;
}
測試案例代碼
// 18.在 O(1) 時(shí)間內(nèi)刪除鏈表節(jié)點(diǎn)
- (void)deleteNode {
DeleteNode_18 *deleteNode = [[DeleteNode_18 alloc] init];
[deleteNode deleteNode];
}
運(yùn)行結(jié)果
18.1刪除鏈表節(jié)點(diǎn).png
18.2 刪除鏈表中重復(fù)的結(jié)點(diǎn)
題目描述
image.png
解題思路
參考18.1的解題思路
詳細(xì)代碼如下
/** 刪除 重復(fù)節(jié)點(diǎn) */
- (void)deleteDuplicationNode {
NSMutableArray *numbers = [NSMutableArray array];
for (int i = 0; i < 10; i++) {
if (i / 2 == 1) {
[numbers addObject:@(2)];
} else if (i / 3 == 1) {
[numbers addObject:@(3)];
} else {
[numbers addObject:@(i)];
}
}
LinkedArray *linkArray = [[LinkedArray alloc] initLiknedArrayWithNunbers:numbers];
NSLog(@"----------------原始鏈表數(shù)據(jù)----------------");
[linkArray printAllListNode];
ListNode *firstNode = [linkArray getFirstListNode];
ListNode *headNode = [self deleteDuplicationListNode:firstNode];
NSLog(@"----------------刪除重復(fù)節(jié)點(diǎn)后的鏈表數(shù)據(jù)----------------");
[headNode printAllListNode];
}
// 刪除重復(fù)節(jié)點(diǎn)
- (ListNode *)deleteDuplicationListNode:(ListNode *)pHeadNode {
if (pHeadNode == nil || pHeadNode.next == nil) {
return pHeadNode;
}
ListNode *next = pHeadNode.next;
if (pHeadNode.value == next.value) {
while (next != nil && pHeadNode.value == next.value) {
next = next.next;
}
return [self deleteDuplicationListNode:next];
} else {
pHeadNode.next = [self deleteDuplicationListNode:pHeadNode.next];
return pHeadNode;
}
}
測試案例代碼
// 18.2 刪除鏈表中重復(fù)的結(jié)點(diǎn)
- (void)deleteDuplication {
DeleteNode_18 *deleteNode = [[DeleteNode_18 alloc] init];
[deleteNode deleteDuplicationNode];
}
運(yùn)行結(jié)果
18.2.刪除重復(fù)節(jié)點(diǎn).png
本文參考CS_Nodes 劍指 offer 題解.md 非常感謝該作者
相關(guān)知識點(diǎn)文章參考鏈接地址
- 更多OC算法詳解文章請持續(xù)關(guān)注作者，本人會(huì)在接下來的時(shí)間陸續(xù)整理。
如有錯(cuò)誤，歡迎指正，多多點(diǎn)贊，打賞更佳，您的支持是我寫作的動(dòng)力。
