自己开始的思路：
1.先把所有的0放到最后
2.再把原数组所有的0删除
for i in range(len(nums))
if nums[i] ==0 :
nums.append(0)
for i in range(len(nums))
if nums[i] ==0 :
nums.delete(0)
# 先数零的个数，再用append 和 remove暴力操作
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
n = nums.count(0)
for i in range(n): # n是0的个数
nums.append(0) # 时间复杂度 O(1)
nums.remove(0) # 时间复杂度 O(n)
'''
评价：
优点：程序简洁易懂
缺点：时间复杂度高
'''
class Solution(object):
def moveZeroes(self, nums):
zero_position = 0 # records the position of "0"
for i in xrange(len(nums)):
if nums[i] != 0:
nums[i], nums[zero_position] = nums[zero_position], nums[i]
zero_position += 1
'''
解说：
zero_position在遇到0就会比i少1，所以他一直记录着最早的0的位置，只要遇到非0就进行互换，所以只要扫描一遍就可以解决
评价：
优点：程序
缺点：时间复杂度一般
'''
c++版：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i,j;
for(i=0,j=0;i<nums.size();i++){
if(nums[i]!=0){
swap(nums[i],nums[j]);
j++;
}
}
}
};
国际站：
java版
// Shift non-zero values as far forward as possible
// Fill remaining space with zeros
/*
思路：
*/
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) return;
int insertPos = 0;
for (int num: nums) {
if (num != 0) nums[insertPos++] = num;
}
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}
python版：
c++版：
装最多水：container-with-most-water
国内站
java版：
/*
思路：
*/
class Solution {
public int maxArea(int[] a) {
// 1.枚举 ：left bar x ,right bar y, (x-y)*height_diff
// 时间复杂度：O(n^2)
int max = 0;
for (int i = 0; i < a.length-1; ++i) {
for (int j = i+1; j< a.length; j++) {
int area =(j - i) * Math.min(a[i],a[j]);
max = Math.max(max,area);
}
}
return max;
}
}
/*
评价：
优点：写出来容易
缺点：时间复杂度过高
*/
/*
思路：
*/
// 时间复杂度为 O(n),左右边界i j ，中间收敛；
class Solution {
public int maxArea(int[] a) {
int max=0;
for(int i=0,j=a.length-1;i<j;) {
int minHeight = a[i] <a[j] ?a[i++]:a[j--];
int area = (j-i+1)*minHeight;
max = Math.max(max,area);
}
return max;
}
}
/*
评价：
优点：时间复杂度低
缺点：
*/
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j){
res = height[i] < height[j] ?
Math.max(res, (j - i) * height[i++]):
Math.max(res, (j - i) * height[j--]);
}
return res;
}
}
python版：
class Solution:
def maxArea(self, height: List[int]) -> int:
i, j, res = 0, len(height) - 1, 0
while i < j:
if height[i] < height[j]:
res = max(res, height[i] * (j - i))
i += 1
else:
res = max(res, height[j] * (j - i))
j -= 1
return res
c++版：
class Solution {
public:
int maxArea(vector<int>& height) {
int res = 0;
int i = 0;
int j = height.size() - 1;
while (i < j) {
int area = (j - i) * min(height[i], height[j]);
res = max(res, area);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return res;
}
};
国外站
java版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
爬楼梯：climbing-stairs
典型的套路题，第一次做感觉贼难，没有思路，会了以后就感觉， 套路，全都是套路，很简单
注意：优化的思想主要有两种，一是空间换时间， 二是升维
其实为什么说算法基本就那么几个，贪心、动态、分支等，而且他们的差别也不是很大，其一根本原因就是
计算机基本只适合处理机械重复性问题，用的语言就是if else for while recursion的逻辑或重复性代码
这对于教学就有指导意义，就是也需要重复练习。
做题的时候懵比的时候，怎么办？
第一步是，从0开始找规律
第二步是，找出规律中的重复子问题
第三步是，编码
国内站
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
f(1)：1
f(2)：2
f(3)：f(1)+f(2)=3
f(4): f(2)+f(3)=5
跨到第n阶的时候，只有两种可能，一是从n-1跨过来，二就是从n-2阶跨过来
所以 ：
f(n)=f(n-1)+f(n-2)
for(int i =0;i<=n;++i) {
a[i]=a[i-1]+a[i-2]
}
'''
class Solution(object):
def climbStairs(self,n) :
if(n<=2):return n
f1,f2,f3=1,2,3
for i in range(3,n+1):
f3=f1+f2
f1=f2
f2=f3
return f3
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
The problem seems to be a dynamic programming one. Hint: the tag also suggests that!
Here are the steps to get the solution incrementally.
Base cases:
if n <= 0, then the number of ways should be zero.
if n == 1, then there is only way to climb the stair.
if n == 2, then there are two ways to climb the stairs. One solution is one step by another; the other one is two steps at one time.
The key intuition to solve the problem is that given a number of stairs n, if we know the number ways to get to the points [n-1] and [n-2] respectively, denoted as n1 and n2 , then the total ways to get to the point [n] is n1 + n2. Because from the [n-1] point, we can take one single step to reach [n]. And from the [n-2] point, we could take two steps to get there.
The solutions calculated by the above approach are complete and non-redundant. The two solution sets (n1 and n2) cover all the possible cases on how the final step is taken. And there would be NO overlapping among the final solutions constructed from these two solution sets, because they differ in the final step.
Now given the above intuition, one can construct an array where each node stores the solution for each number n. Or if we look at it closer, it is clear that this is basically a fibonacci number, with the starting numbers as 1 and 2, instead of 1 and 1.
国外站
The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.
/*
思路：
*/
public List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<>();
for (int i = 0; i < num.length-2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
int lo = i+1, hi = num.length-1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
res.add(Arrays.asList(num[i], num[lo], num[hi]));
while (lo < hi && num[lo] == num[lo+1]) lo++;
while (lo < hi && num[hi] == num[hi-1]) hi--;
lo++; hi--;
} else if (num[lo] + num[hi] < sum) lo++;
else hi--;
}
}
}
return res;
}
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
反转链表:reverse-linked-list/
class Solution {
public ListNode reverseList(ListNode head) {
/* iterative solution */
ListNode newHead = null;
while (head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
}
public class Solution {
public ListNode swapPairs(ListNode head) {
if ((head == null)||(head.next == null))
return head;
ListNode n = head.next;
head.next = swapPairs(head.next.next);
n.next = head;
return n;
}
}
环形链表:linked-list-cycle/
国内站
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
1.Use two pointers, walker and runner.
2.walker moves step by step. runner moves two steps at time.
3.if the Linked List has a cycle walker and runner will meet at somepoint.
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
Define two pointers slow and fast. Both start at head node, fast is twice as fast as slow. If it reaches the end it means there is no cycle, otherwise eventually it will eventually catch up to slow pointer somewhere in the cycle.
Let the distance from the first node to the the node where cycle begins be A, and let say the slow pointer travels travels A+B. The fast pointer must travel 2A+2B to catch up. The cycle size is N. Full cycle is also how much more fast pointer has traveled than slow pointer at meeting point.
A+B+N = 2A+2B
N=A+B
From our calculation slow pointer traveled exactly full cycle when it meets fast pointer, and since originally it travled A before starting on a cycle, it must travel A to reach the point where cycle begins! We can start another slow pointer at head node, and move both pointers until they meet at the beginning of a cycle.
/*
思路：
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
ListNode slow2 = head;
while (slow2 != slow){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
K 个一组翻转链表:reverse-nodes-in-k-group/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
// head - head-pointer to direct part,
// curr - head-pointer to reversed part;
while (count-- > 0) { // reverse current k-group:
ListNode tmp = head.next; // tmp - next head in direct part
head.next = curr; // preappending "direct" head to the reversed list
curr = head; // move head of reversed part to a new node
head = tmp; // move "direct" head to the next node in direct part
}
head = curr;
}
return head;
}
}
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
class Solution {
public int removeDuplicates(int[] A) {
if ( A.length == 0 ) return 0;
int j =0;
for (int i =0;i<A.length;i++) {
if (A[i]!=A[j]){
A[++j]=A[i];
}
}
return ++j;
}
}
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
/*
思路：
*/
public int removeDuplicates(int[] A) {
if (A.length==0) return 0;
int j=0;
for (int i=0; i<A.length; i++)
if (A[i]!=A[j]) A[++j]=A[i];
return ++j;
}
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
旋转数组:rotate-array/
国内站
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
/*
思路：
*/
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
合并两个有序链表:merge-two-sorted-lists/
国内站
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
/*
评价：
优点：
缺点：
*/
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
class Solution {
public void merge(int A[],int m,int B[], int n) {
int i = m-1;
int j = n-1;
int k = m+n-1;
while(i>-1 && j >-1) {
A[k--] = A[i] > B[j] ? A[i--] : B[j--];
}
while(j > -1) {
A[k--] = B[j--];
}
}
}
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
/*
思路：
*/
public void merge(int A[], int m, int B[], int n) {
int i=m-1, j=n-1, k=m+n-1;
while (i>-1 && j>-1) A[k--]= (A[i]>B[j]) ? A[i--] : B[j--];
while (j>-1) A[k--]=B[j--];
}
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
两数之和:two-sum/
国内站
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
/*
思路：
*/
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[1] = i;
result[0] = map.get(target - numbers[i]);
return result;
}
map.put(numbers[i], i);
}
return result;
}
}
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
加一:plus-one/
国内站
/*
思路：
找最近重复子问题
一般只写：if else for while recursion的重复性代码
*/
/*
评价：
优点：
缺点：
*/
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
python版：
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
'''
思路：
'''
'''
评价：
优点：
缺点：
'''
c++版：
/*
思路：
*/
/*
评价：
优点：
缺点：
*/
国外站
/*
思路：
*/
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
for(int i=n-1; i>=0; i--) {
if(digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
int[] newNumber = new int [n+1];
newNumber[0] = 1;
return newNumber;
}
}
/*
评价：
优点：
缺点：
*/
编程语言
发布于：2021-08-03 13:02
|
阅读数：551
|
评论：0
QQ好友和群
QQ空间
