27. Remove Element
Given an array and a value, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Example:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
题目：在一个数组里面移除指定value，并且返回新的数组长度。
思路：用指定的value的后一个数替换它，相当于val后面的数字整体前移。需要设置一个计数count，当遇到val的时候count不计数。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int removeElement(int[] nums, int val) {
int count = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] != val){
nums[count] = nums[i];
count ++;
}
}
return count;
}
}
26. Remove Duplicates from Sorted Array
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 by modifying the input array in-place with O(1) extra memory.
Example:
Given 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 leave beyond the new length.
题目：在一个排序好的数组里面删除 重复的元素，并返回长度。
思路：设置一个j=0，让数组从1开始遍历，每次循环若nums[i] == nums[j]，则i继续后遍历，而j不变；直到遇到不相等的元素，令nums[++j] = nums[i]。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0) return 0;
int j = 0;
for(int i = 1; i < nums.length; i++){
if(nums[i] != nums[j]){
nums[++j] = nums[i];
}
}
return j + 1;
}
}
80. Remove Duplicates from Sorted Array II
Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.
题目：在一个排序好的数组里，允许元素至多有2个，将其它重复元素删除，返回长度。
思路：用一个计数器，允许一个数字出现两次，若大于两次，则与删除重复元素相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int removeDuplicates(int[] nums) {
int count = 0, j = 0;
for(int i = 1; i < nums.length; i++){
if(nums[i] == nums[j]){
count++;
if(count < 2){
nums[++j] = nums[i];
}
}
else{
nums[++j] = nums[i];
count = 0;
}
}
return j+1;
}
}
66. Plus One
Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
题目：一个数字用一个数组来表示，首位各个位数上的数字为降序排列，首位不为0，现将该数字加1，返回该数组。
思路：注意进位，当首位需要进位的时候，数组要扩容1。
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}
118. Pascal’s Triangle
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5, Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
题目：打印一个帕斯卡三角。
思路：每一层除去头尾的数，等于上一层相同位置的数字加上前一个位置的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.ArrayList;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
for(int i = 0; i < numRows; i++){
ArrayList<Integer> layer = new ArrayList<Integer>();
if(i==0) layer.add(1);
else{
for(int j = 0; j < i + 1; j++){
if(j == 0 || j == i) layer.add(1);
else layer.add(res.get(i - 1).get(j) + res.get(i - 1).get(j - 1));
}
}
res.add(layer);
}
return res;
}
}