LeetCode 集锦（三十五） - 第 141 题 Linked List Cycle

发表于 2019-06-28 | 分类于算法 |

问题

Given a linked list, determine if it has a cycle in it. 

 To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. 




 Example 1: 


Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

 Example 2: 

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

 Example 3: 

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 Follow up: 

 Can you solve it using O(1) (i.e. constant) memory?

翻译:

给定一个链表，判断它是否有一个循环。
为了在给定的链表中表示一个循环，我们使用一个整数pos，它表示tail连接到的链表中的位置(0索引)。如果pos为-1，则链表中没有循环。
示例1:
输入:head = [3,2,0，-4]， pos = 1
输出:true
说明:链表中有一个循环，tail连接到第二个节点。
示例2:
输入:head = [1,2]， pos = 0
输出:true
说明:链表中有一个循环，tail连接到第一个节点。
示例3:
输入:head = [1]， pos = -1
输出:false
说明:链表中没有循环。
跟进:
你能用O(1)(即常数)内存来解吗?

解题思路

本题是判断一个链表是否是环路，如果我们根据循环遍历，貌似是可以做到的，但是可能有个更加好的方式，在我们读取/遍历的时候把节点的value修改变成我们一个约束的条件，比如int的最小/最大值，如果再次读取到这个值，说明是循环了（当然这个方式是有一定危险的，因为。。。万一真的出现了一个节点的值和约定的特殊值相同，那就误判了）　

解题方法

按照思路来编写结果

public boolean hasCycle(ListNode head) {

    if (head == null) {
        return false;
    }
    while (head != null) {
        if (head.val == Integer.MIN_VALUE) {
            return true;
        }
        head.val = Integer.MIN_VALUE;
        head = head.next;
    }
    return false;

}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

时间复杂度: 该方案用了遍历的方式，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，抛开之前提到的问题，使用特殊值标记的情况下，改方案还是ok的

LeetCode 集锦（三十四） - 第 136 题 Single Number

发表于 2019-06-28 | 分类于算法 |

问题

Given a non-empty array of integers, every element appears twice except for one. Find that single one. 

 Note: 

 Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 

 Example 1: 


Input: [2,2,1]
Output: 1


 Example 2: 


Input: [4,1,2,1,2]
Output: 4

翻译:

给定一个非空整数数组，除一个元素外，每个元素都出现两次。找到那一个。
注意:
您的算法应该具有线性运行时复杂度。你能在不使用额外内存的情况下实现它吗?
示例1:
输入(2 2 1):
输出:1
示例2:
输入:[4、1、2、1、2)
输出:4

解题思路

本题是找出奇数位的那个值，这就让我们不由的想到了位运算异或^操作，异或操作是位值相同则变成了0，不同则为1，所以如果是同一个数进行异或则会0，0和任何数异或都是当前值。所以很符合我们这边奇偶性筛选

解题方法

使用异或方式来解体

if (nums.length <= 0) {
        return 0;
    }
    int result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        result = result ^ nums[i];
    }

    return result;

时间复杂度: 该方案用了遍历的方式，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，使用位运算的特性，可以让本题更加简单，高效

LeetCode 集锦（三十三） - 第 125 题 Valid Palindrome

发表于 2019-06-28 | 分类于算法 |

问题

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. 

 Note: For the purpose of this problem, we define empty string as valid palindrome. 

 Example 1: 


Input: "A man, a plan, a canal: Panama"
Output: true


 Example 2: 

Input: "race a car"
Output: false

翻译:

给定一个字符串，判断它是否是回文，只考虑字母数字字符而忽略大小写。
注意:为了解决这个问题，我们将空字符串定义为有效的回文。
示例1:
输入:“A man, a plan, a canal: Panama”
输出:true
示例2:
输入:“race a car”
输出:false

解题思路

本题是判断一个字符串是否是回文，之前就也做过类似，但是不同的是，这边需要移除非数字和字母的字符，并且不区分大小写来判断是否回文，所以这边利用遍历的方式可以进行解题

解题方法

按照思路来编写结果

public static boolean isPalindrome(String s) {
     if (s.length() <= 1) {
         return true;
     }
     int equals = 'a' - 'A';

     int index = 0;
     int end = s.length() - 1;
     while (index < end) {
         char left = getLowerChar(s.charAt(index));
         if (!isUseFullChar(left)) {
             index++;
             continue;
         }
         char right = getLowerChar(s.charAt(end));
         if (!isUseFullChar(right)) {
             end--;
             continue;
         }

         int temp = left - right;
         if (temp == 0 || temp == equals || temp == -equals) {
             index++;
             end--;
             continue;
         }
         return false;

     }
     return true;

 }

 private static boolean isUseFullChar(char c) {

     return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z');
 }

 private static char getLowerChar(char c) {

     if (c >= 'A' && c <= 'Z') {
         return (char) (c - 'A'+'a');
     }
     return c;
 }

时间复杂度: 该方案用了双向遍历的方式，但是还是遍历n，所以为O(n)=O(n)

空间复杂度: 该方案并没有使用额外空间来遍历，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，本题没有多余的复杂性，就是要多出很多判断，过滤条件

LeetCode 集锦（三十二） - 第 122 题 Best Time to Buy and Sell Stock II

发表于 2019-06-28 | 分类于算法 |

问题

Say you have an array for which the ith element is the price of a given stock on day i. 

 Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). 

 Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). 

 Example 1: 


Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.


 Example 2: 


Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.


 Example 3: 


Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

翻译:

假设你有一个数组，其中第i个元素是某只股票在第i天的价格。
设计一个算法来寻找最大的利润。您可以完成任意数量的事务(即，买进一股，再卖出一股)。
注:你不可同时进行多项交易(即，你必须先把股票卖了再买。
示例1:
输入:[7、1、5、3、6、4]
输出:7
说明:第2天买入(价格= 1)，第3天卖出(价格= 5)，利润= 5-1 = 4。
然后第4天买进(价格= 3)，第5天卖出(价格= 6)，利润= 6-3 = 3。
示例2:
输入:(1、2、3、4、5)
输出:4
说明:第一天买入(价格= 1)，第5天卖出(价格= 5)，利润= 5-1 = 4。
注意，你不能在第一天买，在第2天买，然后像现在这样卖
同时处理多个事务。你必须先卖再买。
示例3:
输入:[7、6、4、3、1]
输出:0
说明:在本例中，没有进行任何交易，即最大利润= 0。

解题思路

本题是上一题的升华版，由于我们知道如果当前值比之前定位的值大的话，卖出肯定是赚，同样如果定位到比目前最小值还小，那么就可以把前面最大的价格给加起来，这样子就代表之前购买的最大值已经购买，后续也是一样的。

解题方法

按照思路来编写结果

if(prices.length<=0){
        return 0;
    }
    int result = 0;
    int temp = prices[0];
    int index = 0;

    for (int i = 1; i < prices.length; i++) {

        index = Math.max(prices[i] - temp, index);
        if (prices[i] < prices[i - 1]) {
            result += index;
            temp = prices[i];
            index = 0;
        }
    }

    return result+index;

时间复杂度: 该方案用了一层遍历的方式，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外空间来存储，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，利用上一步的思路，把每一段的最大值都加起来，也就是利润最大的结果

LeetCode 集锦（三十一） - 第 121 题 Best Time to Buy and Sell Stock

发表于 2019-06-28 | 分类于算法 |

问题

Say you have an array for which the ith element is the price of a given stock on day i. 

 If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. 

 Note that you cannot sell a stock before you buy one. 

 Example 1: 


Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.


 Example 2: 


Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

翻译:

假设你有一个数组，其中第i个元素是某只股票在第i天的价格。
如你最多只获准完成一项交易(即，买一股，卖一股)，设计一个算法来寻找最大的利润。
注意，你不能在买股票之前卖掉它。
示例1:
输入:[7、1、5、3、6、4]
输出:5
说明:第2天买入(价格= 1)，第5天卖出(价格= 6)，利润= 6-1 = 5。
不是7-1 = 6，因为卖价需要大于买价。
示例2:
输入:[7、6、4、3、1]
输出:0
说明:在本例中，没有进行任何交易，即最大利润= 0。

解题思路

本题是找寻一个买入卖出的最大理论，其实就是寻找当前值和后续值中相差最大的正数值。可以用循环遍历的方式查询，当然也可以一次循环，如果碰到比选中值更小的，那么就替换选中值，并选择差距最大的值记录，实现很简单

解题方法

遍历方式，代码如下

int result = 0;
   for (int i = 0; i < prices.length; i++) {
       for (int m = i + 1; m < prices.length; m++) {
           result = Math.max(prices[m] - prices[i], result);
       }
   }

   return result;

时间复杂度: 该方案用了两次循环遍历的方式，所以为O(n)=O(n^2)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

一次循环方式：

if (prices.length <= 1) {
        return 0;
    }

    int temp = prices[0];
    int result = 0;
    for (int i = 1; i < prices.length; i++) {

        result = Math.max(prices[i] - temp, result);

        if (prices[i] < temp) {
            temp = prices[i];
        }
    }
    return result;

时间复杂度: 该方案用了一次遍历的方式，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，遍历虽然可以，但是性能不佳，可以定位比当前小的值，毕竟如果后面出现差值比较大的，小的值差值肯定更加大

LeetCode 集锦（三十） - 第 119 题 Pascal Triangle II

发表于 2019-06-21 | 分类于算法 |

问题

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. 

 Note that the row index starts from 0. 


In Pascal's triangle, each number is the sum of the two numbers directly above it. 

 Example: 


Input: 3
Output: [1,3,3,1]


 Follow up: 

 Could you optimize your algorithm to use only O(k) extra space?

翻译:

给定一个k≤33的非负索引k，返回帕斯卡三角形的第k个索引行。
注意，行索引从0开始。
在帕斯卡三角形中，每个数都是它上面两个数的和。
例子:
输入:3
输出:[1,3,3,1]

解题思路

本题也是杨辉三角，但是和上一题的要求又是不一样的，这个只需要计算出当前行数所对应的值就行，规律和之前一样，所以直接执行即可，这边可以用一个数组完成，可以用倒序的方式，来一步步覆盖。

解题方法

按照思路来编写结果

if (rowIndex <= 0) {
        return Arrays.asList(1);
    }
    List<Integer> list = new ArrayList<>(rowIndex);

    for (int i = 1; i <= rowIndex+1; i++) {

        for (int j = i - 1; j >= 0; j--) {

            if(j == i - 1){
                list.add(1);
                continue;
            }
            if (j == 0  ) {
                list.set(j, 1);
                continue;
            }
            list.set(j, list.get(j) + list.get(j - 1));
        }
    }
    return list;

时间复杂度: 该方案用了遍历的方式，所以为O(n)=O(n^2)

空间复杂度: 该方案使用了一个数组来存储结果，所以空间复杂度O(n)=O(n)

总结

本题的大致解法如上所诉，利用倒序的方式来避免了使用多余的空间，也算是一种方式把

LeetCode 集锦（二十九） - 第 118 题 Pascal Triangle

发表于 2019-06-21 | 分类于算法 |

问题

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. 


In Pascal's triangle, each number is the sum of the two numbers directly above it. 

 Example: 


Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

翻译:

给定一个非负整数numRows，生成Pascal三角形的第一个numRows。
在帕斯卡三角形中，每个数都是它上面两个数的和。
例子:
输入:5
输出:
1
2
3
4
5
6
7
8
>[
>     [1],
>    [1,1],
>   [1,2,1],
>  [1,3,3,1],
> [1,4,6,4,1]
]
>

解题思路

本题是简单的杨辉三角模型，只要了解杨辉三角的特点，就可以很简单的解决这个问题，杨辉三角的特点是每一行的第一个和最后一个都是1，中间的数值是由上一层相邻的两个相加而成。假设当前行的第n位，那么n=上一层的n位+上一层的n-1位。

解题方法

按照思路来编写结果

List<List<Integer>> lists = new ArrayList<>();


for (int i = 1; i <= numRows; i++) {
    List<Integer> list = new ArrayList<>();
    for (int j = 0; j < i; j++) {
        if (j == 0 || j == i - 1) {
            list.add(1);
            continue;
        }
        List<Integer> laster = lists.get(i - 1);
        int sum = laster.get(j - 1) + laster.get(j);
        list.add(sum);
    }
    lists.add(list);

}
return lists;

时间复杂度: 该方案用了遍历的方式,两层嵌套循环，所以为O(n)=O(n^2)

空间复杂度: 该方案为了存储每一层数据，都用了list，所以空间复杂度O(n)=O(n^2)

总结

本题的大致解法如上所诉，杨辉三角还是很常见的，也是很简单的题，只要知道规律就不难

LeetCode 集锦（二十八） - 第 112 题 Path Sum

发表于 2019-06-18 | 分类于算法 |

问题

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. 

 Note: A leaf is a node with no children. 

 Example: 

 Given the below binary tree and sum = 22, 


      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1


 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

翻译:

给定一棵二叉树和一个和，确定该树是否有根到叶的路径，以便将路径上的所有值相加等于给定的和。
注意:叶子是没有子节点的节点。
例子:
给出下面的二叉树，sum = 22，
1
2
3
4
5
6
7
8
>      5
>     / \
>     4   8
>    /   / \
>   11  13  4
>  /  \      \
> 7    2      1
>

返回 true, 由于存在根到叶的路径5->4->11->2，其和为22。

解题思路

本题相对而言也是简单的，求一个树的根节点到叶子节点的和为目标值。本题只要注意叶子节点就行：

要是叶子节点，叶子节点指的是没有子节点的节点。如果只是一个节点为努力了，那样子不算叶子节点。
其他只要按照遍历的方式，判断是否复合要求

解题方法

按照思路来编写结果

public boolean hasPathSum(TreeNode root, int sum) {
     if (sum < 0 || root == null) {
         return false;
     }

     if (sum == 0 && root.left == null && root.right == null) {
         return true;
     }
     boolean left = hasPathSum(root.left, sum - root.val);
     boolean right = hasPathSum(root.right, sum - root.val);

     return left || right;

 }

 public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;

     TreeNode(int x) {
         val = x;
     }
 }

时间复杂度: 该方案用了遍历的方式，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，通过递归的方式来遍历每一个子节点，判断当前子节点的差是否满足要求，判断是否是叶子节点，就可以判断是否符合要求。

LeetCode 集锦（三十六） - 第 155 题 Min Stack

发表于 2019-06-18 | 分类于算法 |

问题

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. 

 push(x) -- Push element x onto stack. 
 pop() -- Removes the element on top of the stack. 
 top() -- Get the top element. 
 getMin() -- Retrieve the minimum element in the stack. 

 Example: 

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

翻译:

设计一个栈，支持push、pop、top和在常量时间内检索最小元素。
push(x)——将元素x推入堆栈。
pop()——删除堆栈顶部的元素。
top()——获取top元素。
getMin()——检索堆栈中的最小元素。
例子:
MinStack = new MinStack();
minStack.push (2);
minStack.push (0);
minStack.push (3);
minStack.getMin ();- - >返回3。
minStack.pop ();
minStack.top ();- - >返回0。
minStack.getMin ();- - >返回2。

解题思路

本题是编写一个栈，但是对于栈的功能而言，多一个查询里面最小值的方法。栈的特点在于先进后出，我们可以用链表来实现。但是要获取最小值，

第一想到的就是可以通过遍历的方式来获取最小值，每次新进来一个对比一下就好。但是该方式在pop的时候就要重新定位最小值，还是比较耗性能的。
由于栈的特性，早先进去的值不会先被pop掉，所以在新增一个值，判断出最小值的时候，就是这一栈中最小的，即便被pop掉了，下一个节点的最小值是前面入栈中最小值，所以我们可以把最小值存入节点中。这样做就不需要遍历了

解题方法

按照遍历的方式：

class MinStack {

    private List<Integer> list = new ArrayList<>();

    private Integer min = Integer.MAX_VALUE;

    /**
     * initialize your data structure here.
     */
    public MinStack() {

    }

    public void push(int x) {
        list.add(x);
        if (x < min) {
            min = x;
        }

    }

    public void pop() {
        if (list.size() <= 0) {
            return;
        }
        Integer integer = list.remove(list.size() - 1);
        if (integer.equals(min)) {
            //重新遍历获取最小值
            int min = Integer.MAX_VALUE;
            for (Integer integer1 : list) {
                if (min > integer1) {
                    min = integer1;
                }
            }
            this.min = min;
        }

    }

    public int top() {
        if (list.size() <= 0) {
            return 0;
        }
        return list.get(list.size() - 1);
    }

    public int getMin() {
        return min;
    }
}

时间复杂度: 该方案用中，每一次的pop方式都需要遍历，所以为O(n)=O(n)

空间复杂度: 无

链表的方式实现：

class MinStack {


    private Node indexNode;

    /**
     * initialize your data structure here.
     */
    public MinStack() {

    }

    public void push(int x) {
        Node node = new Node(x, x);

        if (indexNode != null) {
            //比较最小
            if (indexNode.min < x) {
                node.setMin(indexNode.min);
            }
        }
        node.next = indexNode;
        indexNode = node;

    }

    public void pop() {
        indexNode = indexNode.next;

    }

    public int top() {
        return indexNode.var;

    }

    public int getMin() {
        return indexNode.min;
    }


}

protected class Node {
    private int var;

    private int min;

    private Node next;

    public Node(int var, int min) {
        this.var = var;
        this.min = min;
    }

    public int getVar() {
        return var;
    }

    public void setVar(int var) {
        this.var = var;
    }

    public int getMin() {
        return min;
    }

    public void setMin(int min) {
        this.min = min;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

时间复杂度: 该方案用中，每一次的pop方式都需要遍历，所以为O(n)=O(1)

空间复杂度: 无

总结

本题的大致解法如上所诉，熟悉数据结构的特点，才能更好的编写代码。利用栈的先进后出保证前面的最小值不会因为pop而变化，如果是队列，那就不能用这种方式了。

LeetCode 集锦（二十七） - 第 111 题 Minimum Depth Of Binary Tree

发表于 2019-06-18 | 分类于算法 |

问题

Given a binary tree, find its minimum depth. 

 The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 

 Note: A leaf is a node with no children. 

 Example: 

 Given binary tree [3,9,20,null,null,15,7], 


    3
   / \
  9  20
    /  \
   15   7 

 return its minimum depth = 2.

翻译:

给定一个二叉树，求它的最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数。
注意:叶子是没有子节点的节点。
例子:
给定如下树[3,9,20,null,null,15,7]:
1
2
3
4
5
6
>    3
>   / \
>  9  20
>    /  \
>   15   7 
>

返回最小深度:2

解题思路

本题相对而言也是简单的，求一颗树的最小高度，所以首先要注意最小高度的定义：最小深度是从根节点到最近叶子节点的最短路径上的节点数。这边需要注意几个点：

要是叶子节点，叶子节点指的是没有子节点的节点。如果只是一个节点为努力了，那样子不算叶子节点。
是最近的叶子节点。
其他其实按照最大深度的方式去执行，就可以做到了

解题方法

按照思路来编写结果

public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int right = minDepth(root.right) + 1;
        int left = minDepth(root.left) + 1;
        int min = Math.min(left, right);
        //判断是否有空的节点
        if (min <= 1) {
            return Math.max(right, left);
        }
        return min;

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

时间复杂度: 该方案用了遍历的方式，所以为O(n)=O(n)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度O(n)=O(1)

总结

本题的大致解法如上所诉，通过递归的方式来获取每一个子节点的深度，判断是否有叶子节点，然后获取最小的深度。

FightCrap

制造bug的永动机

GitHub E-Mail