算法日记 four
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法日记 four，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9106字，纯文字阅读大概需要14分钟。
内容图文
50. Pow(x, n)
Implement pow(x,?n), which calculates x raised to the power n (xn).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
class Solution {
public double myPow(double x, int n) {
if(n==0) return 1;
if(n==Integer.MIN_VALUE) return 1/x* myPow(x,n+1);
if(n<0){
x=1/x;
n=-n;
}
return (n%2==0)? myPow(x*x,n/2):x* myPow(x*x,n/2);
}
}
41First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
class Solution {
public int firstMissingPositive(int[] nums) {
Arrays.sort(nums);
if(nums.length==0) return 1;
int k=1;
for(int i=0;i<nums.length;i++){
if(nums[i]<=0) continue;
if(i>0&&nums[i]==nums[i-1]) continue;
if(nums[i]!=k){
return k;
}
k++;
}
if(nums[nums.length-1]>0){
return nums[nums.length-1]+1;
}else{
return 1;
}
}
}
35. Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
class Solution {
public int searchInsert(int[] nums, int target) {
int index=0;
if(nums[nums.length-1]<target) return nums.length;
for(int i=0;i<nums.length;i++){
if(nums[i]==target){
index=i;
}
if(i>0&&nums[i-1]<target&&nums[i]>target){
index=i;
}
}
return index;
}
}
54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> result=new ArrayList<Integer>();
if(matrix.length==0) return result;
int left=0;//右移坐标
int right=matrix[0].length-1;//左移坐标
int up=0;
int down=matrix.length-1;
while(left<=right&&up<=down){
//-->右移
for(int i=left;i<=right;i++){
result.add(matrix[up][i]);
}
up++;
//-->下移
for(int i=up;i<=down;i++){
result.add(matrix[i][right]);
}
right--;
//-->左移
if(up<=down){
for(int i=right;i>=left;i--){
result.add(matrix[down][i]);
}
down--;
}
//-->上移
if(left<=right){
for(int i=down;i>=up;i--){
result.add(matrix[i][left]);
}
left++;
}
}
return result;
}
}
19. Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first=new ListNode(0);
first.next=head;
ListNode currentone=first;
ListNode currenttwo=first;
if(head==null||n<0) return first;
for(int i=0;i<n+1;i++){
currentone=currentone.next;
}
while(currentone!=null){
currentone=currentone.next;
currenttwo=currenttwo.next;
}
currenttwo.next=currenttwo.next.next;
return first.next;
}
}
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
class Solution {
public String longestCommonPrefix(String[] strs) {
int length = Integer.MAX_VALUE;
StringBuilder stringbuilder = new StringBuilder();
if (strs.length == 0 || strs == null)
return "";
if (strs.length == 1)
return strs[0];
for (int i = 0; i < strs.length; i++) {
length = (strs[i].length() < length) ? strs[i].length() : length;
}
if (length == 0)
return "";
for (int j = 0; j < length; j++) {
for (int i = 0; i < strs.length; i++) {
if (strs[i].charAt(j) != strs[0].charAt(j))
return stringbuilder.toString();
}
stringbuilder.append(strs[0].charAt(j));
}
return stringbuilder.toString();
}
}
56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
ArrayList<Interval> result=new ArrayList<Interval>();
if(intervals.size()==0||intervals.size()<1) return result;
int len=intervals.size();
int []starts=new int[len];
int [] ends=new int[len];
for(int i=0;i<len;i++){
starts[i]=intervals.get(i).start;
ends[i]=intervals.get(i).end;
}
Arrays.sort(starts);
Arrays.sort(ends);
for (int i=0,j=0; i < len; i++) {
if(i == len - 1 || starts[i + 1] > ends[i]) {
result.add(new Interval(starts[j], ends[i]));
j=i+1;
}
}
return result;
}
}
59. Spiral Matrix II
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
class Solution {
public int[][] generateMatrix(int n) {
int[][] result=new int[n][n];
int left=0;
int right=n-1;
int up=0;
int down=n-1;
int num=1;
while(num<=n*n){
//向右转
for(int i=left;i<=right;i++){
result[left][i]=num++;
}
up++;
//向下转
for(int i=up;i<=down;i++){
result[i][right]=num++;
}
right--;
//向左转
if(down>=up){
for(int i=right;i>=left;i--){
result[down][i]=num++;
}
down--;
}
//向上转
if(right>=left){
for(int i=down;i>=up;i--){
result[i][left]=num++;
}
left++;
}
}
return result;
}
}
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
class Solution {
public int trap(int[] height) {
int len=height.length;
int sum=0;
if(height==null||len==0) return 0;
int left=0,right=len-1;
int maxLeft=0;
int maxRight=0;
while(left<right){
maxLeft=Math.max(height[left],maxLeft);
maxRight=Math.max(height[right],maxRight);
if(maxLeft<maxRight){
sum+=maxLeft-height[left];
left++;
}else{
sum+=maxRight-height[right];
right--;
}
}
return sum;
}
}
38. Count and Say(这题没做都)
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 is read off as "one 1" or 11.11 is read off as "two 1s" or 21.21 is read off as "one 2, then one 1" or 1211.
Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"
class Solution {
public String countAndSay(int n) {
String num = "1";
for(int m = 1; m<n ; m++ ){
num = getString(num);
}
return num;
}
public String getString(String num){
StringBuffer result = new StringBuffer();
int j = 0 , i = 0 , n = 0;
while( i< num.length()){
char ch = num.charAt(i);
while( j < num.length() && ch == num.charAt(j) )
j++;
n = j - i;
result.append(n).append(ch-'0');
i = j;
}
return result.toString();
}
}
60. Permutation Sequence
The set [1,2,3,...,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
这题暂时不做都看不懂就不做
64. Minimum Path Sum最典型的动态规划,我真的是太久没有做算法题目了!
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
? [1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
class Solution {
public int minPathSum(int[][] grid) {
if(grid.length==0) return 0;
for(int i=1;i<grid.length;i++){
grid[i][0]+=grid[i-1][0];
}
for(int j=1;j<grid[0].length;j++){
grid[0][j]+=grid[0][j-1];
}
for(int i=1;i<grid.length;i++){
for(int j=1;j<grid[0].length;j++){
grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
}
}
return grid[grid.length-1][grid[0].length-1];
}
}
内容总结
以上是互联网集市为您收集整理的算法日记 four全部内容，希望文章能够帮你解决算法日记 four所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。