First, string processing

Topic describes

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Train of thought

  • To convert numbers into Roman symbols, according to the rules of Roman symbols, you can use map to store them first. And then we’re going to add each digit to our request.
  • Syntax: A StringBuffer is a character buffer that can change the length of a charactersb.toString()To return the string in the buffer

code

/ /! 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(); }}Copy the code

Second, the linked list

Topic describes

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 Copy the code

Train of thought

  • In the linked list problem, even though they say the numbers are in reverse, you can add them in reverse, that is, from left to right.
  • For linked list questions, you should always set a head pointer to head (which stores nothing but the head of the list).

code

/** * 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; }}Copy the code

The longest substring without repeating characters

Topic describes

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.

Train of thought

  • Water problem gradually finished, began to encounter the problem is difficult. This problem uses the so-called sliding window method: swipe from left to right, and if you encounter a character that appears in the left boundary, you move the left boundary to the next digit of the previous character, and refresh it for maximum value.
  • Also see a big god solution, the code is very simple, the idea is the same: slide from left to right, record the last position of each character, in the I bit to compare the last position of the current character and the left boundary, refresh the current left boundary.

Code 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; }}Copy the code

Code 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; }}Copy the code