Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. 这道题的巧妙之处在于，每一个值可以跳“值”大小步数。所以我们的思路如下： 1.记录到现在为止能跳...
Given two words (beginWord and endWord), and a dictionary‘s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:Only one letter can be changed at a time.Each transformed word must exist in the word list. Note that beginWord is not a transformed word.Note:Return 0 if there is no such transformation sequence.All words have the same length.All words co...
Number of Digit OneGiven an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.For example:Given n = 13,Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13. 数学题，真是为难了数学拙计的我了。递归分治，拿8192举栗子：把8192拆成：1-999 -> 递归(999)1000-1999 -> 1000个1 + 递归(999)2001-2999 -> 递归(999)..8000-8192 ->...
Given a collection of integers that might contain duplicates, S, return all possible subsets.Note:Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. For example, If S = [1,2,2],a solution is:[[2],[1],[1,2,2],[2,2],[1,2],[] ]public class Solution {public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {ArrayList<ArrayList<Integer>> resu...
这是悦乐书的第288次更新，第305篇原创01 看题和准备今天介绍的是LeetCode算法题中Easy级别的第156题（顺位题号是682）。你现在是棒球比赛点记录器。给定一个字符串列表，每个字符串可以是以下4种类型之一：整数（一轮的得分）：直接表示你在这轮中获得的积分数。“+”（一轮的得分）：表示你在这一轮得到的分数是最后两个有效回合分数的总和。“D”（一轮得分）：表示你在这一轮得到的分数是最后一轮有效回合分数的加倍数据。“C”...
题目：Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. 题解：这道题是说让B merge到 A 里面。先复习下原本我们在MergeSort里面怎么利用一个新建的数量来merge two array：代码如下： 1 pu...
题目：Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.Example:Input:13/2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).Note: There are at least two nodes in this BST.题意及分析：给出一颗二叉搜索树（节点为非负），要求求出任意两个点之间差值绝对值的最小...
题目：Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.For example, Given board =[["ABCE"],["SFCS"],["ADEE"] ] word = "ABCCED",-> returns true,word = "SEE",-> returns true,word = "ABCB",-...
Question: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board =[["ABCE"],["SFCS"],["ADEE"] ] word = "ABCCED",-> returns true,word = "SEE",-> returns true,word = "A...
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.Note: You may not slant the container.解题思路：本题是经典的“水箱”问题，最简单的方法是暴力枚举，时...
这个题目leetcode上提示用动态规划，但是那样要O(n^2)。我自己想出了一个O(n)的算法，并提交通过。【题目】Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.For "(()", the longest valid parentheses substring is "()", which has length = 2.Another example is ")()())", where the longest valid parentheses substring is "()()", w...
【113-Path Sum II（路径和II）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. For example: Given the below binary tree and sum = 22, 5/ 4 8/ / 11 13 4/ \ / 7 2 5 1 return[[5,4,11,2],[5,8,4,5] ]题目大意 给定一棵二叉树...
Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree without changing its structure.Note:A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? 使用O(n)空间的话可以直接中序遍历来找问题节点。如果是O(1)空间的话，基本上就只能是原地操作了。这里介绍一个Morris Inorder Traversal。可以实现：1. 如果当前节点有左子树，那么找到左子树的...
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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.解题思路：一次遍历，每次找到最小的Buy点即可，JAVA实现如下： public int maxProfit(int[] prices) {int buy = 0;int profit = 0;for (int i = 0; i < prices.len...
题目：Given an array of integers and an integer k,find out whether there there are two distinct indices i and j inthe array such that nums[i] = nums[j] andthe difference between i and j isat most k.解题：第一种办法：最直接用双重循环进行判断，o(n^2)复杂度不能通过第二种办法：用哈希表，key存数组元素值，value存元素对应的索引，每来一个元素进行判断如果之前没有存过则存进去，如果之前有存则取出之前那个元素...