- 1.删除排序数组中的重复项
- 2. 买卖股票的最佳时机
- 3.旋转数组
- 法1 暴力解法
- 法2 法1的简单优化版，向后移动k位
- 法3.三次旋转
- 4.存在重复元素
- 5.只出现一次的数字
- 6.加一
- 7.移动零
- 8.两数之和
- 9.有效数独
- 法一：暴力求解
- 法二：引入数组
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
提示：
●0 <= nums.length <= 3 * 10000
●-1000<= nums[i] <= 10000
●nums 已按升序排列
class Solution {
public int removeDuplicates(int[] nums) {
int count = 0;//储存重复的数字个数
for (int right = 1; right < nums.length; right++) {
if (nums[right] == nums[right - 1]) {
//如果有重复的，count要加1
count++;
} else {
//如果没有重复，后面的就往前挪
nums[right - count] = nums[right];
}
}
//数组的长度减去重复的个数
return nums.length - count;
}
}
2. 买卖股票的最佳时机
定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
思路： 实际上是前一项减去后一项的值，找出其中的最大值
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;//先考虑数组是否是空的
}
int max = 0;//定义一个数据便于储存最大值
for (int i = 0; i < prices.length - 1; i++) {
if (prices[i] < prices[i+1]) {
max = max + prices[i+1] - prices[i];
}
}
return max;
}
}
3.旋转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
法1 暴力解法输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
会显示超时，直接将数组中的元素一次次轮转
class Solution {
public void rotate(int[] nums, int k) {
k = k%nums.length;//k可能会超出数组长度
for (int j = 0; j < k; j++) { //使程序轮转k次
int temp = nums[nums.length-1];
for (int i = nums.length - 1; i > 0; i--) {
nums[i] = nums[i-1];//轮转一次
}
nums[0] = temp;
}
}
}
法2 法1的简单优化版，向后移动k位
可以把最终结果看作是原数组每一项向后移动k位，若大于数组最大下标的再从头开始，即（i+k）%nums.length得到每个元素的下标
class Solution {
public void rotate(int nums[], int k) {
int length = nums.length;
int temp[] = new int[length];
//把原数组值放到一个临时数组中，
for (int i = 0; i < length; i++) {
temp[i] = nums[i];
}
//然后在把临时数组的值重新放到原数组，并且往右移动k位
for (int i = 0; i < length; i++) {
nums[(i + k) % length] = temp[i];
}
}
}
法3.三次旋转
再观察一次题目，假如原数组为[1,6,4,9,13,11],旋转三次为[9,13,11,1,6,4],实际上可以发现先将后k项和余下的(nums.length-k)项分别反转，再将整体反转即可，无论k为多少都只需反转三次 (实际上应该也是法一的优化版…)
class Solution {
public void rotate(int[] nums, int k) {
int length = nums.length;
k %= length;
reverse(nums, 0, length - k - 1);//先反转前面的
reverse(nums, length - k, length - 1);//接着反转后面k个
reverse(nums, 0, length - 1);//最后在反转全部的元素
}
//把数组中从[start，end]之间的元素两两交换,也就是反转
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
}
4.存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
思路： 最好先排序再判断
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);//给数组排序
for(int i=0;i
还有另一种方法，比较麻烦会超时
class Solution {
public boolean containsDuplicate(int[] nums) {
int[] a=new int[nums.length];
for(int i=0;i0){
return true;
}
}
return false;
}
}
5.只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入: [2,2,1]
输出: 1
思路一 ：先排序，再两项之间相互比较（比较麻烦）
class Solution {
public static int singleNumber(int[] nums) {
if(nums == null){
return 0;
}
if(nums.length == 1){
return nums[0];
}
Arrays.sort(nums);
if(nums[0] != nums[1]){
return nums[0];
}
for(int i = 1;i < nums.length - 1;i++){
if(nums[i - 1] != nums[i] && nums[i] != nums[i + 1]) {
return nums[i];
}
}
if(nums[nums.length - 2] != nums[nums.length - 1]){
return nums[nums.length - 1];
}
return 0;
}
}
思路二： 用异或（^）
异或运算，相异为真，相同为假，所以 a^a=0,
a^0=a;所以当运算结果不为0时即为最终结果。
class Solution{
public int singleNumber(int nums[]) {
int result = 0;
for (int i = 0; i < nums.length; i++)
result ^= nums[i];
return result;
}
}
6.加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入： digits = [1,2,3]
输出：[1,2,4]
解释： 输入数组表示数字 123。
思路：当考虑的时候忽略了9的特殊性；digits[digits.length-1]!=9,只需要把最后一位加上一(中间有9的也要考虑后面的步骤…)；digits[digits.length-1]==9，把最后一位加一变0，前一位加一，若为9再以此类推。
class Solution{
public int[] plusOne(int[] digits) {
int length = digits.length;
for (int i = length - 1; i >= 0; i--) {
if (digits[i] != 9) {
//如果数组当前元素不等于9，直接加1
digits[i]++;
return digits;
} else {
//如果数组当前元素等于9，那么加1之后变0
digits[i] = 0;
}
}
//除非数组中的元素都是9，否则不会走到这一步，
//如果数组的元素都是9，我们只需要把数组的长度
//增加1，并且把数组的第一个元素置为1即可
int temp[] = new int[length + 1];
temp[0] = 1;
return temp;
}
}
7.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
思路： 数组元素不为零的按顺序依次填充；再把后面的元素全变为0。
class Solution {
public void moveZeroes(int[] nums) {
int a=0;//用来储存数组中元素不为0的个数
if(nums.length==0||nums=null){
}//考虑一下数组为空的情况
for(int i=0;i
简单优化版
public void moveZeroes(int[] nums) {
int i = 0;//统计前面0的个数
for (int j = 0; j < nums.length; j++) {
if (nums[j] == 0) {//如果当前数字是0就不操作
i++;
} else if (i != 0) {
//否则，把当前数字放到最前面那个0的位置，
//然后再把当前位置设为0
nums[j - i] = nums[j];
nums[j] = 0;
}
}
}
8.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入： nums = [2,7,11,15], target = 9
输出：[0,1]
解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
思路： 暴力求解，使用两个for循环找出那两个下标
class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
for (int i = 0; i < length - 1; i++) {
for (int j = i + 1; j < length; j++)
if (nums[i] + nums[j] == target)
return new int[]{i, j};
}
return new int[]{-1, -1};
}
}
9.有效数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。
示例 1：
输入： board =
[[“5”,“3”,".",".",“7”,".",".",".","."]
,[“6”,".",".",“1”,“9”,“5”,".",".","."]
,[".",“9”,“8”,".",".",".",".",“6”,"."]
,[“8”,".",".",".",“6”,".",".",".",“3”]
,[“4”,".",".",“8”,".",“3”,".",".",“1”]
,[“7”,".",".",".",“2”,".",".",".",“6”]
,[".",“6”,".",".",".",".",“2”,“8”,"."]
,[".",".",".",“4”,“1”,“9”,".",".",“5”]
,[".",".",".",".",“8”,".",".",“7”,“9”]]
输出： true
法一：暴力求解
思路一 ：先判断空格；再判断行列和九宫格
很麻烦很麻烦…
class Solution {
public boolean isValidSudoku(char[][] board) {
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char c=board[i][j];
if(c=='.'){
continue;
} //判断空格，无空格跳出
else{
for(int m=j+1;m<9;m++){
if(c==board[i][m]){
return false;
}//判断行中是否有相等的数
}
for(int m=i+1;m<9;m++){
if(c==board[m][j]){
return false;
}//判断列中是否有相等的数
}
if(!sh(board,c,i,j))
return false;
}
}
}
return true;
}
//判断所属3*3小方格是否重复
public boolean sh(char[][] board,char c,int i,int j){
int x=i/3; //约束判断的范围
int y=j/3;
for(int m=x*3;m<(x+1)*3;m++){
for(int n=y*3;n<(y+1)*3;n++){
if(m==i&&n==j){
continue;
}
if(board[m][n]==c){
return false;
}
}
}
return true;
}
}
法二：引入数组
思路二： 和上面的思路并没有什么不同，引入数组显得更简洁，运算量也更少
public class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] row=new boolean[9][10];
boolean[][] col=new boolean[9][10];
boolean[][] fan=new boolean[9][10];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char c=board[i][j];
if(c!='.'){
int num=Integer.valueOf(String.valueOf(c));//字符转数字
if(row[i][num]||col[j][num]||fan[i/3*3+j/3][num]){
return false;
}
row[i][num]=true;
col[j][num]=true;
fan[i/3*3+j/3][num]=true;
}
}
}
return true;
}
}
