算法-leetcode刷题
2020-03-06 本文已影响0人
tylorsenna
[toc]
LeetCode.1 两数之和
- 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
- 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
// //双重循环 时间复杂度O(n²)
// for(int i=0; i<nums.length; i++){
// for(int j=i+1; j<nums.length; j++){
// if(nums[i]+nums[j] == target){
// result[0] = i;
// result[1] = j;
// return result;
// }
// }
// }
//哈希表 O(n)
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();
for(int i=0; i<nums.length; i++){
if(hashMap.containsKey(nums[i])){
result[0] = hashMap.get(nums[i]);
result[1] = i;
}
//将数据存入 Key为补数——value为下标
hashMap.put(target-nums[i], i);
}
return result;
}
}
- 或者另一种思路：先把数组排序，start、end表示数组下标为0、数组最后一个值的下标。如果nums[start] + nums[end] > target，说明end需要减一；如果nums[start]+ nums[end]<target,说明start需要加1；如果相等则是我们想要的。找到start、end后，再遍历一遍数组，找到对应的结果即可
LeetCode.2 两数相加（大数、链表相加）
- 给出两个非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
- 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode cursor = new ListNode(-1);
ListNode result = cursor;
while(l1 != null || l2 != null || carry>0){
if(l1 != null){
carry += l1.val;
l1 = l1.next;
}
if(l2 != null){
carry += l2.val;
l2 = l2.next;
}
ListNode temp = new ListNode(carry%10);
cursor.next = temp;
cursor = temp;
carry/=10;
}
return result.next;
}
}
LeetCode.67 二进制求和
- 给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。 - 输入: a = "1010", b = "1011"
- 输出: "10101"
class Solution {
public String addBinary(String a, String b) {
// 太容易溢出，错误做法，位数需要满足数据类型。。。
// int int_a = Integer.parseInt(a,2);
// int int_b = Integer.parseInt(b,2);
// int result = int_a + int_b;
// return Integer.toBinaryString(result);
//完美做法：类似链表加法
StringBuffer sb = new StringBuffer();
int carry = 0, i = a.length()-1, j = b.length()-1;
while(i >= 0 || j >= 0 || carry != 0){
if(i >= 0) carry += a.charAt(i--)-'0';
if(j >= 0) carry += b.charAt(j--)-'0';
sb.append(carry%2);
carry /= 2;
}
return sb.reverse().toString();
}
}
LeetCode.112 递归 路径之和Ⅰ（非递归用栈实现）
- 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
- 说明:叶子节点是指没有子节点的节点。
- 示例:给定如下二叉树，以及目标和 sum = 22，
图示: 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1- 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null){
return false;
}
if(root.left == null && root.right == null){
return sum - root.val == 0;
}
return hasPathSum(root.left, sum - root.val)||hasPathSum(root.right, sum - root.val);
}
}
LeetCode.113 递归 路径之和Ⅱ
- 在路径之和Ⅰ的基础上返回路径
- 示例:给定如下二叉树，以及目标和sum = 22，
图示: 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
返回:[[5,4,11,2], [5,8,4,5]]
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> inner = new ArrayList<>();
public void union(TreeNode root, int sum){
if(root == null){
return;
}
sum -= root.val;
inner.add(root.val);
if(root.left == null && root.right == null){
if(sum == 0){
//因为List为引用类型，添加进result后修改还是会改变。所以返回的是拷贝(new 一个拷贝)
result.add(new ArrayList(inner));
}
inner.remove(inner.size()-1);
return;
}
if(root.left!=null) union(root.left, sum);
if(root.right!=null) union(root.right, sum);
inner.remove(inner.size()-1);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
union(root, sum);
return result;
}
}
LeetCode.120 动态规划or递归 三角形最小路径和
-
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形： 存储格式: 2 [ / \ [2], 3 4 [3,4], / \ / \ [6,5,7], 6 5 7 [4,1,8,3] / \ / \ / \ ] 4 1 8 3-
自顶向下的最小路径和为11（即，2+3+5+1= 11）。
说明：
如果你可以只使用 O(n)的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0){
return 0;
}
//二维数组dp[][]
// int[][] dp = new int[triangle.size()+1][triangle.size()+1];
// for(int i = triangle.size()-1; i>=0; i--){
// List<Integer> curTri = triangle.get(i);
// for(int j = 0; j<curTri.size(); j++){
//dp[i][j]表示从顶点到第i+1层第j+1个节点的最小路径
// dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + curTri.get(j);
// }
// }
// // 只需要记录每一层的最小值即可
// int[] dp = new int[triangle.size()+1];
// for(int i = triangle.size()-1; i>=0; i++){
// List<Integer> curTri = triangle.get(i);
// for(int j = 0; j<curTri.size(); j++){
// //这里的dp[j] 使用的时候默认是上一层的，赋值之后变成当前层
// dp[j] = Math.min(dp[j], dp[j+1]) + curTri.get(j);
// }
// }
// return dp[0][0];
//标准On
int n = triangle.size();
int[] dp = new int[n];
for(int i = 0; i < n; i++)
dp[i] = triangle.get(n - 1).get(i);
for(int i = n - 2; i >= 0; i--) {
for(int j = 0; j <= i; j ++) {
dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
//递归法
//return minimumTotalHelper(triangle, 0, 0, new int[triangle.size()][triangle.size()]);
}
int minimumTotalHelper(List<List<Integer>> triangle, int row, int col, int[][] memo){
if(memo[row][col] != 0) return memo[row][col];
if(row == triangle.size()-1){
return memo[row][col] = triangle.get(row).get(col);
}
int left = minimumTotalHelper(triangle, row+1, col, memo);
int right = minimumTotalHelper(triangle, row+1, col+1, memo);
return memo[row][col] = Math.min(left,right) + triangle.get(row).get(col);
}
}
LeetCode.121 动态规划 买卖股票的最好时机1
- 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
- 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
- 注意你不能在买入股票前卖出股票。
- 输入: [7,1,5,3,6,4]
- 输出: 5
- 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6,因为卖出价格需要大于买入价格。
- 输入: [7,6,4,3,1]
- 输出: 0
- 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2) return 0;
int min = prices[0];
int profit = 0;
for(int i=1; i<prices.size(); i++){
profit = profit>prices[i]-min?profit:prices[i]-min;
min = min>prices[i]?prices[i]:min;
}
return profit;
}
};
LeetCode.206 链表 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
//迭代法：
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
//递归：
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
LeetCode.225 队列实现栈
- 一个队列就可实现栈，而一个队列需要两个栈来实现！
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
int size = queue.size();
queue.add(x);
for( ; size>0; size--){
queue.add(queue.remove());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.remove();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
if(queue.isEmpty()){
return true;
}else{
return false;
}
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
LeetCode 面试题57-II 和为target的连续正数序列
- 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
- 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> result = new ArrayList<>();
//target肯定是奇数（由两个连续的数相加(奇数加偶数等于奇数)）
//最大的连续子序列肯定是target的一半的上界加下界（target = mid+mid+1）
int mid = target/2;
//1.滑动窗口暴力法
/*
for(int i=1; i<=mid; i++){
int sum = 0;
int j=i;
while(sum < target){
sum += j++;
}
if(sum == target){
int[] temp = new int[j-i];
for(int k=0; k<j-i; k++){
temp[k] = k+i;
}
result.add(temp);
}
}*/
//双指针优化
for(int l=1,r=2; l<r; ){
int sum = (l + r) * (r - l + 1) / 2;
if (sum == target){
int[] temp = new int[r-l+1];
for (int i = l; i <= r; ++i) temp[i-l] = i;
result.add(temp);
l++;
}
else if (sum < target) r++;
else l++;
}
return result.toArray(new int[result.size()][]);
}
}
LeetCode.994 腐烂的橘子
- 广度遍历即可（使用队列）
- 每分钟每个腐烂的橘子(2)都会使其上下左右的新鲜橘子(1)腐烂.
- 第一个腐烂的橘子在第一个网格(0,0)，所以只让其上下左右的新鲜橘子入队。
- 用 minute 标记腐烂时间，并让新鲜橘子(1)变为腐烂的橘子(2)
- 用 minute 记录腐烂的持续时间，每一层的橘子在内一层的橘子的腐烂时间基础之上自增 1，代表时间过了 1 分钟。
- 最后检查网格中是否还有新鲜的橘子
有，返回 -1 代表 impossible。
没有则返回 minute。
在给定的网格中，每个单元格可以有以下三个值之一：
值0代表空单元格；
值1代表新鲜橘子；
值2代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。
示例 1：
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：
输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示：
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 仅为0、1或2
class Solution {
int[][] dir = { {-1,0},{1,0},{0,-1},{0,1} };
class Node{
int x;
int y;
int minute;
Node(int x, int y, int minute){
this.x = x;
this.y = y;
this.minute = minute;
}
}
public int orangesRotting(int[][] grid) {
int rows = grid.length;
int clunms = grid[0].length;
int minute = 0;
Queue<Node> queue = new LinkedList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < clunms; j++)
if (grid[i][j] == 2)
queue.add(new Node(i, j, minute));
}
while (!queue.isEmpty()) {
Node node = queue.poll();
minute = node.minute;
for (int k = 0; k < 4; k++) { //一个腐烂，四周受害
int newX = node.x + dir[k][0];
int newY = node.y + dir[k][1];
if (newX >= 0 && newX < rows && newY >= 0 && newY < clunms && grid[newX][newY] == 1) {
grid[newX][newY] = 2; //标记腐烂
queue.add(new Node(newX, newY, node.minute + 1)); //腐烂周期+1
}
}
}
//check for fresh oranges
for(int[] row : grid) {
for (int i : row)
if (i == 1) return -1;
}
return minute;
}
}
