sLeetCode笔记
10-10 LeetCode_9回文数
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aobF1ApE-1668064348453)(C:\Users\DELL\Desktop\LeetCode\001.png)]
// 方法1：将整数转为字符串,前后指针循环
public boolean isPalindrome(int x) {
//1.判断x<0 负数不肯是回文数
if (x < 0) {
return false;
}
//2. 转化字符串
String s = x + "";
//3.定义左右指针
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
// 数字最大数21亿反转71亿
public boolean isPalindrome3(int x) {
// 特殊情况：
// 如上所述，当 x < 0 时，x 不是回文数。
// 同样地，如果数字的最后一位是 0，为了使该数字为回文，
// 则其第一位数字也应该是 0
// 只有 0 满足这一属性
// x%10 取一个，不要一个x/10
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
return x == revertedNumber || x == revertedNumber / 10;
}
10-11 LC20 有效地括号
class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return false;
}
//1.把字符串转成字符数组
char[] str = s.toCharArray();
//2.声明一个Stack
Stack<Character> stack = new Stack<>();
//3.遍历配对
for (int i = 0; i < str.length; i++) {
char cha = str[i];
if (cha == '(' || cha == '[' || cha == '{') {
//3.1 如果是3个括号，配对
stack.add(cha == '(' ? ')' : (cha == '[' ? ']' : '}'));
} else {
//3.2 如果stack为空，不对
if (stack.isEmpty()) {
return false;
}
//3.3 不为空，说明配对成功，弹出
char last = stack.pop();
if (cha != last) {
return false;
}
}
}
return stack.isEmpty();
}
}
10-11 LC20 有效地括号（法2）
https://www.bilibili.com/video/BV1J3411n7kU?p=2
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uevjStur-1668064348456)(C:\Users\DELL\AppData\Roaming\Typora\typora-user-images\image-20221013093703839.png)]
10-13 LC13罗马To数字
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZpHMIOiC-1668064348456)(file:///C:\Users\DELL\AppData\Roaming\Tencent\Users\776804258\QQ\WinTemp\RichOle\IF2LC~A%ZMTZ8@Y@5H]T{PX.png)]
class Solution {
public int romanToInt(String s) {
//1. 判断长度为0
if (s.length() == 0) {
return 0;
}
//2声明Map并赋值
Map<Character, Integer> map = init();
//3取出第一个字符
int sum = map.get(s.charAt(0));
//4.比较大小
for (int i = 1; i <s.length() ; i++) {
char curRoman=s.charAt(i);
int curInt=map.get(curRoman);
char lastRoman=s.charAt(i-1);
int lastInt=map.get(lastRoman);
sum+=curInt;
if(curInt>lastInt){
sum=sum-2*lastInt;
}
}
return sum;
}
public Map<Character, Integer> init() {
Map<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
return map;
}
}
10-14 冒泡排序
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UaHDF4u8-1668064348457)(file:///C:\Users\DELL\AppData\Roaming\Tencent\Users\776804258\QQ\WinTemp\RichOle\4KS~4G{[WG582$4YIXA%4P9.png)]
package day04;
import java.util.Arrays;
//冒泡排序
public class BubbleDemo {
public static void main(String[] args) {
//int[] arr = {8,4,2,1,23,344,12};
int[] arr = {4,6,3,7,8,9,10};
//未优化
//sort1(arr);
//优化1 针对比较轮数进行优化
//sort2(arr);
//优化2 针对比较次数进行优化
sort3(arr);
}
//未优化 冒泡排序
public static void sort1(int[] arr) {
for (int i = 0; i <arr.length-1; i++) { //i 轮数
System.out.println("目前是第"+(i+1)+"轮比较");
for (int j = 0; j <arr.length-1-i ; j++) { //j 次数
System.out.println("第"+(i+1)+"轮，第"+(j+1)+"次比较");
//交换的条件
if(arr[j] > arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
//输出当前轮次比较的结果
System.out.println(Arrays.toString(arr));
}
//输出
System.out.println("排序后："+Arrays.toString(arr));
}
//优化1 针对比较轮数进行优化 冒泡排序
public static void sort2(int[] arr) {
for (int i = 0; i <arr.length-1; i++) { //i 轮数
System.out.println("目前是第"+(i+1)+"轮比较");
//标志位
boolean flag = true;
for (int j = 0; j <arr.length-1-i ; j++) { //j 次数
System.out.println("第"+(i+1)+"轮，第"+(j+1)+"次比较");
//交换的条件
if(arr[j] > arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
flag = false;
}
}
//输出当前轮次比较的结果
System.out.println(Arrays.toString(arr));
//当不再发生交换时，则结束比较
if(flag){
break;
}
}
//输出
System.out.println("排序后："+Arrays.toString(arr));
}
//优化2 针对比较次数进行优化 冒泡排序
public static void sort3(int[] arr) {
//定义一个作为比较的边界
int position = arr.length-1;
for (int i = 0; i <arr.length-1; i++) { //i 轮数
System.out.println("目前是第"+(i+1)+"轮比较");
//标志位
boolean flag = true;
//记录最后交换位置的值
int limit = 0;
for (int j = 0; j <position ; j++) { //j 次数
System.out.println("第"+(i+1)+"轮，第"+(j+1)+"次比较");
//交换的条件
if(arr[j] > arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
flag = false;
limit = j;
}
}
position = limit;
//输出当前轮次比较的结果
System.out.println(Arrays.toString(arr));
//当不再发生交换时，则结束比较
if(flag){
break;
}
}
//输出
System.out.println("排序后："+Arrays.toString(arr));
}
}
10-14 二分查找
package day04;
import java.util.Arrays;
import java.util.Scanner;
//练习2：有一个数列：8,4,2,1,23,344,12，此时从键盘中任意输入一个数据，判断数列中是否包含此数
//方法二：先冒泡排序，再折半查找出是否包含
public class BinaryDemo {
public static void main(String[] args) {
int[] arr = {8,4,23,2,1,23,344,12};
//冒泡排序
for (int i = 0; i <arr.length-1; i++) { //i 轮数
for (int j = 0; j <arr.length-1-i ; j++) { //j 次数
//交换的条件
if(arr[j] > arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
//输出
System.out.println("排序后："+Arrays.toString(arr));
//二分搜索法
Scanner scanner = new Scanner(System.in);
System.out.println("请输入搜索数据：");
int key = scanner.nextInt();
int left = 0;
int right = arr.length-1;
int middle = 0;
boolean flag = true;
while (left <= right){
middle = (left + right)/2;
if(key > arr[middle]){
//看右边
left = middle + 1;
}else if(key < arr[middle]){
//看左边
right = middle - 1;
}else if(key == arr[middle]){
flag = false;
System.out.println("存在");
break;
}
}
if(flag){
System.out.println("不存在");
}
}
}
10-14 LC12数字转罗马
public static String intToRoman(int num) {
//I 1
//V 5
//X 10
//L 50
//C 100
//D 500
//M 1000
String[] qian = {"", "M", "MM", "MMM"};
String[] bai = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
String[] shi = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
String[] ge={"","I","II","III","IV","V","VI","VII","VIII","IX"};
return qian[num/1000] +bai[num/100%10]+shi[num%100/10]+ge[num%10];
}
优化版
class Solution {
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
public String intToRoman(int num) {
StringBuffer roman = new StringBuffer();
for (int i = 0; i < values.length; ++i) {
int value = values[i];
String symbol = symbols[i];
while (num >= value) {
num -= value;
roman.append(symbol);
}
if (num == 0) {
break;
}
}
return roman.toString();
}
}
LC 704. 二分查找
package day0;
public class LC704_binarySerach {
public int search(int[] nums, int target) {
//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
LC 278. 第一个错误的版本
package day0;
public class LC278_binarySeracher第一个错误的版本 {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) { // 循环直至区间左右端点相同
int mid = left + (right - left) / 2; // 防止计算时溢出
if (!isBadVersion(mid)) {
// 不是坏的，就是好的
// 1好的 2好的 3好的 4坏的 5坏的
return left=mid+1;
} else {
// 就是坏的 继续向前面看，有没有好的,，不能-1 如果3是坏的 2也是坏的 （1+2）/2=1 1是好的，全部都是好的，结果把2跳过了，好的中有一个坏的
return right=mid;
}
}
// 返回最最左边好的
return left;
}
}
LC 35 搜索插入位置
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
LC997有序数组的平方
// 方法1最简单的方法就是将数组 nums 中的数平方后直接排序
//时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。
//空间复杂度：O(logn)。除了存储答案的数组以外，我们需要O(logn) 的栈空间进行排序。
class Solution {
public int[] sortedSquares(int[] nums) {
int[] newArray=new int [nums.length];
for(int i=0;i<nums.length;i++){
newArray[i]=nums[i]*nums[i];
}
Arrays.sort(newArray);
return newArray;
}
}
@LC1295统计位数为偶数的数字22-10–27
class Solution {
public int findNumbers(int[] nums) {
int count=0;
//1.遍历数组
for(int i=0;i<nums.length;i++){
//3.判断偶数
if(fib( nums[i] ) %2 ==0){
count++;
}
}
return count;
}
//2.判断位数
public int fib(int n){
int count=0;
while(n>0){
n/=10;
count++;
}
return count;
}
}
class Solution {
public int findNumbers(int[] nums) {
int count=0;
for(int i=0;i<nums.length;i++){
// valueof()类型转换
String a=String.valueOf(nums[i]);
if(a.length()%2==0){
count++;
}
}
return count;
}
}
LC1832. 判断句子是否为全字母句
public static boolean checkIfPangram(String sentence) {
// 1.定义数组用于记录改变过的值，只要有26个字母，每一个都会改成-1，否则就是默认值0
int[] count=new int[26];
//2.把string sentence 变成字符数组，遍历拿到一个个元素
for (char i:sentence.toCharArray()){
//abc
//97-97 =0 -1
//98-97=1 -1
// 2拿到数组下标，将值改-1
count[i-'a']--;
}
for (int i = 0; i < 26; i++) {
//数组下标的值，等于0 说明没改
if(count[i]==0){
return false;
}
}
//说明改了，有这个字母
return true;
}
LC283 移动0和LC 27 方法一样
这个录得有视频
// 双指针方法
public void moveZeroes(int[] nums) {
//1.判断边界
if(nums==null){
return;
}
// j记录0的值 和交换数值
int j=0;
for (int i = 0; i < nums.length; i++) {
if(nums[i]!=0){
nums[j++]=nums[i];
}
}
// j中0的位置 放到最后 5个元素，j=4 支循环2次
for (int i = j; i <nums.length ; i++) {
nums[i]=0;
}
}
LC27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
public int removeElement(int[] nums, int val) {
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
nums[j++]=nums[i];
}
}
return j;
}
LC 344. 反转字符串 双针针解法
public void reverseString(char[] s) {
int n=s.length;
// a b c d e
i j
i j
//，假设反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] ... s[0]。
for(int i=0,j=n-1;i<j;i++,j--){
char temp=s[i];
s[i]=s[j];
s[j]=temp;
}
}
LC 344. 字符串反转
private static void fib4() {
//练习4：字符串反转
String str="abcdefg";
//1.把字符串转成字符数组
char[] ch = str.toCharArray();
//2.借用辅助空间
char[] char1= new char[ch.length];
//3.数组反转
for (int i = 0,j=ch.length-1; i <ch.length ; i++) {
char1[j--]=ch[i];
}
//4字符数组转成字符串
String str2 = new String(char1);
System.out.println(str2);
}
@10-20-LC80. 删除有序数组中的重复项 II
public int removeDuplicates(int[] nums) {
int j=2,i=2;
for(i=2;i<nums.length;i++){
//如果快指针和满指针-2下标处值不一样
//1快指针的值赋给满指针，同时++
// 2如果一样 满指针不懂，快指针移动 继续重复1
if(nums[j-2]!=nums[i]){
nums[j++]=nums[i];
}
}
return j;
}
10-20-LC26删除有序数组中的重复项
public int removeDuplicates(int[] nums) {
int i=0;
int j=0;
for(i=0;i<nums.length;i++){
// 如果i所在位置的值，不等于j所在位置的值
if(nums[j]!=nums[i]){
//2.j位置后面的值改成nums[i]的值
//3.j向后移动继续比较，相同跳过，不相同继续
nums[++j]=nums[i];
}
}
return j+1;
}
第二部分：哈希表
@1021—LC349. 两个数组的交集-set
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1==null || nums1.length==0 || nums2==null ||nums2.length==0){
return new int[0];
}
Set <Integer> set1=new HashSet<>();
Set <Integer> result=new HashSet<>();
//把数组1的元素放进去，自动去重
for(int i:nums1){
set1.add(i);
}
//把数组2和数组1重复的元素放到result
for(int i:nums2){
if(set1.contains(i)){
result.add(i);
}
}
// 集合转数组的方法1 慢很多
//return result.stream().mapToInt(x->x).toArray();
//定义一个数组，数组取遍历集合
int[] arr=new int[result.size()];
int index=0;
for(int i:result){
arr[index++]=i;
}
return arr;
}
}
1021-LC242. 有效的字母异位词-哈希数组
class Solution {
public boolean isAnagram(String s, String t) {
//利用数组下标方法
int hasp[]=new int[26];
// 第一个数组有就加
for(int i=0;i<s.length();i++){
hasp[s.charAt(i)-'a']++;
}
// 第二个数组有就加
for(int j=0;j<t.length();j++){
hasp[t.charAt(j)-'a']--;
}
// 两个字符串相同，一加一减值=0
for(int k=0;k<hasp.length;k++){
if(hasp[k]!=0){
return false;
}
}
return true;
}
}
1021-LC217存在重复元素-Set
class Solution {
// 思路1：排序后排序前后是否重复
/*
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i <nums.length-1; i++) {
if(nums[i]==nums[i+1]){
return true;
}
}
return false;
}
*/
public boolean containsDuplicate(int[] nums) {
Set<Integer> set =new HashSet<>();
for(int x:nums){
if(!set.add(x)){
return true;
}
}
return false;
}
}
10-21-LC219存在重复元素2-滑动窗口
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set =new HashSet<>();
for(int i=0;i<nums.length;i++){
//找到了重复的元素
if(set.contains(nums[i])){
return true;
}
//没找到就加入set中 扩大窗口
set.add(nums[i]);
//滑动窗口超过了指定大小，缩小窗口
if(set.size()>k){
set.remove(nums[i-k]);
}
}
return false;
}
}
@10-22-LC202快乐数-哈希
package day0;
import java.util.HashSet;
import java.util.Set;
/**
* @Description TODO
* @Author 李国勇
* @Date 2022/10/22 22:46
*/
public class LC205_快乐数 {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while (n != 1 && !set.contains(n)) {
set.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n) {
int sum = 0;
while (n > 0) {
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
}
10-22-LC15三数之和+哈希去重
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
// 如果三数之和>0,第一个数》0结束
if(nums[i]>0){
return result;
}
// 对a去重
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int left=i+1;
int right=nums.length-1;
while(right>left){
int sum=nums[i]+nums[left]+nums[right];
if(sum>0){
right--;
}
else if(sum<0){
left++;
}
else{
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
// 对b，c进行去重
while(right>left && nums[right]==nums[right-1]){
right--;
}
while(right>left && nums[left]==nums[left+1]){
left++;
}
right--;
left++;
}
}
}
return result;
}
}
@10-23-LC645. 错误的集合
package day0;
import java.util.Arrays;
/**
* @Description TODO
* @Author 李国勇
* @Date 2022/10/23 9:47
*/
public class LC645_n数组重复一个元素 {
//bug 前提必须从1开始，连续的，重复的重现2次
// 数组记录重现出现2次和出现0次的
public static void main(String[] args) {
int nums[]={1,2,2};
System.out.println(findErrorNums(nums));
}
public static String findErrorNums(int[] nums) {
int n=nums.length;
int[] copy=new int[n+1];
int[] ans=new int[2];
for(int i=0;i<nums.length;i++){
copy[nums[i]]++;
}
for(int i=1;i<=n;i++){
if(copy[i]==0) {
ans[1]=i;
}
if(copy[i]==2) {
ans[0]=i;
}
}
return Arrays.toString(ans);
}
}
10-23-LC1768交替合并字符串
class Solution {
public String mergeAlternately(String word1, String word2) {
int m=word1.length();
int n=word2.length();
int i=0,j=0;
StringBuilder ans=new StringBuilder();
while(i<m||j<n){
if(i<m){
ans.append(word1.charAt(i));
i++;
}
if(j<n){
ans.append(word2.charAt(j));
j++;
}
}
return ans.toString();
}
}
10-23-LC454四数相加2(四个数组)
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
int temp;
int res = 0;
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
temp = i + j;
if (map.containsKey(temp)) {
map.put(temp, map.get(temp) + 1);
} else {
map.put(temp, 1);
}
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
temp = i + j;
if (map.containsKey(0 - temp)) {
res += map.get(0 - temp);
}
}
}
return res;
}
}
10-23-LC18四数之和
package day0;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @Description TODO
* @Author 李国勇
* @Date 2022/10/23 16:23
*/
public class LC18四数之和 {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// nums[i] > target 直接返回, 第一次剪枝操作
if (nums[i] > 0 && nums[i] > target) {
return result;
}
//第一次去重操作
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
// 第二次剪枝去重
if (j > i + 1 && nums[j - 1] == nums[j]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (right > left && nums[right] == nums[right - 1]) {
right--;
}
while (right > left && nums[left] == nums[left + 1]) {
left++;
}
left++;
right--;
}
}
}
}
return result;
}
}
10-23-LC18四数之和-官方题解
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4) {
return quadruplets;
}
Arrays.sort(nums);
int length = nums.length;
for (int i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for (int j = i + 1; j < length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int left = j + 1, right = length - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
}
第三部分：字符串
10-23-LC344. 反转字符串
class Solution {
public static void reverseString(char[] s) {
int len=s.length;
for(int i=0,j=s.length-1;i<len/2;i++,j--){
char temp=s[i];
s[i]=s[j];
s[j]=temp;
}
}
}
10-23-LC541. 反转字符串2–有三种解法
package day0;
/**
* @Description TODO
* @Author 李国勇
* @Date 2022/10/23 19:47
*/
public class LC541_反转字符串2 {
public static void main(String[] args) {
String s="abcdefxy";
System.out.println(reverseStr(s, 3));
}
public static String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
// 1. 每隔 2k 个字符的前 k 个字符进行反转===6个
for (int i = 0; i < ch.length; i = i + 2 * k) {
// 2. if剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符===3个
if (i + k <= ch.length) {
reverse(ch, i, i + k - 1);
continue;
}
// 2. else剩余字符少于 k 个，则将剩余字符全部反转 只剩2个
reverse(ch, i, ch.length - 1);
}
return new String(ch);
}
private static void reverse(char[] ch, int i, int j) {
for(; i<j;i++,j--){
char temp=ch[i];
ch[i]=ch[j];
ch[j]=temp;
}
}
}
10-23-LC151. 反转字符串中的单词
package day0;
/**
* @Description TODO
* @Author 李国勇
* @Date 2022/10/23 22:13
*/
public class LC151_反转字符串中的单词 {
public static void main(String[] args) {
System.out.println(reverseWords(" he wo "));
}
public static String reverseWords(String s) {
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
private static void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length() - 1;
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
// 2.反转整个字符串
private static void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
private static StringBuilder removeSpace(String s) {
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') {
start++;
}
while (s.charAt(end) == ' ') {
end--;
}
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.length() - 1 != ' ') {
sb.append(c);
}
start++;
}
return sb;
}
}
@10-25-LC1662. 检查两个字符串数组是否相等
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
StringBuilder s1=new StringBuilder();
StringBuilder s2=new StringBuilder();
for (int i = 0; i < word1.length; i++) {
s1.append(word1[i]);
}
for (int i = 0; i < word2.length; i++) {
s2.append(word2[i]);
}
return s1.toString().equals(s2.toString());
}
@10-27-LC1822元素累积的符号
class Solution {
public int arraySign(int[] nums) {
int flag=1;
for(int i:nums){
if(i==0){
return 0;
}
if(i<0){
flag=-flag;
}
}
return flag;
}
}
10-29-LC200-DFS
class Solution {
public void dfs(char[][] grid,int i,int j){
int row=grid.length;
int col=grid[0].length;
if(i<0 || j<0 || i >=row || j >=col ||grid[i][j]=='0'){
return;
}
grid[i][j]='0';
dfs(grid,i-1,j);
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
}
public int numIslands(char[][] grid) {
if(grid == null && grid.length==0){
return 0;
}
int row=grid.length;
int col=grid[0].length;
int result=0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j]=='1'){
result++;
dfs(grid,i,j);
}
}
}
return result;
}
}
i++){
for(int j=0;j<col;j++){
if(grid[i][j]==‘1’){
result++;
dfs(grid,i,j);
}
}
}
return result;
}
}
本文含有隐藏内容，请 开通VIP 后查看