双指针 ​
26. 删除有序数组重复项 ​
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。返回
k。示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
java
public int removeDuplicates(int[] nums) {
//快慢双指针同一起点
int slow = 0,fast = 0;
//fast在前面探路，如果发现我们想要的不重复元素
for(fast =0;fast<nums.length;fast++){
//就让slow前进一步，然后赋值给slow
if(nums[fast]!=nums[slow]){
slow++;
nums[slow] = nums[fast];
}
}
return slow+1;
}83. 删除排序链表重复元素 ​
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]java
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return head;
//快慢双指针，快指针在前面探路
ListNode slow = head,fast = head;
while(fast!=null){
//如果发现我们想要的不重复元素
if(fast.val!=slow.val){
//把不重复的节点接到slow后面
slow.next = fast;
//slow前进一步
slow = slow.next;
}
fast = fast.next;
}
//最后slow断开与后面重复节点的连接
slow.next = null;
return head;
}27. 移除元素 ​
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]java
public int removeElement(int[] nums, int val) {
//快慢双指针，fast在前面探路
int slow = 0,fast = 0;
for(fast = 0;fast < nums.length;fast++){
//fast是想要的不等于val的数字
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}283. 移动零 ​
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]java
public void moveZeroes(int[] nums) {
int fast = 0,slow = 0;
while(fast<nums.length){
//把不等于0的全部移动到前面
if(nums[fast]!=0){
nums[slow]=nums[fast];
slow++;
}
fast++;
}
//把slow后面的全部赋值为0
while(slow<nums.length){
nums[slow]=0;
slow++;
}
}167. 两数之和 II - 输入有序数组 ​
你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。java
public int[] twoSum(int[] numbers, int target) {
//一看到有序数组，就想到双指针
int left = 0,right = numbers.length-1;
//一左一右相向而行
while(left<right){
int sum = numbers[left]+numbers[right];
if(sum==target){
//题目的下标是从1开始的
return new int[]{left+1,right+1};
}else if(sum<target){
left++;
}else if(sum>target){
right--;
}
}
return null;
}344. 反转字符串 ​
一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
java
public void reverseString(char[] s) {
int left=0,right=s.length-1;
while(left<right){
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}5. 最长回文子串 ​
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。java
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
//aba类型的回文子串
String palindromeOdd = findPalindrome(i, i, s);
//abba类型的回文子串
String palindromeEven = findPalindrome(i, i + 1, s);
res = res.length()>palindromeEven.length()?res:palindromeEven;
res = res.length()>palindromeOdd.length()?res:palindromeOdd;
}
return res;
}
//在s中寻找以 s[left]和s[right]为中心的最长回文子串
String findPalindrome(int left,int right,String s){
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left+1, right);
}
}简单 ​
387字符串中第一个唯一字符 ​
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
输入: s = "leetcode"
输出: 0
输入: s = "loveleetcode"
输出: 2C
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> mmap;
for(auto v:s){//map里存储每个字符出现的次数
mmap[v]++;
}
for(int i=0;i<s.size();i++){
if(mmap[s[i]]==1)//如果某一个字符出现的次数不是1
return i;
}
return -1;
}
};C
//s.find(s[i]) : 返回字符串s中从左向右查找s[i]第一次出现的位置；
//s.rfind(s[i]) : 返回字符串s中从右向左查找s[i]第一次出现的位置；
class Solution {
public:
int firstUniqChar(string s) {
for(int i = 0; i < s.size(); i++){
if(s.find(s[i]) == s.rfind(s[i])){
return i;
}
}
return -1;
}
};383赎金信 ​
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
提示：
- 1 <= ransomNote.length, magazine.length <= 105
- ransomNote 和 magazine 由小写英文字母组成
输入：ransomNote = "aa", magazine = "aab"
输出：true
输入：ransomNote = "aa", magazine = "ab"
输出：falseC
//数组记录每个字母出现的次数
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int ab[26]{};
//统计magazine中包含的各个小写字母的个数
for(char &c : magazine){
ab[c - 'a']++;
}
//统计ransomNote中包含的各个小写字母的个数, 两者相互抵消
for(char &c : ransomNote){
ab[c - 'a']--;
}
for(int &i : ab){
if(i<0)
return false;
}
return true;
}
};
//std::string.find()也能做242有效的字母异位词 ​
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
提示:
1 <= s.length, t.length <= 5 * 104s和t仅包含小写字母输入: s = "anagram", t = "nagaram" 输出: true 输入: s = "rat", t = "car" 输出: falseC//2个map class Solution { public: bool isAnagram(string s, string t) { unordered_map<char,int> mps; unordered_map<char,int> mpt; for(char &c : s){ mps[c]++; } for(char &c : t){ mpt[c]++; } return mps==mpt; } };C//一个数组，互相抵消 class Solution { public: bool isAnagram(string s, string t) { int ab[26]{}; for(char &c : s){ ab[c - 'a']++; } for(char &c : t){ ab[c - 'a']--; } for(int &i : ab){ if(i!=0) { return false; } } return true; } };
中等 ​
36有效的数独 ​
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
输入：board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出：true 示例 2： 输入：board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出：false 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
C
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//定义三个二维整型向量，分别记录每一行、每一列、每个九宫格里每个数字出现的次数
vector<vector<int>> rowVec(9,vector<int>(9,0)); //行向量，rowVec[i][j]表示第i行数字j出现的次数
vector<vector<int>> culVec(9,vector<int>(9,0)); //列向量，culVec[i][j]表示第i列数字j出现的次数
//九宫格向量，nineVec[i][j][k]表示第i行第j列的九宫格里数字k出现的次数
vector<vector<vector<int>>> nineVec(9,vector<vector<int>>(9,vector<int>(9,0)));
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char c=board[i][j];
if(c!='.'){
//将当前字符转换为数字并减去1，因为数字从1开始，而数组下标从0开始
int n=c-'0'-1;
rowVec[i][n]++;
culVec[n][j]++;
//在九宫格向量中将第i行第j列的九宫格里数字n的出现次数加1
nineVec[i/3][j/3][n]++;
//如果当前数字在行向量、列向量或九宫格向量中出现次数大于1，则表示不是有效的数独，返回false
if(rowVec[i][n]>1||culVec[n][j]>1||nineVec[i/3][j/3][n]>1)
return false;
}
}
}
//遍历结束后没有出现不符合规则的情况，则表示是有效的数独，返回true
return true;
}
};