leetcode算法题解(Java版)-6-链表,字符串-阿里云开发者社区

开发者社区> 人工智能> 正文

leetcode算法题解(Java版)-6-链表,字符串

简介: 把数字转化为罗马符号,根据罗马符号的规律,可以先用map来存储一下。之后把每一位添加到所求中去。 语法点:StringBuffer是字符缓冲区,是可以修改字符长度的,最后要用sb.toString()去返回缓冲区的字符串

一、字符串处理

题目描述

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

思路

  • 把数字转化为罗马符号,根据罗马符号的规律,可以先用map来存储一下。之后把每一位添加到所求中去。
  • 语法点:StringBuffer是字符缓冲区,是可以修改字符长度的,最后要用sb.toString()去返回缓冲区的字符串

代码

//!COPY

public class Solution {
    public String intToRoman(int num) {
             String[][] map={
            {"","I","II","III","IV","V","VI","VII","VIII","IX"},
            {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},
            {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},
            {"","M","MM","MMM"}
        };
        StringBuffer sb=new StringBuffer();
        sb.append(map[3][num/1000%10]);
        sb.append(map[2][num/100%10]);
        sb.append(map[1][num/10%10]);
        sb.append(map[0][num%10]);
        
        return sb.toString();
    }
}

二、链表

题目描述

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8 

思路

  • 链表的题,虽然题目说存放的数字是反过来的,但是完全可以把加法也”反过来“,也就是说从”左到右“相加。
  • 链表的题,一般都应该设置一个头指针head(里面什么也不存放,只是用来记住链表的头)

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode head=new ListNode(0);
        ListNode p=head;
        int tem=0;
        while(l1!=null||l2!=null||tem!=0){
            if(l1!=null){
                tem+=l1.val;
                l1=l1.next;
            }
            if(l2!=null){
                tem+=l2.val;
                l2=l2.next;
            }
            p.next=new ListNode(tem%10);
            p=p.next;
            tem/=10;
        }
        return head.next;
    }
}

三、最长无重复字符子串

题目描述

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路

  • 水题渐渐做完了,开始碰到的题有难度了。这题用到了所谓的滑动窗口法:从左到右滑动,如果碰到了在左边界内且出现过的字符,那就将左边界移动到之前的那个字符的下一位,刷新求最大即可。
  • 还看到一位大神的神解法,代码很简洁,思想其实也是一样的:从左到右滑动,记录每一个字符上一次出现的位置,在第i位时比较当前字符的上一次出现的位置和左边界,刷新当前左边界。

代码1

import java.util.HashMap;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap <Character,Integer> map=new HashMap<>();
        int len=s.length();
        if(s==null||len==0){
            return 0;
        }
        int res=0;
        int l=0;
        for(int i=0;i<len;i++){
            char c=s.charAt(i);
            if(map.containsKey(c)){
                l=Math.max(l,map.get(c)+1);
            }
            res=Math.max(res,i-l+1);
            map.put(c,i);
        }
        return res;
    }
}

代码2

import java.util.HashMap;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> map=new HashMap<>();
        int len = s.length();
        if(s==null||len==0){
            return 0;
        }
        for(int i=0;i<len;i++){
            map.put(s.charAt(i),-1);
        }
        int l=-1;
        int res=0;
        for(int i=0;i<len;i++){
            char c=s.charAt(i);
            l=Math.max(l,map.get(c));
            res=Math.max(res,i-l);
            map.put(c,i);
        }
        return res;
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章