头像

越自律越自由




离线:3个月前


活动打卡代码 LeetCode 9. 回文数

双指针遍历,不是最好的方法

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) return false;
        String s=Integer.toString(x);
        int i=0,j=s.length()-1;
        while(i<j){
            if(s.charAt(i)!=s.charAt(j)) return false;
            i++;j--;
        }
        return true;
    }
}


活动打卡代码 LeetCode 7. 整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。其数值范围为 [−231, 231 − 1]

class Solution {
    public int reverse(int x) throws NumberFormatException{
        //无法变为正的2^31,先单独处理
        if(x==Math.pow(-2,31)) return 0;
        String s="";
        if(x<0) s="-"+s;
        //去除-后记得取绝对值
        x=Math.abs(x);
        while(x/10>0){
            s+=x%10;
            x=x/10;
        }
        s+=x%10;
        double d=Double.valueOf(s);
        if(d>Math.pow(2,31)-1 || d<Math.pow(-2,31)) return 0;
        else  return Integer.valueOf(s);
    }
}


活动打卡代码 LeetCode 6. Z 字形变换

取模和处理换行的时候需要注意边界

int n=s.length(),sum=1,row=0,col=0;
        if(numRows==1) return s;
        char[][] p=new char[numRows][n];
        for(int i=0;i<numRows;i++){
            for(int j=0;j<n;j++){
               p[i][j]=' ';
            }
        }
        for(int i=0;i<n;i++){
            //需要减一
            if(col%(numRows-1)==0) {
                p[row][col]=s.charAt(i);
                row++;
                //需要减一
                if(row>numRows-1) {row=0;col++;sum=1;}
            }else{
                //需要减一
                p[numRows-1-sum][col]=s.charAt(i);
                col++;sum++;
                row=0;
            }
        }
        String res="";
        for(int i=0;i<numRows;i++){
            for(int j=0;j<n;j++){
                if(p[i][j]!=' ') res+=p[i][j];
            }
        }
        return res;


活动打卡代码 AcWing 5. 最长回文子串

中心扩散

class Solution {
    public String longestPalindrome(String s) {
        String res="";
        for(int i=0;i<s.length();i++){
            int l=i-1,r=i+1;
            while(l>=0 && l<s.length() && r>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){
                l--;r++;
            }
            if(res.length()<r-l-1) res=s.substring(l+1,r);//保存结果
            //另一种情况,偶数个回文串
            l=i;r=i+1;
            while(l>=0 && l<s.length() && r>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){
                l--;r++;
            }
            if(res.length()<r-l-1) res=s.substring(l+1,r);
        }
        return res;
    }
}

动态规划

//f[i][j] 表示 从第i个到第j个字符串是否为回文串
//  划分:若s[i]和s[j]相等,则f[i][j]=f[i+1][j-1];(此时需保证区间的合理性)
//            若j-1-(i+1)+1<2,即j-i<3,剩下的都是合理的
class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<2) return s;
        int max=1,n=s.length();
        boolean [][] f=new boolean[n][n];
        int beg=0,end;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                f[i][j]=true;
            }
        }
        for(int j=1;j<n;j++){
            for(int i=0;i<j;i++){
                if(s.charAt(i)==s.charAt(j)){
                    //去除边界后剩下的元素只有一个或者零个
                    if(j-i<3) 
                        f[i][j]=true;
                    else 
                        f[i][j]=f[i+1][j-1];
                }else{
                    f[i][j]=false;
                }
                if(f[i][j]==true && j-i+1>=max) {
                    //保存左边界和区间长度
                    max=j-i+1;
                    beg=i;
                }
            }
        }
        return s.substring(beg,beg+max);
    }
}


活动打卡代码 LeetCode 2. 两数相加

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head=new ListNode(-1),node=head;
        int t=0;
        //当两个数都遍历完,并且没进位。
        while(l1!=null || l2!=null || t!=0){
            //两个值分别加上去,最后处理进位
            if(l1!=null) {t+=l1.val; l1=l1.next;}
            if(l2!=null) {t+=l2.val; l2=l2.next;}
            //把结果的一位,先加入List(若最后只有进位,也包括进去处理了)
            node.next=new ListNode(t%10);
            node=node.next;
            //进位继续处理
            t=t/10;
        }
        //head.next为虚拟节点,后面保存结果
        return head.next;
    }
}


活动打卡代码 LeetCode 1. 两数之和

//hashmap去寻找target-num[i]的值是否存在即可,O(n)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res=new int[2];
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],i);
        }
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i]) && i!=map.get(target-nums[i])) {
                res[0]=i;
                res[1]=map.get(target-nums[i]);
            }
        }
        return res;
    }
}



注意按照右端点排序的语句:list接收返回_Collectors.toList()__getR____collect

list=list.stream().sorted(Comparator.comparing(Pair::getR)).collect(java.util.stream.Collectors.toList());

class Pair和class Main并列,即不可同时两个public class

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Pair> list=new ArrayList<>();

        for(int i=0;i<n;i++){
            list.add(new Pair(sc.nextInt(),sc.nextInt()));
        }
        list=list.stream().sorted(Comparator.comparing(Pair::getR)).collect(java.util.stream.Collectors.toList());

        int tar=list.get(0).getR(),res=1;
        for(int i=1;i<list.size();i++){
            int t=list.get(i).getL();
            if(t>tar) {tar=list.get(i).getR();res++;}
        }
        System.out.println(res);
    }
}
class Pair
{
    int l;
    int r;
    Pair(int l,int r){this.l=l;this.r=r;}
    public int getL(){return l;}
    public int getR(){return r;}
}





Pairs数据类型需要额外导入jar包才可使用,本题自己创建

/*
1.宽度(广度)优先搜索:BFS(Breadth宽度——First——Search)
    不考虑结果的可能位置,彻底地搜索整张图,即先找所有距离为1,再找所有距离为2,需额外的距离数组判断是否遍历过和记录距离、即宽度;
    展开节点而得到的子节点都会被加进一个先进先出的队列,直到找到结果为止
2.最短路是包含dp问题的。最短路问题的时间复杂度高,而dp的低,所以dp问题一般不用最短路来求。
3.深搜一般没有框架,宽搜有。深度搜索可以保证搜到,但不能保证最短。

4.宽搜伪代码:  初始状态放入queue,
                while queue不空
                    拿出队头
                    扩展队头
                从距离数组直接拿到数据

5.(好像不太行)dp思路:f[i][j]表示 走到i,j的路径集合
    集合划分:表示从上下左右四个方向而来的路径f[i-1][j],f[i][j-1],f[i+1][j],f[i][j+1]
*/
import java.util.*;
class Main{
    private static int n,m;
    private static int[][] p,d;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();m=sc.nextInt();
        p=new int[n][m];
        d=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                p[i][j]=sc.nextInt();
                //距离值的初始值设为-1用于判断是否遍历过
                d[i][j]=-1;
            }
        }
        System.out.println(bfs());
    }
    //
    public static int bfs(){
        //队列初始化
        Queue<Pair> q=new LinkedList<>();
        //把(0,0)插入队头
        q.add(new Pair(0,0));
        int[] dx={-1,0,1,0},dy={0,1,0,-1};
        while(!q.isEmpty()){
            //取并弹出队头元素
            Pair t=q.poll();
            for(int i=0;i<4;i++){
                int x=t.getKey()+dx[i],y=t.getValue()+dy[i];
                //坐标不越界 && 没被遍历过 && 值为0
                if(x>=0 && x<n && y>=0 && y<m && p[x][y]==0 && d[x][y]==-1){
                    //赋为前一个点的值+1
                    d[x][y]=d[t.getKey()][t.getValue()]+1;
                    q.add(new Pair(x,y));
                }
            }
        }
        //距离起始为-1,最终要+1
        return d[n-1][m-1]+1;
    } 
}
class Pair{
    int key;
    int value;
    Pair(int k,int v){key=k;value=v;}
    public int getKey(){return key;}
    public int getValue(){return value;}
}



和yxc的思路一样的,可是超时了,求大神帮我分析下

import java.util.*;
import java.io.*;
class Main{
    //c数组用于保存数根节点的数量
    private static int[] p=new int[100010],c=new int[100010];
    static int find(int x){
        if(p[x]==x) return x;
        else return find(p[x]);
    }
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.valueOf(s[0]);
        int m = Integer.valueOf(s[1]);
        for(int i=1;i<=n;i++){
            p[i]=i;c[i]=1;
        }
        while(m-->0){
            String[] strs = br.readLine().split(" ");
            if(strs[0].equals("C")) {
                int a = Integer.parseInt(strs[1]);
                int b = Integer.parseInt(strs[2]);
                if(find(a)!=find(b)){ 
                    c[find(b)]=c[find(b)]+c[find(a)];
                    p[find(a)]=find(b);
                }
            }else if(strs[0].equals("Q1")){
                int a = Integer.parseInt(strs[1]);
                int b = Integer.parseInt(strs[2]);
                if(find(a)==find(b)) System.out.println("Yes");
                else System.out.println("No");
            }else if(strs[0].equals("Q2")){
                int a = Integer.parseInt(strs[1]);
                System.out.println(c[find(a)]);
            }
        }
    }
}



/*
注意点:
    1.往最后端点插入时,可以用l[1],即最后一个位置的左节点来确定
    2.同样,往一个点左边插入时,需要的也是l[k]
    3.初始化操作:r[0]=1; l[1]=0; idx=2; head和tail分别为下标0和1
    4.      int t=0;
            while(r[t]!=1){t=r[t];}
            add(t,x);
            //这种方式取尾节点的时间最差为1e9,时间会爆掉=100000^2
*/
import java.util.*;
class Main{
    private static int N=100010;
    //private static int head;
    private static int idx=0;
    private static int[] e=new int[N];
    private static int[] l=new int[N];
    private static int[] r=new int[N];
    public static void init(){
        r[0]=1;
        l[1]=0;
        idx=2;
    }
    //在idx为k后加入一个节点
    public static void add(int k,int x){
        e[idx]=x;
        r[idx]=r[k];
        l[idx]=l[r[k]];
        l[r[k]]=idx;
        r[k]=idx;  //这步要最后做
        idx++;
    }
    //删除idx为k的节点
    public static void remove(int k){
        l[r[k]]=l[k];
        r[l[k]]=r[k];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        init();
        while(n-->0){
            String c=sc.next();

            int k,x;
            if(c.equals("L")){
                x=sc.nextInt();
                add(0,x);
            }else if(c.equals("R")){
                x=sc.nextInt();
                add(l[1],x);

                /*int t=0;
                while(r[t]!=1){t=r[t];}
                add(t,x);*/

            }else if(c.equals("D")){
                k=sc.nextInt();
                remove(k+1);
            }else if(c.equals("IL")){
                k=sc.nextInt();
                x=sc.nextInt();
                add(l[k+1],x);
            }else if(c.equals("IR")){
                k=sc.nextInt();
                x=sc.nextInt();
                add(k+1,x);
            }
        }
        for(int i=0;r[i]!=1;i=r[i]) 
            System.out.print(e[r[i]]+" ");
    }
}