520. 检测大写字母
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public boolean detectCapitalUse(String word) {
int i = 0;
char[] arr = word.toCharArray();
int up = 0, low = 0;
while(i < arr.length){
if(arr[i] >= 'a'){
low++;
}else{
up++;
}
i++;
}
if(up == arr.length) return true;
if(low == arr.length) return true;
if(up == 1 && arr[0] < 'a') return true;
return false;
}
|
125. 验证回文串
经典问题，需要过滤非字符非数字。
1
2
3
4
5
6
7
8
9
10
11
| public boolean isPalindrome(String s) {
if(s == null) return true;
s = s.toLowerCase();
StringBuilder str = new StringBuilder(s.length());
for (char c : s.toCharArray()) {
if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
str.append(c);
}
}
return str.toString().equals(str.reverse().toString());
}
|
14. 最长公共前缀
- 首先计算出最短字符串的长度，这个长度就是外层循环的遍历次数。
- 内层逐个比较字符串的指定位置的值。
- 通过StringBuilder拼接公共前缀。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public String longestCommonPrefix(String[] strs) {
if(strs.length == 0)
return "";
StringBuilder sb = new StringBuilder();
int minLength = 1000;
for(String str : strs){
if(str.length() < minLength){
minLength = str.length();
}
}
String demo = strs[0];
for(int i = 0; i< minLength; i++){
boolean flag = true;
char c = demo.charAt(i);
for(int j = 1; j < strs.length; j++){
if(strs[j].charAt(i) != c){
flag = false;
break;
}
}
if(flag){
sb.append(c);
flag = true;
}else{
break;
}
}
return sb.toString();
}
|
434. 字符串中的单词数
一轮遍历即可，判断依据是：当前值是空格，前一位非空格
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int countSegments(String s) {
if (s == null) {
return 0;
}
s = s.trim();
if (s.length() == 0) {
return 0;
}
int count = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == 32 && s.charAt(i - 1) != 32) {
count++;
}
}
return count;
}
|
58. 最后一个单词的长度
1
2
3
4
5
| public int lengthOfLastWord(String s) {
String[] s1 = s.split(" ");
if(s1.length == 0) return 0;
return s1[s1.length -1].length() == 0 ? 0 : s1[s1.length -1].length();
}
|
344. 反转字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void reverseString(char[] s) {
int left = 0, right = s.length -1;
while(left < right){
swap(s , left, right);
left++;
right--;
}
}
public void swap(char[] s, int i, int j){
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
|
541 反转字符串Ⅱ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i+= 2*k){
int rest = arr.length - i;
if(rest < k){
reverse(arr,i, arr.length - 1);
}else if(rest < 2 * k && rest >= k){
reverse(arr,i, i + k - 1);
}else{
reverse(arr,i, i+k - 1);
}
}
return String.valueOf(arr);
}
public void reverse(char[] s,int i, int j) {
int left = i, right = j;
while(left < right){
swap(s , left, right);
left++;
right--;
}
}
public void swap(char[] s, int i, int j){
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
|
557. 反转字符串中的单词Ⅲ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public String reverseWords(String s) {
String[] strs = s.split(" ");
String[] reverseString = new String [strs.length];
int index = 0;
for(String str : strs){
reverseString[index++] = new StringBuffer(str).reverse().toString();
}
StringBuilder sb = new StringBuilder();
for(int i =0; i < strs.length; i++){
sb.append(reverseString[i]);
if(i != reverseString.length - 1) sb.append(" ");
}
return sb.toString();
}
|
151. 反转字符串中的单词
1
2
3
4
5
6
| public String reverseWords(String s) {
s = s.trim();
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
|
387. 字符串中的第一个唯一字符
1
2
3
4
5
6
7
8
9
10
11
12
| public static int firstUniqChar(String s) {
int[] letter=new int[26];
for (char c:s.toCharArray()) {
letter[c-'a']++;
}
for (int i = 0; i <s.length() ; i++) {
if(letter[s.charAt(i)-'a']==1) {
return i;
}
}
return -1;
}
|
389. 找不同
1
2
3
4
5
6
7
8
9
10
11
| char findTheDifference(string s, string t) {
vector<int> count(26,0);
for(char ch : s){
count[ch - 'a']++;
}
for(char ch : t){
count[ch - 'a']--;
if(count[ch - 'a'] < 0) return ch;
}
return ' ';
}
|
383. 赎金信
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool canConstruct(string ransomNote, string magazine) {
vector<int> count(26, 0);
for(char ch : magazine){
count[ch - 'a']++;
}
for(char ch : ransomNote){
count[ch - 'a']--;
if(count[ch - 'a'] < 0){
return false;
}
}
return true;
}
|
242. 有效的字母异位词
1
2
3
4
5
6
7
| bool isAnagram(string s, string t) {
vector<int> cnt(26,0);
for(char ch : s) cnt[ch - 'a']++;
for(char ch : t) cnt[ch - 'a']--;
for(int count : cnt) if(count != 0) return false;
return true;
}
|
49. 字母异位词分组
1
2
3
4
5
6
7
8
9
10
11
| vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
map<string, vector<string>> map;
for(int i =0; i < strs.size(); i++){
string key = strs[i];
sort(key.begin(), key.end());
map[key].push_back(strs[i]);
}
for(auto ite = map.begin(); ite != map.end(); ite++) res.push_back(ite->second);
return res;
}
|
451. 根据字符出现频率排序
1
2
3
4
5
6
7
8
9
10
11
12
| string frequencySort(string s) {
map<char,int> map;
for(char c : s) map[c]++;
vector<pair<char, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), [](auto & a, auto & b){
return a.second > b.second;
});
string res;
for(auto v : vec) res += string(v.second,v.first);
return res;
}
|
657. 机器人能否返回原点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| bool judgeCircle(string moves) {
int index = 0;
int updown = 0, rightleft = 0;
while(index <= moves.length()){
switch(moves[index]){
case 'R':
rightleft++;
break;
case 'L':
rightleft--;
break;
case 'U':
updown++;
break;
case 'D':
updown--;
break;
}
index++;
}
if(updown == 0 && rightleft == 0) return true;
return false;
}
|
551. 学生出勤记录Ⅰ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| bool checkRecord(string s) {
int late = 0, absent = 0;
for(int i = 0; i < s.length(); i++){
if(s[i] == 'A'){
absent++;
late = 0;
if(absent > 1) return false;
}else if(s[i] == 'L'){
late++;
if(late > 2) return false;
}else {
late = 0;
}
}
return true;
}
|
28. 实现strStr()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int strStr(string haystack, string needle) {
if ( needle == "" )
return 0;
int hlen = haystack.length();
int nlen = needle.length();
int i,j;
for(i=0;i<hlen;i++){
for(j=0;j<nlen;j++)
if(haystack[i+j]!=needle[j])
break;
if(j==nlen)
return i;
}
return -1;
}
|
8. 字符串转换整数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int myAtoi(string s) {
int i=0;
while(i<s.size()&&s[i]==' ') i++;
if(i==s.size()) return 0;
int sign=1;
if(s[i]=='-'){
sign=-1;
i++;
}
else if(s[i]=='+')
i++;
else if(!isdigit(s[i]))
return 0;
int n=0;
while(isdigit(s[i])&&i<s.size()){
if((INT_MAX-(s[i]-'0'))/10.0<n) return sign==-1?sign*INT_MAX-1:INT_MAX;
n=10*n+(s[i]-'0');
i++;
}
return sign*n;
}
|
67. 二进制求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| string addBinary(string a, string b) {
string result;
const int n = a.size() > b.size() ? a.size() : b.size();
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int carry = 0;
for(int i = 0; i < n; i++){
int ai = i < a.size() ? a[i] - '0' : 0;
int bi = i < b.size() ? b[i] - '0' : 0;
int val = (ai + bi + carry) % 2;
carry = (ai + bi + carry) / 2;
result.insert(result.begin(), val + '0');
}
if(carry == 1) result.insert(result.begin(), '1');
return result;
}
|
412. Fizz Buzz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<string> fizzBuzz(int n) {
vector<string> res;
for(int i = 1; i <= n; i++){
string tmp;
if(i % 15 == 0){
res.push_back("FizzBuzz");
}else if(i % 5 == 0){
res.push_back("Buzz");
}else if(i % 3 == 0){
res.push_back("Fizz");
}else{
res.push_back(to_string(i));
}
}
return res;
}
|
299. 猜数字游戏
需要注意数字出现的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| string getHint(string secret, string guess) {
int bull = 0, cow = 0;
vector<int> num(10,0);
for(int i = 0; i < guess.size(); i++){
if(guess[i] == secret[i]){
bull++;
}else {
if(num[secret[i] - '0']++ < 0) cow++;
if(num[guess[i] - '0']-- > 0) cow++;
}
}
return to_string(bull) + 'A' + to_string(cow) + 'B';
}
|
506. 相对名次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| vector<string> findRelativeRanks(vector<int>& score) {
vector<int> org = score;
sort(score.rbegin(), score.rend());
unordered_map<int, string> order;
for(int i = 0; i < score.size(); i++){
if(i >= 3) order[score[i]] = to_string(i+ 1);
if(i == 0) order[score[i]] = "Gold Medal";
if (i == 1) order[score[i]] = "Silver Medal";
if (i == 2) order[score[i]] = "Bronze Medal";
}
vector<string> res(score.size(), "");
for(int i = 0; i < res.size(); i++){
res[i] = order[org[i]];
}
return res;
}
|
539. 最小时间差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int findMinDifference(vector<string>& timePoints) {
vector<int> q;
int res = INT_MAX;
for(string t : timePoints){
int hour = 10 * (t[0] - '0') + t[1] - '0';
int min = 10 * (t[3] - '0') + t[4] - '0';
q.push_back(60 * hour + min);
}
sort(q.begin(), q.end());
q.push_back(q[0] + 24 * 60);
for(int i = 1; i < q.size(); i++){
res = min(res, q[i] - q[i - 1]);
}
return res;
}
|
553. 最优除法
题解：被除数不变，除数最小，如果能理解这个数学知识，那么就是一道easy难度的题目。
1
2
3
4
5
6
7
8
9
10
11
12
13
| string optimalDivision(vector<int>& nums) {
if(nums.size() == 1){
return to_string(nums[0]);
}else if(nums.size() == 2){
return to_string(nums[0]) + "/" + to_string(nums[1]);
}
string res(to_string(nums[0]) + "/(");
for(int i = 1; i < nums.size() - 1; i++){
res += to_string(nums[i]) + "/";
}
res += to_string(nums.back()) + ")";
return res;
}
|
38. 外观数列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public String countAndSay(int n) {
String res = "1";
for(int i = 2; i <= n; i++){
StringBuilder temp = new StringBuilder();
for(int j = 0; j < res.length(); j++){
int count = 1;
while(j + 1 < res.length() && res.charAt(j) == res.charAt(j + 1)){
j++;
count++;
}
temp.append(count).append(res.charAt(j));
}
res = temp.toString();
}
return res;
}
|