LeetCode[155] Min Stack

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.

分析:

Java中本来就有Stack。本题跟普通Stack的区别是需要记住最小值,关键在于push和pop方法。在push时,若x比当前的min更小,则先push值min,再push值x,并令min = x。在pop时,若该值为min值,需要pop两次,并且让第二次pop的值为min值。push和pop相呼应。

代码:

阅读全文

LeetCode[190] Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:

If this function is called many times, how would you optimize it?

分析:

最简单直接的做法,从右向左把一位位取出来,添加到新生成的整数的最低位即
可。

代码:

阅读全文

LeetCode[191] Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

分析:

题目要求算出一个int数二进制表示中1的个数。

n和n-1按位与可以去掉n二进制表示中最右边一位1.

令 n =1101011000

则 n-1=1101010111

n&(n-1)=1101010000

经过K次n&n-1,n变为0.K即n的二进制表示中1的个数。

代码:

阅读全文

LeetCode[202] Happy Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

分析:

这题找到规律后就简单了。如果右边的出现了某个重复的数,但不是1,说明会无限循环下去,这个数就不是快乐数,如果是1,则是快乐数。

代码:

阅读全文

LeetCode[205] Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

Note:
You may assume both s and t have the same length.

分析:

这道题思路跟 LeetCode[290] Word Pattern 一模一样。

代码:

阅读全文

LeetCode[215] Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

分析:

PriorityQueue内部是由堆实现的。每次remove()都会将最小的元素删除。

建一个PriorityQueue,将数组元素都加入该队列。然后移出nums.length-k个,下一个出来的就是第K大的。

代码:

阅读全文


Copyright © 2016 - 2017 LBD's Blog All Rights Reserved.

访客数 : | 访问量 :