刷题周报(20200907-20200913)

刷题周报(20200907-20200913)

剑指offer65.不用加减乘除做加法

写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

这道题要考的就是位运算,但是如果没有强制要求语言的话,Java里面是可以这样做的:

class Solution {
    public int add(int a, int b) {
        AtomicInteger ai = new AtomicInteger(a);
        return ai.addAndGet(b);
    }
}

但是这就没啥意思了,来看位运算的解法:

整体的思路就是将加法运算做拆解,拆解为不进位的和+进位,说起来有点抽象,以十进制为例,例如87+46=133,我们可以这样拆分:87+46 = 23 + 110,其中2是不进位的和,3也是不进位的和,然后110是我们的进位,本来是11的,我们需要对其左移一位,才能表示出正确的结果,同样,二进制也是如此,那为什么要在一个循环中进行呢?

因为不进位的和+进位也是包括+号的,我们需要循环到进位为0,即可得到结果

class Solution {
    public int add(int a, int b) {
        while(b != 0){
            int plus = (a ^ b);//计算不进位的和
            b = ((a & b) << 1);//计算进位的和
            a = plus;
        }
        return a;
    }
}

lc39.组数组合

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。

思路:回溯+剪枝

这道题要想找到所有的组数,最直接的方法还是遍历,遍历过程中需要考虑到一些附加条件,例如可能出现条件不满足的情况,那么就退出进行下一步遍历,就是这种做法,这玩意的官方叫法叫做回溯

另外在遍历过程中可以进行优化的一个地方是candidate数组的数组大小,如果事先对这个数组进行一个排序的话,可以节省很大的时间成本

除此以外保证组合不能重复,这一点可以通过我们在递归过程中传进去的起始遍历下表来保证,这玩意的官网叫法叫做剪枝

代码实现:

class Solution {    
    List<List<Integer>> res  = new ArrayList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates == null || candidates.length == 0)    return res;
        //先排个序,可以优化
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList();
        dfs(candidates,list,target,0);
        return res;
    }
    public void dfs(int[] candidates, List<Integer> list,int target,int start){
        if(target == 0){
            res.add(new ArrayList(list));
            return;
        }       
        for(int i = start;i < candidates.length;i++){
            if(candidates[i] > target){
                return;
            }
            list.add(candidates[i]);
            dfs(candidates,list,target - candidates[i],i);
            list.remove(list.size()-1);
        }
    }
}

lc116. 填充每个节点的下一个右侧节点指针

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

Solution1

class Solution {
    public Node connect(Node root) {
        if(root == null)    return root;
        Queue<Node> list = new LinkedList();
        list.add(root);
        Node temp = null;
        while(!list.isEmpty()){
            int size = list.size();
            for(int i = 0;i < size;i++){
                temp = list.poll();
                if(i < size-1){
                    temp.next = list.peek();
                }                   
                if(temp.left != null){
                    list.add(temp.left);
                }
                if(temp.right != null){
                    list.add(temp.right);
                }
            }
        }
        return root;
    }
}

复习点:

整体思路就是在层次遍历的过程中修改指针,使用for循环提前来读取进行连接的节点数,一开始使用的是while循环,错误的将下一层的节点也进行了连接,另外使用判断条件if(i < size-1)对临界节点做一个处理就好了!

Solution2

思路:

这种方法是看题解学到的,思路就是利用上一层已经构建好的next指针来构建下一层的next指针,每一层都是从最左面的leftmost节点开始,水平的遍历操作同一层的每一个节点,nice!

class Solution {
    public Node connect(Node root) {
        if(root == null)    return root;
        Node leftmost = root;
        while(leftmost.left != null){
            Node temp = leftmost;//使用temp变量来进行操作,不破坏每一层的最左节点
            while(temp != null){
                temp.left.next = temp.right;
                temp.right.next = temp.next != null? temp.next.left : null;
                temp = temp.next;
            }
            leftmost = leftmost.left;
        }
        return root;
    }
}

递归方式实现,清爽一些:

class Solution {
    public Node connect(Node root) {
        if(root == null)    return root;
        if(root.left != null){
            root.left.next = root.right;
        }
        if(root.right != null){
            root.right.next = root.next != null? root.next.left : null;
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

lc1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

晚上刷Hot100,居然给我推出了lc第一题,看来第一题热度还是比较高的哈,整体难度不大, 就当是重复刷了,可以使用暴力方法做,但是这就失去了这道题目的意义,下面的做法使用了空间换时间的策略,将遍历过程中的数据存储在哈希表中

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null || nums.length == 0) return res;
        HashMap<Integer,Integer> map = new HashMap();
        for(int i = 0;i < nums.length;i++){          
            if(map.containsKey(target-nums[i])){
                res[0] = i;
                res[1] = map.get(target-nums[i]);
                break;
            }
            map.put(nums[i],i);
        }
        return res;
    }
}

lc2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

没想到热题居然都是前面的,这道题目虽然我做过,但是几个细节处理了半天,看来这玩意还是得反复做,熟悉编程技巧

具体思路没啥说的,好好学习一下循环怎么写的,周末打开链接再来一遍

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int extra = 0;
        while(l1 != null || l2 != null){
            int x = l1 != null ? l1.val : 0;
            int y = l2 != null ? l2.val : 0;
            int val = extra + x + y;
            ListNode node = new ListNode(val%10);
            curr.next = node;
            curr = node;
            extra = val / 10;
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        if(extra != 0){
            ListNode lastone = new ListNode(extra);
            curr.next = lastone;
        }
        return dummy.next;
    }
}

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

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

滑动窗口

其实滑动窗口这个方法也不是很新奇,思路就是遍历字符串的每一个字符,找到从这个字符开始的最长无重复字符字串,中间要想保证不重复,利用set集合的不含重复元素的特性即可,并且在遍历每个字符的过程中更新最大值

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet();
        int n = s.length();
        int right = -1;//滑动窗口右侧指针
        int ans = 0;
        for(int i = 0;i < n;i++){
            if(i != 0){
                set.remove(s.charAt(i-1));
            }
            while(right + 1 < n && !set.contains(s.charAt(right+1))){
                set.add(s.charAt(right+1));
                right++;
            }
            ans = Math.max(ans,right-i+1);
        }
        return ans;
    }
}

还有一种性能非常好的写法:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        for(int i = 0;i < 128;i++){
            last[i] = -1;
        }
        int n = s.length();
        int res = 0;
        int start =0;
        for(int i = 0; i < n; i++){
            int index = s.charAt(i);
            start = Math.max(start,last[index]+1);
            res = Math.max(res,i-start+1);
            last[index] = i;
        }
        return res;
    }
}

这是评论里面的一个题解,实现起来不仅非常优雅,而且效率比上面的滑动窗口的方法要好很多,看了好长时间才理解,周日的时候再复习一下

lc139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

动态规划,dp[i]数字表示前i个字符是否可以被划分为单词

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet();
        for(String word : wordDict){
            set.add(word);
        }
        //dp[i]表示前i个字符中是否可以被拆分为单词
        boolean[] dp = new boolean[s.length()+1];

        dp[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i; j++){
                dp[i] = dp[j] && set.contains(s.substring(j,i));
                if(dp[i])   break;
            }
        }
        return dp[s.length()];
    }
}

lc136. 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

主要的解法还是面向最后的说明,不然这道题要是直接使用集合来解决就没什么意义了,或者是暴力解法,时间复杂度也是太大了 ,除此以外,排序也是一种办法,下面介绍一种在题解里面看大的神仙解法:位运算

能够使用位运算的原因还是分析题意,每两个一对的重复运算,不正是符合异或运算嘛, 最后,只出现一次的数字和0进行异或,解决就是只出现一次的数字!

class Solution {
    public int singleNumber(int[] nums) {
        int num = nums[0];
        for(int i = 1; i < nums.length; i++){
            num = num ^ nums[i];
        }
        return num;
    }
}

lc128. 最长连续序列

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

这道题的难点在于对事件复杂度的约束,如果要是使用排序做的话,那么时间复杂度就会超出,这里可以使用空间换时间的思路,将这个数组存储到Set或者哈希表中,来控制时间复杂度

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int i : nums){
            set.add(i);
        }
        int res = 0;
        for(int i : nums){
            int len = 0;
            int num = i;
            if(!set.contains(num-1)){
                len += 1;
                while(set.contains(num+1)){
                    len++;
                    num++;
                }
            }
            res = Math.max(res,len);
        }
        return res;
    }
}

lc124. 二叉树中的最大路径和

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

最开始做的时候对路径和认识不对,实际上这里的路径是不能分叉的,也就是说,只能是单一方向的一条路径:

image-20200912220728263

这里理解了之后,题目实现起来就通畅多了,总体上还是使用递归的方法做,分别计算出左右节点的贡献值。这个过程中不断的更新最大值即可

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

做了一些树的题目之后,总结出来一个规律,就是树的问题百分之九十都是可以通过递归的方式解决的,只要理解递归在树种的运用,一些题目解决起来还是非常有技巧性的

lc79. 单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

这道题和之前做过的岛屿问题相似,都是采用dfs+回溯的方法,看到官方题解之后学到了处理这种问题非常优雅的办法,以后可以用来当作一个技巧使用

public class Solution {

    private boolean[][] marked;

    private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    // 盘面上有多少行
    private int m;
    // 盘面上有多少列
    private int n;
    private String word;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        if (m == 0) {
            return false;
        }
        n = board[0].length;
        marked = new boolean[m][n];
        this.word = word;
        this.board = board;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int start) {
        if (start == word.length() - 1) {
            return board[i][j] == word.charAt(start);
        }
        if (board[i][j] == word.charAt(start)) {
            marked[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int newX = i + direction[k][0];
                int newY = j + direction[k][1];
                if (inArea(newX, newY) && !marked[newX][newY]) {
                    if (dfs(newX, newY, start + 1)) {
                        return true;
                    }
                }
            }
            marked[i][j] = false;
        }
        return false;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

首先就是在处理四个方向的时候使用了这个数组:

private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

对一个位置做四个方向的搜索的时候,只需要遍历direction数组,分别加上四个变量即可。

另外在代码可读性方面,将判断出界的逻辑抽象到一个方法中:

 private boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
 }

这周总体上刷题数目不多,不过没关系,这玩意也不是走量的,另外就是大大小小的笔试实在是太多了,这周末就参加了四场,这周一共已经参加至少十场了,下周的笔试日程也是安排上了,哎,娃娃好苦,快上岸吧。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/刷题周报20200907-20200913md