posted in leetcode  数组 

问题

给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

示例 1:

输入:\(["bella","label","roller"]\)
输出:\(["e","l","l"]\)

示例 2:

输入:\(["cool","lock","cook"]\)
输出:\(["c","o"]\)

提示:

  1. \(1 <= A.length <= 100\)
  2. \(1 <= A[i].length <= 100\)
  3. \(A[i][j]\) 是小写字母

解法

首先需要将每一个字符串进行字母的数量统计。然后遍历数量数组,获取每个字符的最小出现次数,即为答案。
数量统计有多种做法,二维数组、hashmap。此题中使用了二维数组。

代码

java

class Solution {
    public List<String> commonChars(String[] A) {
        //生成一个二维数组用于保存词频
        int[][] array = new int[A.length][26];
        //词频统计
        for (int i = 0; i < A.length; i++) {
            String s = A[i];
            for (char c : s.toCharArray()) {
                array[i][c - 97]++;
            }
        }
        List<String> result = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if(array[0][i]==0) {
                continue;
            }
            //得到第一组词频
            int count = array[0][i];
            for (int j = 1; j < A.length; j++) {
                if (array[j][i] == 0){
                    count = 0;
                    break;
                }
                count = Math.min(count, array[j][i]);
            }
            //如果词频大于0,那么加入结果中
            if (count > 0) {
                char c = (char) (97 + i);
                String s = Character.toString(c);
                while (count-- >0) {
                    result.add(s);
                }
            }
        }
        return result;
    }
}
posted in leetcode  数组 

问题

给定一个二进制数组, 计算其中最大连续1的个数。

示例 1:

输入: \([1,1,0,1,1,1]\)
输出: \(3\)
解释: 开头的两位和最后的三位都是连续\(1\),所以最大连续\(1\)的个数是 \(3\).

注意:

  • 输入的数组只包含 0 和1。
  • 输入数组的长度是正整数,且不超过 10,000。

解法

此题比较简单,一次遍历即可完成。直接上代码。

代码

java

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int result = 0;
        int curr = 0;
        for(int i: nums) {
            if (i == 0) {
                curr = 0;
            } else{
                curr++;
                result = Math.max(result, curr);
            }
        }
        return result;
    }
}
posted in 二叉树  leetcode  数组 

问题

最大树定义:一个树,其中每个节点的值都大于其子树中的任何其他值。

给出最大树的根节点 \(root\)。

就像之前的问题那样,给定的树是从表 \(A(root = Construct(A))\)递归地使用下述 \(Construct(A)\) 例程构造的:

  • 如果 \(A\) 为空,返回 \(null\)
  • 否则,令 \(A[i]\) 作为 \(A\) 的最大元素。创建一个值为 \(A[i]\) 的根节点 \(root\)
  • \(root\) 的左子树将被构建为 \(Construct([A[0], A[1], ..., A[i-1]])\)
  • \(root\) 的右子树将被构建为 \(Construct([A[i+1], A[i+2], ..., A[A.length - 1]])\)
  • 返回 \(root\)
    请注意,我们没有直接给定 \(A\),只有一个根节点 \(root = Construct(A)\).

假设 \(B\) 是 \(A\) 的副本,并附加值 \(val\)。保证 \(B\) 中的值是不同的。

返回 \(Construct(B)\)。

示例 1:

输入: \(root = [4,1,3,null,null,2], val = 5\)
输出: \([5,4,null,1,3,null,null,2]\)
解释: \(A = [1,4,2,3], B = [1,4,2,3,5]\)

示例 2:

输入:\(root = [5,2,4,null,1], val = 3\)
输出:\([5,2,4,null,1,null,3]\)
解释:\(A = [2,1,5,4], B = [2,1,5,4,3]\)

示例 3:

输入:\(root = [5,2,3,null,1], val = 4\)
输出:\([5,2,4,null,1,3]\)
解释:\(A = [2,1,5,3], B = [2,1,5,3,4]\)

解法

这道题本身不难,难得是理解题意,一开始我还在想示例2中的3放在5前面似乎也并无不可。后来才发现,其实\(val\)是追加在\(A\)末尾的,而不是随便放在哪个位置的。既然这样,考虑一下\(val\)与\(root\)的大小关系,一共有三种情况:

  1. \(root\)为空,此时直接生成一个TreeNode(val)返回即可
  2. \(root.val < val\),此时说明,\(val\)已经找到了应该在的位置,那么生成一个TreeNode(val), 并且将左儿子设置成\(root\)(因为\(root\)对应的数组元素必然在\(val\)的左边。)
  3. \(root.val > val\),此时说明,\(val\)仍然没有找到所在位置,但是因为\(val\)在最右,那么递归到\(root.right\)中去处理。

递归完成后返回root即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        // 情况1
        if (root == null) {
            return new TreeNode(val);
        }
        // 情况2
        if (root.val < val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        // 情况3
        root.right = insertIntoMaxTree(root.right,val); 
        //最终递归返回
        return root;
    }
}
posted in 二叉树  数组  leetcode 

问题

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

  1. 二叉树的根是数组中的最大元素。
  2. 左子树是通过数组中最大值左边部分构造出的最大二叉树。
  3. 右子树是通过数组中最大值右边部分构造出的最大二叉树。
  4. 通过给定的数组构建最大二叉树,并且输出这个树的根节点。

Example 1:

输入: \([3,2,1,6,0,5]\)
输入: 返回下面这棵树的根节点:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

注意:

  • 给定的数组的大小在 [1, 1000] 之间。

解法

通过定义,我们发现,可以通过遍历获取到此次遍历的根结点,然后再次分别遍历根节点左边的子数组获取此次遍历的根节点的左儿子,遍历根节点右边的子数组获取根节点的右儿子。需要注意的点是儿子是否存在有两种情况,需要在遍历子数组的时候处理好。
整体没有太大难度,边界条件处理好即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return treefy(nums, 0, nums.length-1);
    }
    private TreeNode treefy(int[] nums, int start, int end){
        //当start==end时,表示为叶节点了,可以生成叶节点跳出了
        if(start == end) {
            return new TreeNode(nums[start]);
        }
        //当start>end时,表示叶节点为空,返回null
        if (start>end) {
            return null;
        }
        //遍历start与end之间的元素,找到最大值,生成节点。
        int maxIndex = start;
        for(int i = start; i <= end; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        //找到最大值后,递归调用左儿子与右儿子
        TreeNode node = new TreeNode(nums[maxIndex]);
        node.left = treefy(nums, start, maxIndex - 1);
        node.right = treefy(nums,maxIndex + 1, end);
        return node;
    }
}
posted in leetcode 

问题

在二维平面上,有一个机器人从原点(0, 0)开始。给出它的移动顺序,判断这个机器人在完成移动后是否在(0, 0) 处结束。

移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R(右),L(左),U(上)和 D(下)。如果机器人在完成所有动作后返回原点,则返回 true。否则,返回 false。

注意:机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次,“L” 将始终向左移动等。此外,假设每次移动机器人的移动幅度相同。

示例 1:

输入: "UD"
输出:true
解释:机器人向上移动一次,然后向下移动一次。所有动作都具有相同的幅度,因此它最终回到它开始的原点。因此,我们返回 true。

示例 2:

输入: "LL"
输出: false
解释:机器人向左移动两次。它最终位于原点的左侧,距原点有两次 “移动” 的距离。我们返回 false,因为它在移动结束时没有返回原点。

解法

问题看似复杂,其实就是上下的步数相等,左右的步数相等,那么必然回到原点。所以设置4个int。遍历moves,对应++即可。

代码

java

class Solution {
    public boolean judgeCircle(String moves) {
        //实际上就是上下数量一致,左右数量一致就可以回到原点
        int u=0;
        int d=0;
        int l=0;
        int r=0;
        char[] array = moves.toCharArray();
        for (char c : array) {
            switch(c) {
                case 'U': u++;break;
                case 'D': d++;break;
                case 'L': l++;break;
                case 'R': r++;break;
            }
        }
        return u == d && l == r;
    }
}
posted in leetcode  链表  双指针 

问题

编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:

在节点\( c1 \)开始相交。
示例 1:

输入: intersectVal = 8, listA = \([4,1,8,4,5]\), listB = \([5,0,1,8,4,5]\), skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 \(8 \)(注意,如果两个列表相交则不能为 \(0\))。从各自的表头开始算起,链表 A 为 \([4,1,8,4,5]\),链表 B 为 \([5,0,1,8,4,5]\)。在 A 中,相交节点前有\(2\)个节点;在 B 中,相交节点前有\(3\)个节点。

示例 2:

输入:intersectVal = 2, listA = \([0,9,1,2,4]\), listB = \([3,2,4]\), skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 \(2\) (注意,如果两个列表相交则不能为 \(0\))。从各自的表头开始算起,链表 A 为 \([0,9,1,2,4]\),链表 B 为 \([3,2,4]\)。在 A 中,相交节点前有 \(3\) 个节点;在 B 中,相交节点前有 \(1\) 个节点。

示例 3:

输入:intersectVal = 0, listA = \([2,6,4]\), listB = \([1,5]\), skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 \([2,6,4]\),链表 B 为 \([1,5]\)。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:

  1. 如果两个链表没有交点,返回 null.
  2. 在返回结果后,两个链表仍须保持原有的结构。
  3. 可假定整个链表结构中没有循环。
  4. 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

解法

注意到这样一个事实,如果两个链表相交,那么在相交节点前面的两个分叉上,正好相差这两个链表长度之差的元素个数。因此,首先遍历两个链表,得到链表长度,然后长度更长的链表先往前走长度之差的步数,然后后面两个链表向前推进到相等即为结果。

代码

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        //首先遍历两个链表查询长度
        int l1 = 0;
        ListNode h1 = headA;
        while (h1 != null) {
            h1 = h1.next;
            l1++;
        }
        int l2 = 0;
        ListNode h2 = headB;
        while (h2 != null) {
            h2 = h2.next;
            l2++;
        }
        
        //长度更长的那个需要先走几步,直到两个长度相等时才同时前进。
        h1 = headA;
        h2 = headB;
        int dif = l1-l2;
        if (dif > 0) {
            while(dif-- >0) {
                h1 = h1.next;
            }
        } else if (dif < 0) {
            while(dif++ < 0) {
                h2 = h2.next;
            }
        }
        int len = Math.min(l1, l2);
        while (h1 != h2){
            h1 = h1.next;
            h2 = h2.next;
        }
        return h1;
    }
}
posted in leetcode 

问题

假设Andy和Doris想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。
示例 1:
输入:
\(["Shogun", "Tapioca Express", "Burger King", "KFC"]\)
\(["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]\)
输出: \(["Shogun"]\)
解释: 他们唯一共同喜爱的餐厅是\("Shogun"\)。

示例 2:

输入:
\(["Shogun", "Tapioca Express", "Burger King", "KFC"]\)
\(["KFC", "Shogun", "Burger King"]\)
输出: \(["Shogun"]\)
解释: 他们共同喜爱且具有最小索引和的餐厅是\("Shogun"\),它有最小的索引和1(0+1)。
提示:

  1. 两个列表的长度范围都在 \([1, 1000]\)内。
  2. 两个列表中的字符串的长度将在\([1,30]\)的范围内。
  3. 下标从\(0\)开始,到列表的长度减\(1\)。
  4. 两个列表都没有重复的元素。

解法1

直接看上去就是两个数组求并集的一个延伸,那么直接使用双层循环+特殊退出条件即可完成。时间复杂度\(O(m*n)\),其中\(m、n\)为两个数组的长度。

代码1

java

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        // 最小索引和
        int minIndex = Integer.MAX_VALUE;
        List<String> result = new LinkedList<>();
        // 第一层循环,可以依靠minIndex来缩短部分循环
        for(int i = 0;i < list1.length && i <= minIndex; i++) {
            // 第二层循环,依靠i与minIndex可以缩短部分循环
            for(int j = 0;j < list2.length && i + j <= minIndex; j++) {
                // 如果两个元素相等,才进入后面的判断
                if (list1[i].equals(list2[j])) {
                    // 如果i+j<minIndex,说明找到了更小的索引和,需要重置result,并且 缩小minIndex
                    if (i + j < minIndex) {
                        minIndex = i + j;
                        result.clear();
                        result.add(list1[i]);
                    } else if (i + j == minIndex) {
                        result.add(list1[i]);
                    }
                }
            }
        }
        return result.toArray(new String[0]);
    }
}

解法2

解法1时间复杂度较高,能不能通过另外的手段降低呢?同时发现提示中有个数组中没有重复元素的前提,考虑java中的HashMap(插入、查询的时间复杂度可以认为是\(O(1)\)的)来保存其中一个列表的字符串与索引值。另一个数组再次遍历一下查找HashMap中是否存在相同的关系就可以了。两个循环非嵌套,所以可以认为时间复杂度为\(O(m+n)\)的。
另外,为了减少空间复杂度与降低HashMap的hash冲突,考虑对两个数组中较小的那个放入HashMap中。同时,更极端的情况下需要考虑HashMap的rehash对时间复杂度与空间复杂度的影响。

代码2

java

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        int l1 = list1.length;
        int l2 = list2.length;
        
        //找到规模更小的数组进行hash化
        if (l1 > l2) {
            return findRestaurant(list2, list1);
        }
        //极端情况下需要考虑rehash
        Map<String, Integer> map = new HashMap<>(l1);
        for(int i = 0;i < l1; i++) {
            map.put(list1[i],i);
        }
        int minIndex = Integer.MAX_VALUE;
        List<String> result = new LinkedList<>();
        
        //遍历第二个数组,这里可以用j<=minIndex来提前跳出循环,因为大于的必然不在结果中
        for(int j = 0;j < l2 && j <= minIndex; j++) {
            Integer index = map.get(list2[j]);
            if (index != null) {
                if (index + j < minIndex) {
                    minIndex = index + j;
                    result.clear();
                    result.add(list2[j]);
                } else if (index + j == minIndex){
                    result.add(list2[j]);
                }
                
            }
        }
        return result.toArray(new String[0]);
    }
}
posted in leetcode  二叉树 

问题

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法

递归方法很简单,不再赘述。迭代方法一般考虑用双栈法。java的LinkedList提供了add(0,value)的方法,可以直接使用这个作为第二个栈与返回值。

代码

java

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        dfs(root);
        return result;
    }
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        dfs(root.right);
        result.add(root.val);
    }
}

迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.empty()) {
            TreeNode node = stack.pop();
            //直接add(0,val);
            result.add(0, node.val);
            //注意这里是左先入栈
            if (node.left !=null){
                stack.push(node.left);
            }
            //然后是右入栈
            if(node.right !=null) {
                stack.push(node.right);
            }
        }
        return result;
    }
}
posted in leetcode 

问题

给定一个 N 叉树,返回其节点值的后序遍历。
例如,给定一个 \(3叉树\):

返回其后序遍历: \([5,6,3,2,4,1]\).

**说明: **递归法很简单,你可以使用迭代法完成此题吗?

解法

589. N叉树的前序遍历基本一样,只是把前序变成后续即可。
但是迭代的后序遍历比较难。这里考虑用双栈法处理。同时,联想到java的List接口提供一个add(int index, E val)的方法,可以当作栈使用,所以,其实第二个栈可以直接用result代替。

代码

java

递归

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new LinkedList<>();
    
    public List<Integer> postorder(Node root) {
        if (root == null) {
            return result;
        }
        dfs(root);
        return result;
    }
    private void dfs(Node root) {
        if (root == null) {
            return;
        }
        //优先去遍历子树而不是root本身
        if (root.children !=null) {
            for(Node node:root.children) {
                dfs(node);
            } 
        }
        result.add(root.val);
    }
}

递归

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new LinkedList<>();
    
    public List<Integer> postorder(Node root) {
        if (root == null) {
            return result;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        while(!stack.empty()) {
            Node node = stack.pop();
            //直接将当前val写入result第一个元素即可。
            result.add(0, node.val);
            //这里要注意。是node.children。一开始写成了root.children...
            //而且与前序遍历不同,这里是从左往右入栈,如果不能想清楚可以在纸上画一下。
            List<Node> children = node.children;
            if (children != null) {
                stack.addAll(children);
            }
        }
        return result;
    }
}

问题

给定一个 \(N\) 叉树,返回其节点值的前序遍历。
例如,给定一个 \(3叉树\) :
 

返回其前序遍历: \([1,3,5,6,2,4]\)。

说明: 递归法很简单,你可以使用迭代法完成此题吗?

解法

如果忽略说明的话,使用递归确实非常简单。与二叉树的前序遍历一样,唯一需要注意的一点是儿子是个list。递归转迭代也只是用
下面给出递归与迭代的不同代码

代码

java

递归方式

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return result;
        }
        dfs(root);
        return result;
    }
    private void dfs(Node root) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        //唯一需要注意的就是这里的对儿子的处理
        if (root.children !=null) {
            for(Node node:root.children) {
                dfs(node);
            }
        }
    }
}

迭代方式

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return result;
        }
        //使用栈来存储
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.val);
            if (node.children !=null) {
                List<Node> children = node.children;
                //这里需要注意的一点是,压栈的顺序,要从最右开始压
                for(int i=children.size() - 1;i >= 0;i--){
                    stack.push(children.get(i));
                }
            }
        }
        return result;
    }
}