Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)You have the following 3 operations permitted on a word:a) Insert a character b) Delete a character c) Replace a character解题思路：DP问题，JAVA实现如下： public int minDistance(String word1, String word2) {int[] dp = new int[word2.length() + 1];for (int i ...
【151-Evaluate Reverse Polish Notation（计算逆波兰式）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Some examples: ["2", "1", "+", "3", "*"] ->((2 + 1) * 3) ->9["4", "13", "5", "/", "+"] ->(4 + (13 / 5)) ->6题目大意 ...
Implement int sqrt(int x).Compute and return the square root of x. 题意：算一个数的平方根。 好不容易想到用二分查找来解决改题，但是也破费了点力气，放到eclipse中调试来出来。注意点就是：取中值相乘，有可能会超过整数的最大范围，所以比较的时候就会出错。所以在定义的时候全部定义为long型。 第一版： public int mySqrt(int x){if (x == 0)return 0;long low = 1;long high = x;long tmp;long mid = 1;while (low <= h...
【137-Single Number II（只出现一次的数字II）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 题目大意 给一个数组，里面只有一个数字一次，其它数字都出现3次，找出这个出现一...
题目： Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.It doesn‘t matter what you ...
题目：A city‘s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B). The geometric information of each building is represented by a t...
题目： Given n non-negative integers representing the histogram‘s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area = 10 unit. For example, Given height = [2,1,5,6,2,3], return 10. 题解： 这道题自...
题目： Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [?2,1,?3,4,?1,2,1,?5,4], the contiguous subarray [4,?1,2,1] has the largest sum = 6. More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle 题解： 这道题要求 求连续的数...
题目：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.For 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.题意：给定一棵二叉树和一个...
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list.题意：不破坏原链表的情况下判断有没有环，，，，，，/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { pub...
解法：class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode l3 = null;boolean add = false;while (l1 != null || l2 != null) {//位数相加int plus;if (l1 == null) {plus = l2.val;} elseif (l2 == null) {plus = l1.val;} else {plus = l1.val + l2.val;}if (add) {plus++;add = false;}//生成节点 ListNode temp;if (plus >= 10) {temp = new ListNode(plus % 10);add = true;} el...
ZigZag Conversion一、题目如下： The string "PAYPALISHIRING" iswritten in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given a number of rows:string convert(strin...
第k个排列给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下："123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。说明：给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例 1:输入: n = 3, k = 3输出: "213"示例 2: 输入: n = 4, k = 9输出: "2314" 思路：观察一下： 我们取k=17。首先数组都是从0开始计数的，所以k-1=16。从16开始，先可以...
题目：同字符分组难度：Medium题目内容：Given an array of strings, group anagrams together.翻译：给定一组字符串数组，按相同字符组成的字符串分为一组。Example:Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [["ate","eat","tea"],["nat","tan"],["bat"] ]我的思路：因为要分组，那么使用map即可，相同的字符作为键，值为一个List作为对应分组1、首先遍历，每次将当前字符串打断成char数组，然后sort，判断ma...
Patching ArrayGiven a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.Example 1:nums = [1, 3], n = 6Return 1.Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.Now if we add/patch 2 to n...