codetop几道题练习


image-20220401175851252

3. 无重复字符的最长子串

两次遍历

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0) return 0;
        int[] lastPos = new int[128];
        Arrays.fill(lastPos,-1); // -1 not appear before
        int c = (int)s.charAt(0);
        lastPos[c] = 0;
        int left = 0;
        int result = 1;
        for(int i=1;i<s.length();i++) {
            c = (int)s.charAt(i);
            int lastC = lastPos[c];
            lastPos[c] = i;
            if(lastC!=-1) {
                int tmp;
                while(left<=lastC) {
                    tmp = (int)s.charAt(left);
                    if(lastPos[tmp]<=left) {
                        lastPos[left]= -1;
                    }
                    left++;
                }
            }
            //System.out.printf("%d %d\n",left,i);
            result = Math.max(result,i-left+1);
        }
        return result;
    }
}

一次遍历

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0) return 0;
        int[] lastPos = new int[128];
        Arrays.fill(lastPos,-1); // -1 not appear before
        int c = (int)s.charAt(0);
        lastPos[c] = 0;
        int left = 0;
        int result = 1;
        for(int i=1;i<s.length();i++) {
            c = (int)s.charAt(i);
            if(lastPos[c]!=-1&&left<=lastPos[c]) {
                left=lastPos[c]+1;
            }
            lastPos[c] = i;
            //System.out.printf("%d %d\n",left,i);
            result = Math.max(result,i-left+1);
        }
        return result;
    }
}

变种:允许最多一个重复字符

需要记录前前一个和前一个字符的位置

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0) return 0;
        //记录前前一个对应字符的位置,(需要记录前一个字符的位置)
        int[] lastPos = new int[128]; //前一个
        int[] llPos = new int[128]; //前前一个
        Arrays.fill(lastPos,-1); // -1 not appear before
        Arrays.fill(llPos,-1);
        int c = (int)s.charAt(0);
        lastPos[c] = 0;
        int left = 0;
        int result = 1;
        for(int i=1;i<s.length();i++) {
            c = (int)s.charAt(i);
            if(llPos[c]!=-1&&left<=llPos[c]) {
                left=llPos[c]+1;
            }

            //llPos[c] = i;
            llPos[c] = lastPos[c];
            lastPos[c] = i;

            result = Math.max(result,i-left+1);
        }
        return result;
    }
}

延伸:395. 至少有 K 个重复字符的最长子串

笨方法超时

class Solution {
    public int longestSubstring(String s, int cc) {
        int n = s.length();
        int[][] appearTimes = new int[n+2][128];
        int c;
        for(int i=0;i<n;i++) {
            c = (int)s.charAt(i);
            for(int k=0;k<128;k++) {
                appearTimes[i+1][k] = appearTimes[i][k];
            }
            appearTimes[i+1][c]=appearTimes[i][c]+1;
        }
        for(int k=0;k<128;k++) {
            appearTimes[n+1][k] = appearTimes[n][k];
        }
        //System.out.println(appearTimes[4][(int)'b']);
        int result = 0;
        for(int i=0;i<=n+1;i++) {
            for(int j=0;j<i;j++) {
                boolean allGT = true;
                for(int k=0;k<128;k++) {
                    if(appearTimes[i][k]-appearTimes[j][k]<cc&&appearTimes[i][k]-appearTimes[j][k]>0) {
                        allGT = false;
                        //System.out.printf("%d %d %c\n",i,j,k);
                        break;
                    }
                }
                if(allGT) {
                   // System.out.printf("===%d %d\n",i,j);
                    result = Math.max(result,i==n+1?n-j:i-j);
                }
            }
        }
        return result;
    }
}

==递归方法==

class Solution {
    public int longestSubstring(String s, int k) {
        if(s.length()==0||k>s.length()) return 0;
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++) {
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for(Character c:map.keySet()) {
            if(map.get(c)<k) {
                int result = 0;
                for(String str : s.split(String.valueOf(c)))
                    result = Math.max(result,longestSubstring(str,k));
                return result;
            }
        }
        return s.length();
    }
}

41. 缺失的第一个正数

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++) {
            if(nums[i]==i+1) continue;
            int nextPos = nums[i];
            int tmp;
            while(nextPos>=1&&nextPos<=n) {
                if(nums[nextPos-1]==nextPos) break;
                tmp = nums[nextPos-1];
                nums[nextPos-1] = nextPos;
                nextPos = tmp;
            }
        }
        for(int i=0;i<n;i++) {
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }
}

129. 求根节点到叶节点数字之和

递归

递归比较简单。

class Solution {
    public int sumNumbers(TreeNode root) {
        return sumNumbers(root,0);
    }

    private int sumNumbers(TreeNode root,int father) {
        if(root==null) return father;
        if(root.left==null&&root.right==null) return father*10+root.val;
        int left = 0;
        int right = 0;
        if(root.left!=null) left = sumNumbers(root.left,father*10+root.val);
        if(root.right!=null) right = sumNumbers(root.right,father*10+root.val);
        return left+right;
    }
}

非递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;
        Map<TreeNode,Integer> map = new HashMap<>();
        Deque<TreeNode> queue = new LinkedList<>();
        map.put(root,root.val);
        queue.addLast(root);
        int result = 0;
        while(!queue.isEmpty()) {
            int n = queue.size();
            for(int i=0;i<n;i++) {
                TreeNode cur = queue.pollFirst();
                if(cur.left==null&&cur.right==null) {
                    result+=map.get(cur);
                    continue;
                }
                if(cur.left!=null) {
                    queue.addLast(cur.left);
                    map.put(cur.left,cur.left.val+map.get(cur)*10);
                }
                if(cur.right!=null) {
                    queue.addLast(cur.right);
                    map.put(cur.right,cur.right.val+map.get(cur)*10);
                }
            }
        }
        return result;
    }
}

==(再看看)124. 二叉树中的最大路径和

递归,不连父节点向上传递的直接比较大小,传递的时候只能传左孩子、右孩子和父节点,不能同时传,传的时候也要判断小于零拉倒。最后如果是零的话,选一个最大的结点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int result;
    public int maxPathSum(TreeNode root) {
        result = Integer.MIN_VALUE;
        maxPathSum0(root);
        if(result==0) {
            result = Integer.MIN_VALUE;
            findLargestNode(root);
        }
        return result;
    }

    private void findLargestNode(TreeNode root) {
        if(root==null) return;
        result = Math.max(result,root.val);
        findLargestNode(root.left);
        findLargestNode(root.right);
    }


    private int maxPathSum0(TreeNode root) {
        if(root==null) return 0;
        int left = maxPathSum0(root.left);
        int right = maxPathSum0(root.right);
        result = Math.max(result,left);
        result = Math.max(result,right);
        result = Math.max(result,left+right+root.val);
        int tmp = Math.max(Math.max(left+root.val,right+root.val),root.val);
        return tmp<0?0:tmp;
    }
}

打印路径呢?

在每一个max的地方考虑路径。

402. 移掉 K 位数字

超时需优化

class Solution {
    public String removeKdigits(String num, int k) {
        //num = "0"+num+"0";
        return removeKdigits0(num,k);
    }

    public String removeKdigits0(String num, int k) {
        
        if(k==0) {
            int i=0;
            for(;i<num.length();i++) {
                if(num.charAt(i)!='0') {
                    break;
                }
            }
            String result = num.substring(i,num.length());
            return result.length()==0?"0":result.substring(0,result.length());
        }
        int i=1;
        for(;i<num.length();i++) {
            if(num.charAt(i)>=num.charAt(i-1)) {
                continue;
            } else {
                break;
            }
        }
        String n = num.substring(0,i-1)+num.substring(i,num.length());
        return removeKdigits0(n,k-1);
    }
}

==避免重复执行:单调栈==

class Solution {
    public String removeKdigits(String num, int k) {
        //num = "0"+num+"0";
        return removeKdigits0(num,k);
    }

    public String removeKdigits0(String num, int k) {
        if(num==null||k>num.length()) return "0";
        num = num + "0";
        Deque<Character> deque = new LinkedList<>();
        deque.addLast(num.charAt(0));
        int count = 0;
        for(int i=1;i<num.length();) {
            if(deque.isEmpty() || num.charAt(i)>=deque.getLast()) {
                deque.addLast(num.charAt(i));
                i++;
                continue;
            } else {
                //num.charAt(i)<deque.getLast()
                deque.pollLast();
                count++;
                if(count==k) {
                    StringBuilder result = new StringBuilder();
                    for(Character c:deque) {
                        result.append(c);
                    }
                    result.append(num.substring(i,num.length()-1));
                    String ret =  result.toString();
                    int kk = 0;
                    for(;kk<ret.length();kk++) {
                        if(ret.charAt(kk)!='0') break;
                    }
                    ret = ret.substring(kk,ret.length());
                    return ret.length()==0?"0":ret;
                }
            }
        }
        return "0";
    }
}

(刚看到不容易想)31. 下一个排列

从后往前看,如果降序,继续找,直到找到升序或者结束,如果一直降序,排列,返回。否则将第一个升序的值和右边降序序列的最小值交换,排序右边的降序序列,返回。

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n-1;
        int j = i;
        for(;i>=1;i--) {
            j = i;
            if(nums[i-1]>=nums[i]) continue;
            else {
                // nums[i-1]<nums[i]
                // 找到右边比nums[i-1]大但是最小的数
                for(j=n-1;j>=i;j--) {
                    if(nums[j]>nums[i-1]) break;
                }
                break;
            }
        }
        if(i==0) {
            Arrays.sort(nums);
            return;
        }
        int tmp = nums[i-1];
        nums[i-1] = nums[j];
        nums[j] = tmp;
        Arrays.sort(nums,i,n);
    }
}

反转链表

206. 反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        
        while(cur!=null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

92. 反转链表 II

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode fakeHead = new ListNode();
        fakeHead.next = head;
        // find node before left node
        ListNode before = fakeHead;
        for(int i=1;i<left;i++) {
            before = before.next;
        }

        ListNode cur = before.next;
        before.next = null;
        ListNode revHead = cur;
        ListNode pre = null;
        ListNode next = cur.next;
        for(int i=left;i<=right;i++) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        ListNode revTail = pre;
        before.next = revTail;
        revHead.next = cur;
        return fakeHead.next;
    }
}

98. 验证二叉搜索树

递归

判断左右结点是否符合范围,进一步判断左右节点的左右节点是否符合范围。

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST0(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean isValidBST0(TreeNode root,long min,long max) {
        if(root==null) return true;
        if(root.val<=min||root.val>=max) {
            return false;
        }
        return isValidBST0(root.left,min,root.val) &&
                    isValidBST0(root.right,root.val,max);
    }
}

151. 颠倒字符串中的单词

先转内部,再转整体。

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        s = s+" ";
        char[] chrs = s.toCharArray();
        int left = -1;
        int right = -1;
        for(int i=0;i<chrs.length;i++) {
            if(chrs[i]==' ') {
                if(left==-1) continue;
                else {
                    right = i-1;
                    for(int j=right;j>=left;j--) {
                        sb.append(chrs[j]);
                    }
                    sb.append(" ");
                    left = -1;
                    right = -1;
                }
            }
            else {
                // char
                if(left==-1) {
                    left = i;
                }
            }
        }
        sb.deleteCharAt(sb.length()-1);
        return sb.reverse().toString();
    }
}

或者:

class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        char[] array = s.toCharArray();
        // 删除冗余空格
        int afterSize = 0;
        int cur = 0;
        // 删除首部空格
        for(;cur<n;cur++) {
            if(array[cur]!=' ') {
                array[afterSize++] = array[cur];
                cur++;
                break;
            }
        }
        // 删除其它空格
        for(;cur<n;cur++) {
            if(array[cur]!=' ') {
                array[afterSize++] = array[cur];
            }
            else {
                if(array[afterSize-1]==' ') continue;
                else array[afterSize++] = ' ';
            }
        }
        afterSize--;
        if(array[afterSize]==' ') afterSize--;
        cur = 0;
        int left = 0;
        for(;cur<afterSize;cur++) {
            if(array[cur]==' ') {
                reverseChrs(array,left,cur-1);
                left=cur+1;
            }
        }
        reverseChrs(array,left,afterSize);
        reverseChrs(array,0,afterSize);
        return String.valueOf(Arrays.copyOfRange(array,0,afterSize+1));
    }

    private void reverseChrs(char[] chrs,int start,int end) {
        int i=start;
        int j=end;
        while(i<j) {
            char tmp = chrs[i];
            chrs[i] = chrs[j];
            chrs[j] = tmp;
            i++;
            j--;
        }
    }
}

297. 二叉树的序列化与反序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null) return "[]";
        StringBuilder sb = new StringBuilder("[");
        
        Deque<TreeNode> cur = new LinkedList<>();
        cur.addLast(root);
        StringBuilder lastStr = new StringBuilder();
        while(!cur.isEmpty()) {
            int n = cur.size();
            TreeNode node;
            boolean isNull = true;
            for(int i=0;i<n;i++) {
                node = cur.pollFirst();
                if(node==null) {
                   lastStr.append("null,");
                   continue; 
                } 
                sb.append(lastStr);
                sb.append(node.val);
                lastStr.setLength(0);
                sb.append(",");
                cur.addLast(node.left);
                cur.addLast(node.right);
                if(node.left!=null||node.right!=null) {
                    isNull = false;
                }
            }
            if(isNull) break;
        }

        sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        //System.out.println(sb.toString());
        return sb.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        StringBuilder sb = new StringBuilder(data);
        sb.deleteCharAt(0);
        sb.deleteCharAt(sb.length()-1);
        if(sb.length()==0) return null;
        String[] strs = sb.toString().split(",");
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        Deque<TreeNode> deque = new LinkedList();
        deque.addLast(root);
        TreeNode cur;
        int i = 1;
        while(!deque.isEmpty()) {
            cur = deque.pollFirst();
            if(cur==null) continue;

            if(i>=strs.length) break;
            if(strs[i].equals("null")) cur.left = null;
            else  {
                cur.left = new TreeNode(Integer.parseInt(strs[i]));
                deque.addLast(cur.left);
            }

            i++;
            if(i>=strs.length) break;
            if(strs[i].equals("null")) cur.right = null;
            else {
                cur.right = new TreeNode(Integer.parseInt(strs[i]));
                deque.addLast(cur.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

93. 复原 IP 地址

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        Deque<String> deque = new LinkedList<>();
        restoreIpAddresses(s,0,3,result,deque);
        return result;
    }

    private void restoreIpAddresses(String s,int start,int times,List<String> result,Deque<String> deque) {
        if(times==0) {
            String last = s.substring(start,s.length());
            if(isLegal(last)) {
                deque.add(last);
                result.add(String.join(".",new LinkedList(deque)));
                deque.pollLast();
            }
            return;
        }

        for(int i=start;i<start+3;i++) {
            if(i>=s.length()) return;
            String str = s.substring(start,i+1);
            if(isLegal(str)) {
                deque.addLast(str);
                restoreIpAddresses(s,i+1,times-1,result,deque);
                deque.pollLast();
            }
        }
    }

    private boolean isLegal(String str) {
        if(str.length()==0||str.length()>3) {
            return false;
        }

        if(str.equals("0")) return true;
        if(str.charAt(0)=='0') return false;

        for(int i=0;i<str.length();i++) {
            if(str.charAt(i)<'0'||str.charAt(i)>'9') return false;
        }
        return Integer.parseInt(str)<=255;
    }
}

139. 单词拆分

动态规划。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for(int i=1;i<=n;i++) {
            for(String word:wordDict) {
                if(i-word.length()<0) continue;
                if(!word.equals(s.substring(i-word.length(),i))) continue;
                dp[i] |= dp[i-word.length()];
            }
        }
        return dp[n];
    }
}

15. 三数之和

排序 - 首尾双指针 - 去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int lastP = Integer.MIN_VALUE;
        for(int i=0;i<nums.length-2;i++) {
            if(nums[i]==lastP) continue;
            lastP = nums[i];
            int sum = 0-nums[i];
            int left = i+1;
            int right =nums.length-1;
            int lastLeft = Integer.MIN_VALUE;
            int lastRight = Integer.MIN_VALUE;
            // -1 -1 0 1
            while(left<right) {
                lastLeft = nums[left];
                lastRight = nums[right];
                if(nums[left]+nums[right]==sum) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    left++;
                    while(left<n&&nums[left]==lastLeft) left++;
                    right--;
                    while(right>=0&&nums[right]==lastRight) right--;
                } else if(nums[left]+nums[right]<sum) {
                    left++;
                    while(left<n&&nums[left]==lastLeft) left++;
                } else {
                    right--;
                    while(right>=0&&nums[right]==lastRight) right--;
                }
            }
        }

        return result;
    }
}

662. 二叉树最大宽度

层序遍历,记录最左边和最右边的值就可以了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    class NodePos {
        TreeNode node;
        int pos;
        public NodePos(TreeNode n,int p) {
            node = n;
            pos = p;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        int result = -1;
        Deque<NodePos> deque = new LinkedList<>();
        if(root==null) return 0;
        deque.addLast(new NodePos(root,1));
        NodePos cur;
        while(!deque.isEmpty()) {
            int left = -1;
            int right = -1;
            int n = deque.size();
            for(int i=0;i<n;i++) {
                cur = deque.pollFirst();
                if(i==0) {
                    left = right = cur.pos;
                }
                if(i==n-1) {
                    right = cur.pos;
                }
                if(cur.node.left!=null) deque.addLast(new NodePos(cur.node.left,cur.pos*2));
                if(cur.node.right!=null) deque.addLast(new NodePos(cur.node.right,cur.pos*2+1));
            }
            result = Math.max(result,right-left+1);
        }
        return result;
    }
}