总结
CASE
1、回文
最长回文子串。
最多删除一个字符串 1.1.2
给定一个字符串判断有多少个回文串。（1.2）
回文对 （1.3）
2、运算
加1 （4.1）
求积
类加数
3、子序列
3、最长子串
知识点
1、字符串
|
1 2 3 4 5 6 7 |
//string 转 char char a = line.charAt(right)) char[] arr = s.toCharArray(); String[] array = s.split(" "); s.length(); startsWith subString |
2、 stringBuilder可以翻转
reverse();
3、Character
|
1 2 3 4 5 6 7 8 9 10 |
isLetterOrDigit(left); isLetter(left); isDigit(left); toLowerCase(ch); toUpperCase isLowerCase isUpperCase toUpperCase |
1 回文串
回文解释：以某个字符为中心的前缀和后缀都是相同的，例如以一段回文串“aba”为例，以b为中心，它的前缀和后缀都是相同。
1.1 判断是否回文
1.1.1 判断一个字符串是否为回文 （双指针）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/** * 判断一个字符串是否为回文。 需要考虑空字符串 */ private boolean checkStrIsHuiwen(String line) { // 空字符 if (line.length() == 0) { return true; } int left = 0; int right = line.length() - 1; while (left < right) { if (line.charAt(left) == line.charAt(right)) { left++; right--; continue; } else { return false; } } return true; } |
1.1.2 删除一个字符串之后 （双指针）
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: “aba”
输出: True
示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。
链接：https://leetcode-cn.com/problems/valid-palindrome-ii
算法：
- 在发现第一次不一致之后，分为两种情况。
|
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 33 34 35 36 37 |
class Solution { public boolean validPalindrome(String s) { int i =0; int j=s.length()-1; boolean delete = false; while(true){ if(i>=j){ return true; } if(s.charAt(i) != s.charAt(j)){ break; }else{ i++; j--; } } <span style="color: #ff0000;"><strong>// 不一致之后，分为两种情况</strong></span> return valid(s,i+1,j) || valid(s,i,j-1); } public boolean valid(String s,int beg,int end){ if(beg>=end){ return true; } if(s.charAt(beg) == s.charAt(end)){ return valid(s,beg+1,end-1); }else{ return false; } } } |
1.1.3 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
|
1 2 |
输入: "A man, a plan, a canal: Panama" 输出: true |
算法：通过StringBuilder.reverse判断。
|
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 |
class Solution { public boolean isPalindrome(String s) { if(s==null || s.length()==0){ return true; } int i=0; StringBuilder builder = new StringBuilder(); while(i<s.length()){ char left = s.charAt(i); i++; if(!Character.isLetterOrDigit(left) ){ continue; } left = Character.toLowerCase(left); builder.append(left+""); } if(builder.toString().equals(builder.reverse().toString())){ return true; }else{ return false; } } } |
1.2 最长回文串(中心拓展法)
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
|
1 2 3 |
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 |
算法：
- 核心：一个回文子串一定是有轴心的。根据轴心计算回文字符串时需要区分奇偶两种情况。
- STEP1 对于子串中每个字符作为轴心时，都可以计算一个最大回串。
- STEP2 循环遍历一遍字符串就可以得到每个字符作为轴心时，最大子串了
注意：这里有个疑问，就是对于”aaaa”这样字符串，”aaaa”是在遍历[1]个节点时，得到。一个回文子串一定是有轴心的，只需要关注这个轴心的的回文串就可以。
|
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 33 34 35 36 37 38 39 |
class Solution { public String longestPalindrome(String s) { if(s==null || s.length()==0){ return ""; } int maxLen = Integer.MIN_VALUE; int position = -1; for (int i = 0; i < s.length(); i++) { // 根据轴心计算回文字符串时需要区分奇偶两种情况。所以这里接受riht和left： // 如偶数时，那么传递参数时，就是right=left+1，否则right=left int jlen = findLen(s, i, i); int rlen = findLen(s, i, i + 1); int len = Math.max(jlen, rlen); if (len > maxLen) { maxLen = len; position = i; } } int start = position - (maxLen - 1) / 2; int end = position + maxLen / 2; return s.substring(start, end + 1); } // left作为轴心的最长回文串。 private int findLen(String input, int left, int right) { while (left >= 0 && right < input.length()) { if (input.charAt(left) != input.charAt(right)) { break; } else { left--; right++; } } return right - 1 - left; } } |
1.3 回文子串个数（中心拓展法）
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。https://leetcode-cn.com/problems/palindromic-substrings/
|
1 2 3 |
输入："aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" |
思路：以 每个点 为轴心 进行判断是否有回文，包含奇数和偶数个数
|
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 |
class Solution { public int countSubstrings(String s) { List<String> result = new ArrayList(); for(int index=0 ;index<s.length();index++){ // 查询偶数个对称节点 find(s, index,index+1, result); // 查找奇数个对称点 find(s, index,index, result); } return result.size(); } private void find(String input, int left,int right, List<String> result) { // 记录最新的结果 String lastResult = ""; while (left >= 0 && right < input.length()) { if (input.charAt(left) == input.charAt(right)) { if(left != right){ lastResult = input.charAt(left)+lastResult + input.charAt(right); }else{ lastResult = input.charAt(left)+""; } result.add(lastResult); left--; right++; } else { break; } } } } |
1.4 回文对
给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。https://leetcode-cn.com/problems/palindrome-pairs/
|
1 2 3 |
输入：["bat","tab","cat"] 输出：[[0,1],[1,0]] 解释：可拼接成的回文串为 ["battab","tabbat"] |
思路：借助于map进行分组，考虑空字符串情况，空字符传需要和各个字符串拼接进行判断。
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
/** * 考虑:空字符串 * 空字符串可以和任意字符串组成回文 */ public class HuiwenZuhe { public List<List<Integer>> palindromePairs(List<String> words) { Map<String, List<Integer>> begCharDic = new HashMap<String, List<Integer>>(); Map<String, List<Integer>> endCharDic = new HashMap<String, List<Integer>>(); // 初始化数据 int index = 0; for (String word : words) { String begChar = ""; String endChar = ""; // 空字符 if (null != word && word.length() > 0) { begChar = word.charAt(0) + ""; endChar = word.charAt(word.length() - 1) + ""; } if (!begCharDic.containsKey(begChar)) { begCharDic.put(begChar, new ArrayList<Integer>()); } begCharDic.get(begChar).add(index); if (!endCharDic.containsKey(endChar)) { endCharDic.put(endChar, new ArrayList<Integer>()); } endCharDic.get(endChar).add(index); index++; } // 组合判断 List<List<Integer>> result = new ArrayList<List<Integer>>(); for (Map.Entry<String, List<Integer>> entry : begCharDic.entrySet()) { List<Integer> prefixList = entry.getValue(); // 1.起始map中包含空字符串可以和任意字符串组成回文 if (entry.getKey().equals("")) { processBegEmpty(prefixList, endCharDic, words, result); continue; } // 2.begKey不为空字符串 // 2.1 处理endMap中存在空字符串 if (endCharDic.containsKey("")) { processEndEmpty(prefixList, endCharDic, words, result); } // 2.2 处理endMap非空字符 if (!endCharDic.containsKey(entry.getKey())) { continue; } for (Integer prefix : prefixList) { List<Integer> suffixList = endCharDic.get(entry.getKey()); for (Integer suffix : suffixList) { // 相同字符 if (prefix.intValue() == suffix.intValue()) { continue; } String tmp = words.get(prefix) + words.get(suffix); if (checkStrIsHuiwen(tmp)) { List<Integer> group = new ArrayList<Integer>(); group.add(prefix); group.add(suffix); result.add(group); } } } } return result; } /** * 空字符串可以和任意字符串组成回文。 */ private void processBegEmpty(List<Integer> prefixList, Map<String, List<Integer>> endCharDic, List<String> words, List<List<Integer>> result) { for (Integer prefix : prefixList) { for (Map.Entry<String, List<Integer>> entry : endCharDic.entrySet()) { for (Integer suffix : entry.getValue()) { // 相同字符 if (prefix.intValue() == suffix.intValue()) { continue; } String tmp = words.get(prefix) + words.get(suffix); if (checkStrIsHuiwen(tmp)) { List<Integer> group = new ArrayList<Integer>(); group.add(prefix); group.add(suffix); result.add(group); } } } } } private void processEndEmpty(List<Integer> prefixList, Map<String, List<Integer>> endCharDic, List<String> words, List<List<Integer>> result) { for (Integer prefix : prefixList) { for (Integer suffix : endCharDic.get("")) { // 相同字符 if (prefix.intValue() == suffix.intValue()) { continue; } String tmp = words.get(prefix) + words.get(suffix); if (checkStrIsHuiwen(tmp)) { List<Integer> group = new ArrayList<Integer>(); group.add(prefix); group.add(suffix); result.add(group); } } } } /** * 判断一个字符串是否为回文。 需要考虑空字符串 */ private boolean checkStrIsHuiwen(String line) { // 空字符 if (line.length() == 0) { return true; } int left = 0; int right = line.length() - 1; while (left < right) { if (line.charAt(left) == line.charAt(right)) { left++; right--; continue; } else { return false; } } return true; } public static void main(String[] args) { HuiwenZuhe huiwenZuhe = new HuiwenZuhe(); List<String> input = Lists.newArrayList("bat", "tabv", "cadt"); List<List<Integer>> result = huiwenZuhe.palindromePairs(input); System.out.println(result); } } |
2 翻转
2.1 翻转单词
1、给定一个字符串，逐个翻转字符串中的每个单词。https://leetcode-cn.com/problems/reverse-words-in-a-string/
|
1 2 |
输入: "the sky is blue" 输出: "blue is sky the" |
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public String reverseWords(String s) { String[] array = s.split(" "); List<String> result = new ArrayList<String>(); for(String word : array){ word = word.trim(); if(word.length()>0) { result.add(word); } } StringBuilder stringBuilder = new StringBuilder(); for(int i=result.size()-1;i>=0;i--){ stringBuilder.append(result.get(i)); if(i!=0){ stringBuilder.append(" "); } } return stringBuilder.toString(); } } |
2.2 翻转字符串
方法1 使用双向指针空间O(1)
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public void reverseString(char[] s) { reverse(s,0,s.length-1); } public void reverse(char[] s,int beg,int right) { if(beg>=right){ return; } char temp = s[beg]; s[beg]=s[right]; s[right] = temp; reverse(s,beg+1,right-1); } } |
3 字符串比较
3.1 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
|
1 2 |
输入: ["flower","flow","flight"] 输出: "fl" |
链接：https://leetcode-cn.com/problems/longest-common-prefix/
算法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public String longestCommonPrefix(String[] strs) { if(strs==null || strs.length==0){ return ""; } if(strs.length == 1){ return strs[0]; } StringBuilder result = new StringBuilder(); String base = strs[0]; for(int i=0;i<base.length();i++){ for(int j=1;j<strs.length;j++){ String str = strs[j]; if(str.length() == i || str.charAt(i)!=base.charAt(i)){ return result.toString(); } } // 添加 result.append(base.charAt(i)+""); } return result.toString(); } } |
3.2 子序列
3.2.1 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。
示例 1:
s = “abc”, t = “ahbgdc”
返回 true.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-subsequence
算法
|
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 |
class Solution { public boolean isSubsequence(String s, String t) { if(s == null || t==null){ return false; } if(s.length() ==0){ return true; } // 循环最外层 int j=0; for(int i=0;i<s.length();i++){ boolean include = false; while(j<t.length()){ if(s.charAt(i)==t.charAt(j++)){ include = true; break; } } if(!include){ return false; } } return true; } } |
3.2.2 通过删除字母匹配到字典里最长单词
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
|
1 2 3 4 5 |
输入: s = "abpcplea", d = ["ale","apple","monkey","plea"] 输出: "apple" |
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting
算法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public String findLongestWord(String s, List<String> d) { int length = Integer.MIN_VALUE; String result = ""; for(String str:d){ if(isSubsequence(str,s)){ if(str.length()> length){ length = str.length(); result = str; }else if(str.length() == length){ // 字典顺序小的值 if(str.compareTo(result)<0){ result = str; } } } } return result; } public boolean isSubsequence(String s, String t) { 3.2.1判断子序列 } } |
3.3 最长子串
3.3.1 无重复最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
|
1 2 3 |
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 |
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
算法：
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Solution { public int lengthOfLongestSubstring(String s) { if (s.equals("") || s == null) { return 0; } Map<Byte, Integer> dic = new HashMap<Byte, Integer>(); byte[] input = s.getBytes(); // 结果 long max = 0; int beg = 0; int end = 0; int scanBeg = 0; int scanEnd = 0; for (int i = 0; i < s.length(); i++) { // 1. 出现重复字符 if (dic.containsKey(input[i])) { // 1.2更新dic int deleteEnd = dic.get(input[i]); for (int index = scanBeg; index <= deleteEnd; index++) { dic.remove(input[index]); } // 1.2更新scanBeg开始 scanBeg = deleteEnd + 1; } // 2.更新遍历信息 // 2.1更新scanEnd的索引值 scanEnd++; // 2.2更新dic dic.put(input[i], i); // 3更新结果 if (dic.size() > max) { // 1.1 更新结果 max = dic.size(); beg = scanBeg; end = scanEnd - 1; } } return end + 1 - beg; } } |
3.4 累加数
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。
|
1 2 3 |
输入: "199100199" 输出: true 解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199 |
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/additive-number
算法思想：
- 一个字符串，给定前两个数之后，判断是不是满足累加条件。check()
- 穷举第一个数和第二数使用 check()判断是否为累加数。
|
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 33 34 35 36 37 38 39 40 41 42 |
class Solution { public boolean isAdditiveNumber(String num) { if(num==null && num.length()<3){ return false; } // 穷举第1个字符串 for(int i=1;i<=num.length()/2;i++){ // 数字只是0开头,不能是0开头数字，比如012 if( i>1 && num.charAt(0)=='0') { break; } String sub1 = num.substring(0,i); // 穷举第2个字符串 for(int j=i+1;j<num.length();j++){ // 数字只是0开头,不能是0开头数字，比如012 if( j>i+1 && num.charAt(i)=='0') { break; } String sub2 = num.substring(i,j); if(check(num,sub1,sub2)){ return true; } } } return false; } // 给定前两个数之后，判断是不是满足累加条件 public boolean check(String num, String sub1, String sub2) { Long sum = Long.parseLong(sub1) + Long.parseLong(sub2); String remain = num.substring(sub2.length()+sub1.length()); if (!remain.startsWith(sum + "")) { return false; } if (remain.equals(sum + "")) { return true; } return check(num.substring(sub1.length()), sub2, sum + ""); } } |
4 运算
4.1 求和
4.1.1 加1
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
链接：https://leetcode-cn.com/problems/plus-one/
算法：
- 陷阱：只加1，不是每位加1。
- 加1之后，需要判断是否继续向下走
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public int[] plusOne(int[] digits) { int carry = 1; for (int i = digits.length - 1; i >= 0; i--) { digits[i] = digits[i]+carry; carry = digits[i]/10; digits[i] = digits[i]%10; if(carry==0){ return digits; } } if(carry>0){ int[] nd = new int[digits.length+1]; nd[0]=carry; for(int i=0 ;i<digits.length;i++){ nd[i+1] = digits[i]; } return nd; }else{ return digits; } } } |
4.1.2 二进制求和
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
|
1 2 |
输入: a = "11", b = "1" 输出: "100" |
链接：https://leetcode-cn.com/problems/add-binary/
算法：
|
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 |
class Solution { public String addBinary(String a, String b) { String result = ""; int i = a.length()-1; int j = b.length()-1; int carry = 0; while(i>=0 || j>=0 || carry>0){ int left = 0; int right = 0; if(i>=0){ left = Integer.parseInt(a.charAt(i)+""); i--; } if(j>=0){ right = Integer.parseInt(b.charAt(j)+""); j--; } int sum = left + right + carry; carry = sum/2; sum = sum%2; result= sum + result; } if(carry >0){ result = carry + result; } return result; } } |
4.1.3 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
链接：https://leetcode-cn.com/problems/add-strings/
算法：
|
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 |
public String addStrings(String num1, String num2) { int beg1 = num1.length() - 1; int beg2 = num2.length() - 1; int add = 0; StringBuilder result = new StringBuilder(); while (beg1 >= 0 || beg2 >= 0 || add > 0) { int left = 0; int right = 0; if (beg1 >= 0) { left = Integer.parseInt(num1.charAt(beg1) + ""); beg1--; } if (beg2 >= 0) { right = Integer.parseInt(num2.charAt(beg2) + ""); beg2--; } int sum = left + right; if (add > 0) { sum += add; } result.append(sum % 10 + ""); add = sum / 10; } return result.reverse().toString(); } |
4.2 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
链接：https://leetcode-cn.com/problems/multiply-strings/
算法：
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
class Solution { public String multiply(String num1, String num2) { int beg2 = num2.length() - 1; String result = "0"; StringBuilder zero = new StringBuilder(""); // 循环累加result的值 while (beg2 >= 0) { int down = Integer.parseInt(num2.charAt(beg2) + ""); beg2--; // 1.获取积 StringBuilder psb = new StringBuilder(); int carry = 0; int beg1 = num1.length() - 1; while (beg1 >= 0) { int up = Integer.parseInt(num1.charAt(beg1) + ""); beg1--; int productTwo = up * down; productTwo += carry; psb.append(productTwo % 10); carry = productTwo / 10; } // 追加进位 if (carry > 0) { psb.append(carry); } // 翻转结果 psb = psb.reverse(); // 2.追加0 psb.append(zero); zero.append("0"); // 3.累加 result = add(result, psb.toString()); } // 5.判断结果为0000 int i=0; for(;i<result.length();i++){ if(result.charAt(i)=='0'){ continue; }else{ break; } } if(i==result.length()){ return "0"; }else{ return result; } } public static String add(String num1, String num2) { int beg1 = num1.length() - 1; int beg2 = num2.length() - 1; int add = 0; StringBuilder result = new StringBuilder(); while (beg1 >= 0 || beg2 >= 0 || add > 0) { int left = 0; int right = 0; if (beg1 >= 0) { left = Integer.parseInt(num1.charAt(beg1) + ""); beg1--; } if (beg2 >= 0) { right = Integer.parseInt(num2.charAt(beg2) + ""); beg2--; } int sum = left + right; if (add > 0) { sum += add; } result.append(sum % 10 + ""); add = sum / 10; } return result.reverse().toString(); } } |
4.3 两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
链接：https://leetcode-cn.com/problems/divide-two-integers/
算法:
|
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 33 34 35 36 37 |
class Solution { public int divide(int dividend, int divisor) { if (divisor == 0) { throw new RuntimeException("dividend error"); } if (dividend == 0) { return 0; } if (dividend == divisor) { return 1; } if (divisor == 1) { return dividend; } if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } long dividend1 = Math.abs((long) dividend); long divisor1 = Math.abs((long) divisor); // 结果 long ans = 0; while(dividend1>=divisor1){ dividend1 -=divisor1; ans++; } if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) ans = -ans; return (int)ans; } } |
4.4 数字和字符串转换
给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（”Gold Medal”, “Silver Medal”, “Bronze Medal”）。
(注：分数越高的选手，排名越靠前。)
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/relative-ranks
|
1 2 3 4 |
输入: [5, 4, 3, 2, 1] 输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"] 解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal"). 余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。 |
代码：
|
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 33 |
class Solution { public String[] findRelativeRanks(int[] nums) { if(nums==null || nums.length==0){ return new String[0]; } PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){ public int compare(Integer o1 , Integer o2){ return nums[o2] - nums[o1]; } }); for(int i=0; i<nums.length;i++){ pq.add(i); } String[] result = new String[nums.length]; for(int i=0;i<nums.length;i++){ // i+1 String name = i + 1+""; if(i==0){ name ="Gold Medal"; }else if(i==1){ name ="Silver Medal"; } else if(i==2){ name ="Bronze Medal"; } result[pq.poll()] =name; } return result; } } |
5 字符串匹配
5.1 实现strStr()
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
|
1 2 |
输入: haystack = "hello", needle = "ll" 输出: 2 |
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
算法： 使用单词移动，比较字符串
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { // 使用单词移动 public int strStr(String haystack, String needle) { // 条件判断 if (haystack == null || needle == null) { return -1; } else if (needle.length() == 0 && haystack.length() == 0) { return 0; } else if (needle.length() == 0) { return 0; } int j = 0; while (j <= haystack.length() - needle.length()) { String temp =haystack.substring(j, j+needle.length()); if (temp.equals(needle)) { return j; } j++; } return -1; } } |
6 字符串统计
6.1 字符串中单词个数
统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
|
1 2 3 |
输入: "Hello, my name is John" 输出: 5 解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。 |
链接：https://leetcode-cn.com/problems/number-of-segments-in-a-string/
算法：
|
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 33 34 |
class Solution { public int countSegments(String s) { if(s==null || s.length()==0){ return 0; } // 类似可重入的值 boolean isEmpty = false; int count =0; // 根据第一个节点初始这个值 if(s.charAt(0) == ' '){ isEmpty = true; }else { count =1; } for(int i=0;i<s.length();i++){ if(s.charAt(i) == ' ' ){ if(!isEmpty) { isEmpty = true; }else { continue; } }else { if(isEmpty){ count++; isEmpty = false; } } } return count; } } |
