常规字符串，数组，矩阵
1 实现超长数字减1
- 思路：Java中用BigInteger类
public String subOne(String s){
BigInteger bi = new BigInteger(s);
bi = bi.subtract(BigInteger.ONE);
return bi.toString();
}
2 十八进制数比较大小
任意进制的字符串a，转成十进制的数 ： Integer aTen = Integer.valueOf(a, 任意进制)
十进制的数aTen，转成任意进制的字符串 ：String str = Integer.toString(aTen, 任意进制)
public String compareTenEight20241020(String a, String b){
Integer aten = Integer.valueOf(a, 18);
Integer bten = Integer.valueOf(b, 18);
return aten > bten ? a : b;
}
3 最长公共前缀
思想：取第一个字符串作为前缀，然后遍历数组中的每个字符串，不断缩小前缀长度，直到它匹配字符串的前缀为止
public String longestCommonPrefix(String[] strs) {
int n = strs.length;
String prefix = strs[0];
for (int i = 1; i < n; i ++){
String cur = strs[i];
//如果当前字符串不是以prefix开头，则不断缩小prefix的长度，直到它匹配当前字符串的前缀为止
while (cur.indexOf(prefix) != 0){
prefix = prefix.substring(0, prefix.length() - 1);
}
}
return prefix;
}
4 八进制求和
不难想到用Integer类提供的方法，但当a，b过长超出Integer型范围时会报错。
public String addBinary(String a, String b) { //会超时
int aten = Integer.valueOf(a,2);
int bten = Integer.valueOf(b,2);
int sum = aten + bten;
return Integer.toString(sum,2);
}
还得用常规运算
//二进制求和
public String addBinary(String a, String b) {
int aLen = a.length();
int bLen = b.length();
int i = aLen - 1;
int j = bLen - 1;
StringBuilder sb = new StringBuilder();
int jw = 0; //表示进位
//从a，b末尾开始运算
while (i >= 0 || j >= 0){
int sum = jw;
//若a还有数字
if (i >= 0){
sum += a.charAt(i) - '0';
i --;
}
//若b还有数字
if (j >= 0){
sum += b.charAt(j) - '0';
j --;
}
//考虑进位
jw = sum / 2;
sb.insert(0,sum % 2);
if (i < 0 && j < 0 && jw > 0){
sb.insert(0,jw);
}
}
return sb.toString();
}
八进制求和代码类似上面二进制求和
//八进制求和
public static String addEightJZ(String a, String b){
int aLen = a.length();
int bLen = b.length();
int i = aLen - 1;
int j = bLen - 1;
int jw = 0; //表示进位
StringBuilder sb = new StringBuilder();
while (i >=0 || j >= 0){
int sum = jw;
if (i >= 0){
sum += a.charAt(i) - '0';
i --;
}
if (j >= 0){
sum += b.charAt(j) - '0';
j --;
}
//sum % 8表示当前位置值， sum / 8表示进位
jw = sum / 8; //进位
sb.insert(0, sum % 8);
//如果当前是最高位，且进位大于0 则把进位也加进去
if (i < 0 && j < 0 && jw > 0){
sb.insert(0,jw);
}
}
return sb.toString();
}
5 O(n)时间内求和为target两个数
思路：用hashmap
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
//map存放<nums[i],i> 也就是<值,下标>
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < n; i ++){
int cur = nums[i];
int other = target - nums[i];
//看other是否在map中 在则直接返回
if (map.containsKey(other)){
return new int[]{i,map.get(other)};
}
map.put(cur, i);
}
return new int[2];
}
6 判断回文串
public boolean isPalindrome(String s) {
//将所有大写字母转为小写字母
s = s.toLowerCase();
//知识点：s.toUpperCase();//将所有小写字母转为大写字母
//将所有非小写字母 数字字符替换成空字符（移除所有非小写字母 数字字符）
s = s.replaceAll("[^0-9a-z]","");
int n = s.length();
int left = 0, right = n - 1;
while(left < right){
char lc = s.charAt(left);
char rc = s.charAt(right);
if (lc != rc) return false;
left ++;
right --;
}
return true;
}
7 字母异位词分组
public List<List<String>> groupAnagrams(String[] strs) {
int n = strs.length;
//map中 key为排序后的字符串，value排序前的字符串
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < n; i ++ ){
String str = strs[i];
//将str进行排序变成key的过程
char[] chars = str.toCharArray();
Arrays.sort(chars);
// String key = chars.toString(); 这个不行
String key = new String(chars); //这个可以
//若map包含key 则将str直接加入
if (map.containsKey(key)){
map.get(key).add(str);
}
else{ //否则新建一个list，将str加到list 组成键值对<key ,list>加到map中
List<String> list = new ArrayList<>();
list.add(str);
map.put(key, list);
}
}
return new ArrayList<>(map.values());
}
8分发糖果
思路：两次循环，第一次从左到右遍历 若右边的孩子比左边孩子评分高，则右孩子糖数为左孩子糖+1，否则为1。第二次从右到左遍历 若左边孩子比右边孩子评分高，则左边孩子糖 = max(左孩子第一轮糖，右孩子糖 + 1)
public int candy(int[] ratings) {
int n = ratings.length;
int[] candy = new int[n]; //candy[i] 表示第i个孩子收到的糖数
candy[0] = 1; //初始化
int cnt = 0; //用来统计糖总数
//从左往右遍历 若右孩子评分比左孩子高则右孩子糖数 = 左孩子糖数 + 1,否则右孩子糖数为1
for (int right = 1; right < n; right ++){
int leftCandy = candy[right - 1];
int leftRate = ratings[right - 1];
int rightRate = ratings[right];
if (rightRate > leftRate) {
candy[right] = leftCandy + 1; //若右孩子评分比左孩子高则右孩子糖数 = 左孩子糖数 + 1
}else{
candy[right] = 1;//否则右孩子糖数为1
}
}
//从右往左遍历 若左孩子评分比右孩子高 左孩子糖数 = max（左孩子糖数，右孩子糖数 + 1）
for (int left = n - 2; left >= 0; left --){
int rightRate = ratings[left + 1];
int rightCandy = candy[left + 1];
int leftRate = ratings[left];
if (leftRate > rightRate){
candy[left] = Math.max(candy[left], rightCandy + 1);
}
}
//统计糖总数
for (int a : candy){
cnt += a;
}
return cnt;
}
9 计算字符串的数字和
2243. 计算字符串的数字和 - 力扣（LeetCode）
public String digitSum(String s, int k) {
//递归终止条件
if (s.length() <= k) return s;
int n = s.length();
StringBuilder sb = new StringBuilder(); //记录变化中的字符串
//i以k位间隔
for (int i = 0; i < n; i += k){
int num = 0;
for (int j = 0; j < k && i + j < n; j ++){
char c = s.charAt(i + j);
num += c - '0';
}
sb.append(num);
}
return digitSum(sb.toString(), k);
}
2 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int start = binsearch(nums, target);
if (start == n || nums[start] != target){
return new int[]{-1, -1};
}
int end = binsearch(nums, target + 1) - 1;
return new int[]{start,end};
}
//闭区间二分查找
public int binsearch(int[] nums, int target){
int n = nums.length;
int left = 0, right = n - 1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return left;
}
10 字符串压缩
面试题 01.06. 字符串压缩 - 力扣（LeetCode）
public String compressString(String S) {
int n = S.length();
//用来记录字符以及次数
Map<Character, Integer> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i ++){
char c = S.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
if (i > 0){ //i > 0确保左边有字符
char lc = S.charAt(i - 1); //拿到左边字符
if (lc != c){ //若c左边的字符不等于c 则将左边的字符以及个数存到sb中
sb.append(lc).append(map.get(lc));
map.put(lc,0);
}
}
//若到了最后字符
if (i == n - 1){
sb.append(c).append(map.get(c));
}
}
//sb S 哪个短返回哪个
return sb.length() < n ? sb.toString() : S;
}
11 判断是ipv4还是ipv6地址
正常解法
public String validIPAddress(String queryIP) {
if (isIPv4(queryIP)){
return "IPv4";
}else if (isIPv6(queryIP)){
return "IPv6";
}else{
return "Neither";
}
}
public boolean isIPv4(String ip){
String[] split = ip.split("\\.");
//若分割后的数组长度不为4，则不是ipv4地址
if (split.length != 4 || ip.charAt(ip.length() - 1) == '.'){
return false;
}
//遍历分割后的每个数，是否符合Ipv4的要求
for (String s : split) {
//IP为172.16.254.1 则s分别代表172 16 254 1
//1、若s的长度为0或者大于3，则不是ipv4地址
if (s.length() == 0 || s.length() > 3){
return false;
}
//2、判断首位0是否合理。172.16.254.01 不是ipv4地址，但172.0.0.1是ipv4地址
if (s.charAt(0) == '0' && s.length() != 1){
return false;
}
//3、判断是否为数字
for (int i = 0; i < s.length(); i++) {
if (!Character.isDigit(s.charAt(i))){
return false;
}
}
//4、判断是否在0~255之间（经3之后得知是数字）
int sint = Integer.parseInt(s);
if (sint < 0 || sint > 255){
return false;
}
}
//若上述都满足则返回true
return true;
}
public boolean isIPv6(String ip){
if (ip.contains("::")){
return false;
}
String[] split = ip.split(":");
//若分割后的数组长度不为8，则不是ipv6地址
if (split.length != 8 || ip.charAt(ip.length() - 1) == ':'){
return false;
}
//遍历分割后的每个数，判断每个数的长度是否小于等于4，是否为16进制数
for (String s : split) {
//"2001:0db8:85a3:0:0:8A2E:0370:7334" 是ipv6地址
//s分别代表2001 0db8 85a3 0 0 8A2E 0370 7334
//1、若s的长度大于4，则不是ipv6地址
if (s.length() > 4){
return false;
}
//2、判断是否为16进制数
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!Character.isDigit(c) && (c < 'a' || c > 'f') && (c <'A' || c > 'F')){
return false;
}
}
}
return true;
}
正则表达式解法 (如何写出来的待学习)
public String validIPAddress(String queryIP) {
String ipv4Pattern = "((2(5[0-5]|[0-4]\\d))|(1([0-9][0-9]))|[1-9][0-9]?|[0-9])(.((2(5[0-5]|[0-4]\\d))|(1([0-9][0-9]))|[1-9][0-9]?|[0-9])){3}";
String ipv6Pattern = "([0-9a-fA-F]{1,4})(:[0-9a-fA-F]{1,4}){7}";
if(queryIP.indexOf(".") > 0 && (queryIP.matches(ipv4Pattern))){
return "IPv4";
}
if(queryIP.indexOf(":") > 0 && (queryIP.matches(ipv6Pattern))){
return "IPv6";
}
return "Neither";
}
12旋转矩阵旋转90度
面试题 01.07. 旋转矩阵 - 力扣（LeetCode）
思路：先转置，再沿着中间列翻转
public void rotate(int[][] matrix) {
int n = matrix.length;
//1转置 a[i][j] = a[j][i]
for (int i = 0; i < n; i ++){
for (int j = 0; j < i; j ++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
//2 沿着中间列倒转 a[i][j] = a[i][n - j - 1] 当j=0时 a[i][0] = a[i][n - 1]
for(int i = 0; i < n; i ++){
for (int j = 0; j < n / 2; j ++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = tmp;
}
}
}