520 Detect Capital
思路:
- 题目:判定word :if the usage of capitals in it is right.
- 遍历所有的string:
两种情况:
首字母capitals–>判定第二个字母是否大写–>所有字母大写
otherwise 除第一个以外全部小写,首字母小写–>判定所有的字母是否小写
(ASCII码中 Z<a)- 细节:无
class Solution {
public:bool detectCapitalUse(string word) {bool isCapital = 0;//just 0&1 both capital aB ab AB Abif(word[0] < 'a' && word[1] < 'a'){isCapital = 1;}int n = word.size();for(int i = 1 ; i < n ; i ++){if(isCapital && word[i] >= 'a'){return false;}//大写情况出现小写else if(!isCapital && word[i] < 'a'){return false;}//小写情况出现大写}return true;}
};
125 Valid Palindrome
思路:
- 题目:回文串,Alphanumeric characters include letters and numbers.
- 大体: 判断首尾是否一致:i 反转string ii 双指针一前一后判断。
选ii,跳过非Alphanumeric characters的内容,bool isCharacter(char c)isalnum() ;大写变小写:s[i]-‘A’+‘a’;tolower();
大致:i从头到尾 j从尾到头,移动ij直至对应位置isCharacter,然后判别s[i] == s[j]?如果不等就return
false, 等就继续。直至循环(i < n && j >= 0)(i<j)结束,return true。- 细节:当String.size() == 0 or 1需直接返回true.优化中不需要,因为left < right不满足直接return true了。
class Solution {
public:bool isCharacter(char c){return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');}char changeCapital(char c){if(c >= 'A' && c <= 'Z'){return 'a' + (c - 'A');}return c;}bool isPalindrome(string s) {int n = s.size();if(n < 2) return true;int i = 0, j = n - 1;while(i < j) {if(!isCharacter(s[i])) {i++;continue;}if(!isCharacter(s[j])) {j--;continue;}if(changeCapital(s[i]) != changeCapital(s[j])) {return false;}i++;j--;}return true;}
};
c++代码学习
tolower();//大写变小写
isalnum();//判断是否为数字或者字符串
优化:
class Solution {
public:bool isPalindrome(string s) {int n = s.size() , left = 0 , right = n-1;while(left < right){while(left < right && !isalnum(s[left])){left++;}while(left < right && !isalnum(s[right])){right--;}if(tolower(s[left]) != tolower(s[right])){return false;}left++;right--;}return true;}
};
14 Longest Common Prefix
【默写】纵向比较,没做出的原因:以为是子字符串,prefix是前缀!!!
语言学导论全忘了思路:
- 题目:prefix前缀特点:从0开始,按顺序一一比较。
- 大体:纵向比较,确定第一个string为参考,和后面的string中同一位置比较,比较完这一位才会比较后一位。当对应位置字符不等或者后者的字符串遍历结束,返回strs[0]对应的子串。
- 细节:strs为空时,return “”;
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if(!strs.size())return "";int len = strs[0].size();int count = strs.size();//第一个数组为固定比较对象for(int i = 0 ; i < len ;i++){char c = strs[0][i];for(int j = 1 ; j < count ; j++){if(i == strs[j].size() || c != strs[j][i]){return strs[0].substr(0 , i);}}}return strs[0];}
};
34 Find First and Last Position of Element in Sorted Array
思路:
- 题目:non-decreasing 非递减数组,找始末位置 他有要求时间复杂度!!!
- 大体:遍历数组:当nums[i]<tar的时候,直接continue。当nums[i]>tar时,直接break。剩余就是有tar,判断边界就可以,起始:i==0 || nums[i-1] != tar 结束:i == n-1 || nums[i+1] !=tar
- 细节:注意为空的情况或者tar就不在nums数组范围内,直接return {-1 , -1};
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res = {-1 , -1};int n = nums.size();if(!n || target < nums[0] || target > nums[n-1]){return res;}//non-decreasing orderfor(int i = 0 ; i < n ; i++){if(nums[i] < target){continue;}if(nums[i] > target){break;}if(i == 0 || nums[i-1] != target){res[0] = i;}if(i == n-1 || nums[i+1] != target){res[1] = i;break;}}return res;}
};
优化:二分查找
int left = 0 , right = n-1;
while(left <= right){mid = (left + right) >> 1;//如果mid满足条件 [left ,mid]之间查找 即right = mid;//不满足就是[mid+1 , right] 即left = mid+1;
}
//---------------------------acwingの----------------------
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size() , left = 0 , right = n-1;vector<int> res = {-1,-1};//找起始while(left <= right){int mid = (left + right) >> 1;if(nums[mid] == target){//往前找res[0] = mid;right = mid-1;}else if(nums[mid] > target){right = mid-1;}else{left = mid+1;}}left = 0;right = n-1;//找结尾while(left <= right){int mid = (left + right) >> 1;if(nums[mid] == target){//往后找res[1] = mid;left = mid+1;}else if(nums[mid] > target){right = mid-1;}else{left = mid+1;}}return res;}
};