用时：42min
class Solution {
public int removeDuplicates(int[] nums) {
/**
* 双指针，右指针遍历整个数组，左指针记录有效值
*/
int l = 0, r = 0;
Set<Integer> s = new HashSet<Integer>();
for(; r < nums.length; r++){
if(s.add(nums[r])){
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
l++;
}
}
return l;
}
}
/*优化后版本*/
class Solution {
public int removeDuplicates(int[] nums) {
// 非严格递增序列：去除重复元素后的序列是递增的，也就是说重复元素相邻
int l = 0, r = 0;
for(; r < nums.length; r++){
// 让左指针位置的元素是符合条件的，右指针一直向后遍历
// 换句话说就是让左指针后面的相邻元素不与左指针元素重复
if(nums[l] != nums[r]){
nums[l + 1] = nums[r];
l++;
}
}
return l + 1;
}
}
用时: 17min
class Solution {
public int maxProfit(int[] prices) {
// 当天买卖无收益，计算相邻两天的正收益之和 [贪心算法：通过局部最优解实现整体最优]
// 假如是第一天买，第三天卖 (d3 - d1) = (d3 - d2) + (d2 - d1)
int profit = 0;
for(int i = 1; i < prices.length; i++){
// profit += prices[i] - prices[i - 1] > 0 ? prices[i] - prices[i - 1] : 0;
profit += Math.max(0, prices[i] - prices[i - 1]);
}
return profit;
}
}
用时：38min
class Solution {
public void rotate(int[] nums, int k) {
/**
先整体翻转，再局部翻转
*/
k %= nums.length;
convertNums(nums, 0, nums.length - 1);
convertNums(nums, 0, k - 1);
convertNums(nums, k, nums.length - 1);
}
public void convertNums(int [] nums, int l , int r){
while(l < r){
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
l++;
r--;
}
}
}
用时：5min
class Solution {
public boolean containsDuplicate(int[] nums) {
// 占用额外内存
Set<Integer> s = new HashSet<>();
for(int num : nums){
if(!s.add(num)){
return true;
}
}
return false;
// 慢
// Arrays.sort(nums);
// for(int i = 1; i < nums.length; i++){
// if(nums[i - 1] == nums[i]){
// return true;
// }
// }
// return false;
}
}
用时: 26min
class Solution {
public int singleNumber(int[] nums) {
if(nums.length == 1){
return nums[0];
}
Arrays.sort(nums);
int t = nums[0];
int p = -1;
for(int i = 1; i < nums.length; i++){
if(nums[i] == p){
continue;
}
if(t == nums[i] && t != p){
p = nums[i];
t = -1;
}else{
t = t == -1 ? nums[i] : t;
}
}
return t;
}
}
/* 优化版本 */
class Solution {
public int singleNumber(int[] nums) {
// 位运算（异或运算，相同为零、不同为1, 0 ^ n = n，所以最后就剩下那个唯一的元素）
if(nums.length == 1){
return nums[0];
}
int result = 0;
for(int num : nums){
result ^= num;
}
return result;
}
}
用时: 32min
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
// 散列桶计数
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int num : nums1){
map.put(num, map.getOrDefault(num, 0) + 1);
}
int [] result = new int[nums1.length < nums2.length ? nums1.length : nums2.length];
int index = -1;
for(int num : nums2){
int count = map.getOrDefault(num, 0);
if(count > 0){
result[++index] = num;
map.put(num, count - 1);
}
}
return Arrays.copyOfRange(result, 0, index + 1);
}
}
用时: 33min
class Solution {
public int[] plusOne(int[] digits) {
int len = digits.length;
boolean last = false;
for(int i = len - 1; i >= 0; i--){
int num = digits[i] + 1;
if(num < 10){
digits[i] = num;
break;
}else{
digits[i] = num - 10;
}
if(i == 0){
last = num > 9;
}
}
int [] arr = last ? new int[digits.length + 1] : new int[digits.length];
if(last){
arr[0] = 1;
System.arraycopy(digits, 0, arr, 1, digits.length);
return arr;
}else{
return digits;
}
}
}
/* 优化版本 */
class Solution {
public int[] plusOne(int[] digits) {
for(int i = digits.length - 1; i >= 0; i--){
int num = digits[i] + 1;
digits[i] = num % 10;
if(num < 10){
return digits;
}
}
digits = new int[digits.length + 1];
// 为什么之赋值一个就够了呢？因为原数组空间不够的情况只能是数值为 10000(n个零)
digits[0] = 1;
return digits;
}
}
用时：5min
class Solution {
public void moveZeroes(int[] nums) {
int l = 0, r = 0;
while(r < nums.length){
if(nums[r] != 0){
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
l++;
}
r++;
}
}
}
用时：9min
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int num = target - nums[i];
int idx = map.getOrDefault(num, -1);
if(idx != -1){
return new int[]{idx, i};
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}
}
用时：20min
class Solution {
public boolean isValidSudoku(char[][] board) {
int [][] row = new int[9][9];
int [][] column = new int[9][9];
int [][][] block = new int[3][3][9];
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
continue;
}
int idx = board[i][j] - '0' - 1; // 数值要转化成对应索引，所以需要减一
row[i][idx]++;
column[j][idx]++;
block[i / 3][j / 3][idx]++;
if(row[i][idx] > 1 || column[j][idx] > 1 || block[i / 3][j / 3][idx] > 1){
return false;
}
}
}
return true;
}
}
用时：15min
class Solution {
public void rotate(int[][] matrix) {
/** 先主对角线翻转，然后再左右翻转 */
int [][] arr = new int[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < i; j++){
int num = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = num;
}
}
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length / 2; j++){
int num = matrix[i][j];
matrix[i][j] = matrix[i][matrix[0].length -1 - j];
matrix[i][matrix[0].length -1 - j] = num;
}
}
}
}