饭后小甜点leetcode——字符串中的算法

文章目录

• • • 字符串翻转
    • • 翻转整个字符串
      • 分组翻转字符串
      • 字符串内部的单词位置翻转（参数为string）
      • 字符串内部的单词位置翻转（参数为char[]）
      • 字符串中的单词内部翻转
    • 字符串匹配
    • • 实现strStr()
    • 字符串和数字运算

字符串翻转

翻转整个字符串

344. 反转字符串
【思路】两头逼近

public void ReverseString(char[] s)
{var i = 0; var j = s.Length - 1;while (i < j){var temp = s[i];s[i] = s[j];s[j] = temp;i++; j--;}
}

分组翻转字符串

2k个一组，每组翻转前k个，不满k个的组全部翻转，介于k和2k之间的组翻转前k个

public string ReverseStr(string s, int k)
{var res = s.ToArray();var i = 0;while (i < s.Length){var l = i;var r = i + k - 1;if (r >= s.Length){r = s.Length - 1;//如果r到了数组边界，令r等于最后一个元素下标}while (l < r){var t = res[l];res[l] = res[r];res[r] = t;l++; r--;}i += k * 2;}return new string(res);
}

字符串内部的单词位置翻转（参数为string）

一个字符串，把里面的每一个单词进行单词间翻转，单词间空格只保留一个，多余的不要。
【思路】就代码简洁度来说，直接用C#的LINQ解决。
【易错点】记住函数咋调用

public string ReverseWords(string s)
{var list = s.Split(' ').Where(t => t != "").ToList();list.Reverse();return string.Join(" ", list);
}

字符串内部的单词位置翻转（参数为char[]）

【思路】两次翻转，第一次翻转范围为整个字符数组，第二次（或者说后面的N次）翻转每个单词内部

public class WordsReverseII
{public void ReverseWords(char[] str){var i = 0; var j = str.Length - 1;//第一次调用Swap(str, i, j);i = 0; j = 0;while (j < str.Length){//每个单词while (j < str.Length && str[j] != ' '){//每个单词内部j++;}//第二次调用Swap(str, i, j - 1);i = j + 1; j = i;}}public void Swap(char[] str, int i, int j){while (i < j){var temp = str[i];str[i] = str[j];str[j] = temp;i++; j--;}}
}

字符串中的单词内部翻转

【思路】跟上一题差不多，这道题给的条件是没有多余空格，所以直接从上一题改改就行。

public class WordsReverseIII
{public string ReverseWords(string s){var arr = s.ToArray();var i = 0; var j = 0;while (i < s.Length){while (j < s.Length && arr[j] != ' '){j++;}Swap(arr, i, j - 1);i = j + 1; j = i;}return new string(arr);}public void Swap(char[] str, int i, int j){while (i < j){var temp = str[i];str[i] = str[j];str[j] = temp;i++; j--;}}
}

字符串匹配

实现strStr()

leetcode题目地址

【思路】用KMP算法
【复杂度】O(n)

public int StrStr(string S, string T)
{if (string.IsNullOrEmpty(T)) return 0;var next = GetNext(T);var i = 0; var j = 0;while (i < S.Length && j < T.Length){if (j == -1 || S[i] == T[j]){i++; j++;}else j = next[j];}if (j == T.Length) return i - j;return -1;
}private int[] GetNext(string t)
{var next = new int[t.Length];next[0] = -1;var i = 0; var j = -1;while (i < t.Length - 1){if (j == -1 || t[i] == t[j]){i++; j++;//next数组是prefix table向右移动一位得到的，所以这两要加一，其中，prefix table中的值是common前后缀长度next[i] = j;}else j = next[j];}return next;
}

字符串和数字运算

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！