力扣刷题记录

• 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 map = new HashMap();
        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;
    }

//1.
    
    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();
    }

//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;
    }

//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;
    }

//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;
        }
    }

//1.回溯
    List list;
    StringBuilder sb;
    public List 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);
        }
    }