LeetCode中等题（⼀）
题⽬⼀：
给出两个⾮空的链表⽤来表⽰两个⾮负的整数。其中，它们各⾃的位数是按照逆序的⽅式存储的，并且它们的每个节点只能存储⼀位数字。
如果，我们将这两个数相加起来，则会返回⼀个新的链表来表⽰它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
⽰例：
输⼊：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
分析：这道题⽬是⼀个链表题，对链表元素相加得出⼀个新的链表，那么怎么能实现链表元素的相加呢？其实这和我们实现两个数相加很类似，⾸先应该从个位数开始，如果之和⼤于10则将向前进⼀位。
1、创建⼀个新的链表，⽤于返回最后相加和的结果，ListNode DummyNode=new ListNode(0);
2、设置⼀些指向链表的节点，分别指向l1，l2，DummyNode, p1=l1,p2=l2,curr=DummyNode;
3、开始遍历列表，进⾏求和，⾸先获取了l1,l2头节点的值，在进⾏相加  int x=(p1!=null)? p1.val:0;    int y=(p2!=null)? p2.val:0;  int
sum=x+y+count;
4、这⾥的难点在于求和后的结果超过10应该怎么办？我们应该将其记录下来，然后添加到下⼀次求和中，如上式的sum，记录的⽅式
为：sum=sum/10，结果是0或者1；
5、curr节点应该添加⼀个新的节点，并且存放所求得的和值，⽅式为=new ListCode(sum%10);
6、将curr,p1,p2分别向后移动指针，;    if(p1!=null) ;    if(p2!=null) ;
7、如果在最后⼀轮循环中count⼤于1，这需要新创建⼀个节点  =new ListNode(count);
8、返回链表，因为第⼀个节点为0，⽆意义。
具体实现过程：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode DummyNode=new ListNode(0);
ListNode p1=l1,p2=l2,curr=DummyNode;
int count=0;
while(p1!=null||p2!=null)
{
int x=(p1!=null)? p1.val:0;
int y=(p2!=null)? p2.val:0;
int sum=x+y+count;
count=sum/10;
<=new ListNode(sum%10);
;
if(p1!=null) ;
if(p2!=null) ;
}
if(count>0)
<=new ListNode(count);
;
}
}
题⽬⼆：
给定⼀个字符串，请你出其中不含有重复字符的最长⼦串的长度。
⽰例 1:
输⼊: "abcabcbb"
输出: 3
解释: 因为⽆重复字符的最长⼦串是 "abc"，所以其长度为 3。
⽅法⼀：暴⼒法
1、获得字符串长度，⽤⼆次循环直接遍历所有的可能性 for(int i=0; i<s.lenght;i++) for(int j=i+1;j<s.lenght;j++)
2、获取所有字符串长度的最⼤值，ans=Math.max(ans,j-i)
3、这⾥最主要的⼀部是获取字符串长度的⽐较，⾸先设置⼀个集合Set<Character> set=new HashSet<>();
4、将字符串s，i,j的位置传⼊判断函数，获取传⼊的值Character ch=s.CharAt(i)，获取索引i的值；
5、判断ch值是否重复，ain(ch)) return false，set.add(ch);
6、返回true;
具体代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length();
int ans=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<=n;j++)
{
if(JugleFun(s,i,j)) ans=Math.max(ans, j-i);
}
return ans;
}
public boolean JugleFun(String s,int start,int end)
{
Set<Character> set=new HashSet<>();
for(int i=start;i<end;i++)
{
Character ch=s.charAt(i);
ains(ch)) return false;
set.add(ch);
}
return true;
}
}
⽅法⼆：滑动窗⼝
1、使⽤i=0,j=0两个值向后逐个滑动；
2、主要的思想：如果遍历过字符串为不重复⼦串，就没必要再去重复判断，如果1234561，i=1，j=1，直接从i=2和j=1进⾏判断；
3、if(!ain(s.charAt(j)))，set.add(s.char(j++))  否则ve(s.charAt(i++));
具体代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length();
int i=0,j=0,ans=0;
Set<Character> set=new HashSet<>();
while(i<n&&j<n)
{
if(!ains(s.charAt(j)))
{
set.add(s.charAt(j++));
ans=Math.max(ans, j-i);
}
else {
}
}
return ans;
}
}
题⽬三：
给定⼀个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满⾜：
左括号必须⽤相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
⽰例 1:
输⼊: "()"
输出: true
分析：
1、字符的两两匹配问题，先将其放⼊哈希表中，HashMap<Character,Character> hashmap=new HashMap<>()；
2、在构造函数中进⾏初始化，hashmap.put(')','(')；
3、应该使⽤栈数据结构，将放⼊的元素和栈顶元素对⽐，Stack<Character> stack=new Stack<>()，获取串元素：k=s.CharAt(i)；
4、如果是哈希表中的键，将进⾏对⽐，否则直接压栈，ainKey(c)), 获取栈顶元素：Character pty()? '#':stack.pop();
5、⽐较栈顶元素和要⼊栈的元素是否相同，if(topElem!=(c))
6、返回栈是否为空，pty();
具体代码：
class Solution {
private HashMap<Character, Character> hashMap=new HashMap<Character,Character>();
public Solution()
{
hashMap.put(')', '(');
hashMap.put('}', '{');
hashMap.put(']', '[');
}
public boolean isValid(String s) {
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++)
{
char c=s.charAt(i);
ainsKey(c))
{
Character pty()? '#':stack.pop();
if(topEle!=(c))
return false;
}
else {
stack.push(c);
}
}
pty();
}
}
题⽬四：
给定⼀个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
⽰例：
给定⼀个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第⼆个节点后，链表变为 1->2->3->5.
⽅法⼀：
1、删除倒数第n个节点，先应该遍历出链表的长度，然后⽤lenght=length-n；
2、判断链表长度定位到删除的位置，if(lenght>0) ;
字符串长度最大是多少3、需要设置两个节点，⼀个⽤来遍历curr，另⼀个指向头结点，ListNode dummy=new ListNode;
4、返回;
具体代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode curr=head;
ListNode dummy=new ListNode(0);
<=head;
int count=0;
while(curr!=null)
{
count++;
;
}
count-=n;
curr=dummy;
while(count>0)
{
count--;
;
}
<=;
;
}
}
⽅法⼆：
分析：
1、采⽤双指针实现，first指针先执⾏n步，然后second指针开始执⾏；
2、直到first为空，停⽌执⾏second；
3、将second指针指向下⼀个节点=；
4、开始设置哑结点指向头结点，first和second都指向dummy；
具体代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode(0);
<=head;
ListNode first=dummy;
ListNode second=dummy;
for(int i=1;i<=n+1;i++)
{
;
}
while(first!=null)
{
;
;
}
<=;
;
}
}
题⽬五：
给定⼀个字符串 s，到 s 中最长的回⽂⼦串。你可以假设 s 的最⼤长度为 1000。
⽰例 1：
输⼊: "babad"
输出: "bab"
注意: "aba" 也是⼀个有效答案。
⽅法⼀：暴⼒法
判断字符串中的回⽂，并将最⼤的回⽂串返回
1、将所有的字符串进⾏遍历，判断每个字符串是否为回⽂；
2、可以另外设置⼀个函数进⾏判断，判断字符串的第⼀位和最后⼀位是否相同即可，即if(s.charAt(i)==s.charAt(lenght-i-1))
3、设置返回的字符串为ans=" "；如果字符串为回⽂，那么返回最⼤的字符
串，ma=0;if(str.lengt>0)，ans=str，ma=Math.max(max，str.lenght)；
4、返回length；
class Solution {
public String longestPalindrome(String s) {
String ans="";
int ma=0;
for(int i=0;i<s.length();i++)
for(int j=i+1;j<=s.length();j++)
{
String str=s.substring(i,j);
if(isHuiWei(str)&&str.length()>ma)
{
ans=s.substring(i,j);
ma=Math.max(ma, ans.length());
}
}
return ans;
}
public boolean isHuiWei(String s)
{
int len=s.length();
for(int i=0;i<len/2;i++)
{
if(s.charAt(i)!=s.charAt(len-i-1))
{
return false;
}
}
return true;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。