- 1、 无重复字符的最长子串(力扣3)
- 2、 Z 字形变换(力扣6)
- 3、 字符串转换整数 (atoi)(力扣8)
- 4、盛最多水的容器(力扣11)
- 5、合并两个有序链表(力扣21)
- 6、括号生成(力扣22)
- 7、括号生成(力扣22)
//1.滑动窗口
public int lengthOfLongestSubstring(String s) {
if(s.length() < 2) return s.length();
Map<Character,Integer> map = new HashMap<Character,Integer>();
int left = 0,right = 0,max = 0;
while(right < s.length()){
if(map.containsKey(s.charAt(right))){
//以“abba”为例,防止left被原来的数据影响
left = Math.max(map.get(s.charAt(right)) + 1,left);
}
map.put(s.charAt(right),right);
max = Math.max(max,right - left + 1);
right ++;
}
return max;
}
2、 Z 字形变换(力扣6)
//1.
/*
* 0 4 8
* 1 3 5 7 9
* 2 6 10
*
* */
public String convert(String s, int numRows) {
if(numRows == 1) return s;
String[] rows = new String[Math.min(s.length(),numRows)];
Arrays.fill(rows,"");
int curRow = 0;
//用来判断是不是向下的
boolean goingDown = false;
for(char c : s.toCharArray()){
rows[curRow] += c;
//每当为第一行和最后一行时,调整方向
if(curRow == 0 || curRow == numRows - 1){
goingDown = !goingDown;
}
curRow += goingDown ? 1 : -1;
}
StringBuilder sb = new StringBuilder();
for(String str : rows){
sb.append(str);
}
return sb.toString();
}
3、 字符串转换整数 (atoi)(力扣8)
//1.从前向后遍历,理清各种情况
public int myAtoi(String s) {
char[] chars = s.toCharArray();
int len = chars.length;
int index = 0;
// 去掉前导空格
while(index < len && chars[index] == ' '){
index ++;
}
//去掉前导空格以后到了末尾了
if(index == len) return 0;
//判断是否是负数
boolean negative = false;
if(chars[index] == '-'){
negative = true;
index ++;
}else if(chars[index] == '+'){
index ++;
}else if(chars[index] - '0' > 9 || chars[index] - '0' < 0){
return 0;
}
//ans:记录最终数值
int ans = 0;
//当满足是数字时继续向下进行
while(index < len && chars[index] - '0' <= 9 && chars[index] - '0' >= 0){
int digit = chars[index] - '0';
//判断是否会越界
if(ans > (Integer.MAX_VALUE - digit) / 10){
return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
}
ans = ans * 10 + digit;
index ++;
}
return negative ? -ans : ans;
}
4、盛最多水的容器(力扣11)
//1.双指针
public int maxArea(int[] height) {
int len = height.length;
//左指针,右指针,最大值
int left = 0,right = len - 1,max = 0;
while(left < right){
max = Math.max(max,(right - left) * Math.min(height[left],height[right]));
//选择短板进行移动
if(height[left] <= height[right]){
left ++;
}else{
right --;
}
}
return max;
}
5、合并两个有序链表(力扣21)
//1.迭代
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
//设置哑结点,便于返回头节点
ListNode yummy = new ListNode(-101);
ListNode root = yummy;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
root.next = list1;
list1 = list1.next;
}else{
root.next = list2;
list2 = list2.next;
}
root = root.next;
}
if(list1 != null){
root.next = list1;
}
if(list2 != null){
root.next = list2;
}
return yummy.next;
}
//2.递归
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null){
return list2;
}else if(list2 == null){
return list1;
}else if(list1.val <= list2.val){
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}else{
list2.next = mergeTwoLists(list1,list2.next);
return list2;
}
}
6、括号生成(力扣22)
//1.回溯
List<String> list;
StringBuilder sb;
public List<String> generateParenthesis(int n) {
list = new ArrayList<>();
sb = new StringBuilder();
backTracking(n,n);
return list;
}
//leftNum:可用的‘(’数量 rightNum:可用的‘)’数量
public void backTracking(int leftNum,int rightNum){
if(leftNum == 0 && rightNum == 0){
list.add(sb.toString());
return;
}
//如果已经加入的右括号比左括号多,非法,直接返回
if(leftNum > rightNum){
return;
}
//优先加入左括号
if(leftNum > 0){
sb.append('(');
backTracking(leftNum - 1,rightNum);
sb.deleteCharAt(sb.length() - 1);
}
if(leftNum < rightNum){
sb.append(')');
backTracking(leftNum,rightNum - 1);
sb.deleteCharAt(sb.length() - 1);
}
}
7、括号生成(力扣22)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)