刷题周报(20200831-20200906)

刷题周报(20200831-20200906)

剑指offer42.连续数组的最大子序和

这道题目印象中做过好几次了,应该也算是一种动态规划的思想吧

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0)    return 0;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i : nums){
            sum += i;
            max = Math.max(max,sum);
            if(sum < 0){
                sum = 0;
            }
        }
        return max;
    }
}

image-20200906193214391

lc224.基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ,右括号 ),加减乘除,非负整数和空格

class Solution {
    public int calculate(String s) {
        if(s == null && s.length() == 0)  return 0;
        int res = helper(s,0);
        return res;
    }
    private int helper(String s,int index){
        Stack<Integer> stack = new Stack();
        char[] chars = s.toCharArray();
        int num = 0;
        char op = '+';
        for(int i = index;i < chars.length;i++){          
            char ch = chars[i];
            if(Character.isDigit(ch)){
                num = 10 * num + (chars[i] - '0');
            }
            if(chars[i] == '('){
                num = helper(s,++i);
            } 
            if((!Character.isDigit(ch) && chars[i] != ' ') || i == chars.length - 1){
                if(op == '+'){
                    stack.push(num);
                }
                else if(op == '-'){
                    stack.push(-num);
                }
                else if(op == '*' || op == '/'){
                    int temp = op == '*' ? stack.peek() * num :stack.peek() / num;
                    stack.pop();
                    stack.push(temp);
                }

                if(op == ')'){
                    break;
                }
                num = 0;
                op = ch;
            }
        }
        int res = 0;
        while(!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }
}

剑指 Offer36. 二叉搜索树与双向链表

class Solution {
public void flatten(TreeNode root) {
    while (root != null) { 
        //左子树为 null,直接考虑下一个节点
        if (root.left == null) {
            root = root.right;
        } else {
            // 找左子树最右边的节点
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            } 
            //将原来的右子树接到左子树的最右边节点
            pre.right = root.right;
            // 将左子树插入到右子树的地方
            root.right = root.left;
            root.left = null;
            // 考虑下一个节点
            root = root.right;
        }
    }
}
}

lc25.K 个一组翻转链表

非递归方式

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null)    return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode sub_head = head;
        ListNode toNull = head;//用来遍历找到子链表尾部
        ListNode tail = dummy;
    while(sub_head != null){
        int i = k;
        while(i - 1 > 0){
            toNull = toNull.next;
            if(toNull == null){
                return dummy.next;
            }
            i--;
        }
        ListNode temp = toNull.next;
        toNull.next  =null;
        ListNode new_sub_head = reverse(sub_head);
        tail.next = new_sub_head;
        tail = sub_head;
        tail.next = temp;
        sub_head = temp;
        toNull = sub_head;
    }
    return dummy.next;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){            
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;  
        }
        return pre;         
    }
}

递归方式

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null)    return head;
        ListNode point = head;
        int i = k;
        while(i - 1 > 0){
            point = point.next;
            if(point == null){
                return head;
            }
            i--;
        }
        ListNode temp = point.next;
        point.next = null;
        ListNode newHead = reverse(head);
        head.next = reverseKGroup(temp,k);
        return newHead;

    }
    public ListNode reverse(ListNode head){
        if(head == null)    return head;
        ListNode pre = null;
        while(head != null){
            ListNode next = head.next;
            head.next =  pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

手撕快排

public class Main{
    public static void main(String[] args) {
        int[] arr = {2,1,4,3,6,4};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static int divide(int[] arr,int start,int end){
        int base = arr[end];
        while(start < end){
            while(start < end && arr[start] <= base){
                start++;
            }
            if(start  < end){
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                end--;
            }
            while(start < end && arr[end] >= base){
                end--;
            }
            if(start < end){
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
                start++;
            }

        }
        return end;
    }
    public static void sort(int[] arr,int start,int end){
        if(start >= end){
            return;
        }
        int base = divide(arr,start,end);
        sort(arr,start,base-1);
        sort(arr,base+1,end);
    }
}

作业帮面试题

字符串格式化分割

public class StringSeparator {
    public static void main(String[] args) {
        String str = "1bc4ghg3qw";
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            System.out.print(ch);
            if(i == chars.length -1){
                continue;
            }
            if(Character.isDigit(ch) && (chars[i+1] > 'a' && chars[i+1] < 'z')){
                System.out.print(':');
            }
            if((chars[i] > 'a' && chars[i] < 'z') && Character.isDigit(chars[i+1]) ){
                System.out.print('\n');
            }
        }
    }
}

lc92.反转链表

反转从位置 mn 的链表。请使用一趟扫描完成反转。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || m == n)  return head;
        ListNode pre = null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode dummy_head = head;
        ListNode toM = null;
        int i = m - 2;
        while(i > 0){
            dummy_head = dummy_head.next;
            i--;
        }
        toM = dummy_head.next;
        if(m == 1){
            toM = head;
        }
        ListNode temp = toM;
        int sub = n - m + 1 ;
        ListNode next = null;
        while(sub > 0){
            next = temp.next;
            temp.next = pre;
            pre = temp;
            temp = next;
            sub--;
        }
        if(m == 1){
            dummy.next = pre;
            toM.next = next;
            return dummy.next;
        }
        dummy_head.next = pre;
        toM.next = next;
        return head;
    }
}

递归方式实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    static ListNode pre = null;
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || m == n)  return head;
        ListNode dmy = new ListNode(0);
        dmy.next = head;
        int step = m - 1;
        ListNode new_head = dmy;
        while(step > 0){
            new_head = new_head.next;
            step--;
        }
        ListNode toM = new_head.next;
        ArrayList<ListNode> list = new ArrayList(2);
        ArrayList<ListNode> res = reverse(toM,m,n,list);
        new_head.next = res.get(0);
        toM.next = res.get(1);
        return dmy.next;
    }
    private static ArrayList<ListNode> reverse(ListNode toM,int m,int n,ArrayList<ListNode> list){
        if(toM == null)  return null;
        ListNode next = toM.next;
        toM.next = pre;
        pre = toM;
        toM = next;        
        if(m == n){
            list.add(pre);
            list.add(toM);
            return list;
        }
        ArrayList<ListNode> res = reverse(toM,m+1,n,list);
        return res;
    }
}

二叉树的遍历

前序遍历

递归实现:

class Solution {
    ArrayList<Integer> list = new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {               
        helper(root);
        return list;
    }
    public void helper(TreeNode root){
        if(root == null) return;
        list.add(root.val);
        helper(root.left);
        helper(root.right);
    }
}

非递归实现;

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList();
        if(root == null)    return list;
        Stack<TreeNode> stack = new Stack();
        while(root != null){
            list.add(root.val);
            if(root.right != null){
                stack.push(root.right);
            }
            root = root.left;
        }
        while(!stack.isEmpty()){
            TreeNode temp = stack.pop();
            while(temp != null){
                list.add(temp.val);
                if(temp.right != null){
                    stack.push(temp.right);
                }
            temp = temp.left;
            }
        }
        return list;
    }
}

冗长代码简化:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList();
        if(root == null)    return list;
        Stack<TreeNode> stack = new Stack();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()){
            while(p != null){
                list.add(p.val);
                stack.push(p);
                p = p.left;
            }
            if(!stack.isEmpty()){
                TreeNode temp = stack.pop();
                p = temp.right;
            }
        }
        return list;
    }
}

中序遍历

中序遍历和后序遍历的递归方式实现和前序基本一致,不重复实现~

非递归方式:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList();
        if(root == null)    return list;
        Stack<TreeNode> stack = new Stack();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            if(!stack.isEmpty()){
                TreeNode temp = stack.pop();
                list.add(temp.val);
                p = temp.right;
            }
        }
        return list;
    }
}

后序遍历

非递归实现:

public List<Integer> postorderTraversal(TreeNode root) {//非递归写法
    List<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode pre = null;
    stack.push(root);
    while(!stack.isEmpty()){
        TreeNode curr = stack.peek();            
        if((curr.left == null && curr.right == null) ||
           (pre != null && (pre == curr.left || pre == curr.right))){ 
                        //如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时,当前结点出栈
            res.add(curr.val);
            pre = curr;
            stack.pop();
        }else{
            if(curr.right != null) stack.push(curr.right); //先将右结点压栈
            if(curr.left != null) stack.push(curr.left);   //再将左结点入栈
        }            
    }
    return res;        
}

lc200.岛屿数量

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

lc上面是这样问的,但是这道题目有几个变种方式,昨天面试时候问的是最大岛屿面积,只需要在遍历的时候改动一些细节就可以了,要记住dfs这种模板解题方式:

class Solution {
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0)    return 0;
        int nums = 0;
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == '1'){
                    nums += 1;
                    dfs(grid,i,j);
                }
            }
        }
        return nums;
    }
    public static void dfs(char[][] grid,int i,int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){
            return;
        }
        grid[i][j] = '0';
        dfs(grid,i-1,j);
        dfs(grid,i,j-1);
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);
    }
}

lc102.二叉树的层次遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList();
        if(root == null)    return lists;
        ArrayList<TreeNode> nodes = new ArrayList();
        nodes.add(root);       
        while(!nodes.isEmpty()){
            int len = nodes.size();
            ArrayList<Integer> list = new ArrayList();
            for(int i = 0;i < len;i++){
                TreeNode temp = nodes.remove(0);
                list.add(temp.val);
                if(temp.left != null){
                    nodes.add(temp.left);
                }
                if(temp.right != null){
                    nodes.add(temp.right);
                }               
            }
            lists.add(list);
        }
        return lists;

    }
}

lc46.全排列问题

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

回溯+剪枝

package debug01;

import java.util.ArrayList;
import java.util.List;


public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        // 首先是特判
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, res);
                // 注意:这里是状态重置,是从深层结点回到浅层结点的过程,代码在形式上和递归之前是对称的
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }
}